数据结构（2）

六、数Tree

数的表示方法

双亲表示法

每个结点除了自身的数据域外，添加一个指示器，指向双亲在数组中的位置(链式存储结构则是指针域)

根结点的为-1 链表则是null

灵魂画师

image-20221123001919199

index data parent
0 A -1
1 B 0
2 C 0
3 D 1
4 E 1
5 F 2
…

通过上述数组表我们找到当前结点的双亲结点时间复杂度为O(1) ，但如果要查找孩子需要遍历整个树

如果我们需要知道结点的孩子肿么办，再新增一个firstchild 长子域 左边孩子 不存在同样可以值设置为-1

index data parent firstchild
0 A -1 1
1 B 0 3
2 C 0 6
3 D 1 8
4 E 1 -1
5 F 2 -1
…
  • 如果你还想知道一个结点的更多信息 比如 右孩子 ，兄弟 只需在数组接触上继续添加这些域即可

孩子表示法

data

chiled head 孩子链表的头指针

每个结点指针域个数等于该结点的度，顺序结构单独定义一个数组长度为所有结点的长度 用于存放孩子结点下标

而原数组中孩子结点的指针域作为头指针 指向chiled数组 直到这个线性表指向空

同样如果需要知道双亲结点我们也可以添加一个双亲域

孩子兄弟表示法

任意一个结点有自身数据域 ，它的左孩子存在就是唯一，右孩子也是一样

data 数据

firstchild 左孩子

rightchild 右孩子

  • 如果一个树并不是二叉树，每个结点的度差值都很大，因为数组结构所以会浪费一大部分空间

    解决方法，再建立一个数组 大小为 结点数，这个数组的目的是建立一个孩子结点的链表，而链表的头指针就是数组中的孩子域

    image-20221123232443510

index data parent firstchild(充当头索引)
0 A -1 1
1 B 0 3
2 C 0 4
3 D 1 6
4 E 2 9
5 F 2 ^
6 G 3 ^
7 H 3 ^
8 I 3 ^
9 J 4 ^

孩子结点静态链表

index_child next
0 ^
1（B） 2
2 ( C ) ^
3 （ D） ^
4 (E) 5(F)
5(F) ^
6 ^
7 ^
8 ^
9(E) ^ 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//下面是孩子表示法结点定义

public class Tree {
    
}

class ElemType{//数据域
    char ch;

    public ElemType() {
    }
    public ElemType(char ch) {
        this.ch = ch;
    }
}
class Child{//孩子链表
    int child;
    Child next;
}

class CTNode{//孩子表示法 
    ElemType data;
    Child firstchild;
}

class CTree{//顺序存储结构  
    //链式结构需要在每个结点再添加一个next指针域
    CTNode[] data;  //数组
    int root;   //根结点位置
    int node_count; //总结点
}

二叉树Binary Tree

  • 特殊的树 一个结点最多只能有两个子树

  • 左右子树是有序的不可改变

  • 树中左右树严格区分即使只有一个树

五种基本形态：

空，只有一个根节点，根结点只有左子树，根结点只有右子树，根结点左右都有

斜树

所有结点只能有左或者右的二叉树称为斜树，左子树就是左斜，右子树就是右斜

满二叉树

在一棵二叉树中所有叶子结点都在同一层，所有分支结点度为2，这样二叉树称为满二叉树

同样深度情况下满二叉树节点数最多

完全二叉树

对一棵具有n个结点的二叉树按层编号，如果与满二叉树中编号完全对于，则这颗二叉树就是完全二叉树

满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树

叶结点只能出现在最下面2层

最下层的叶子结点一定都是向右连续的

如果完全二叉树中有结点度为1，则该结点只有左孩子，不存在右孩子而且还是最后一个结点的双亲

二叉树性质

由满二叉树可以推导

1层：1个结点 2^0 = 1

2层：2个结点 2^1 = 2

3层：4个结点 2^2 = 4

4层：8个鸡蛋 2^3 = 4

在二叉树中第i层至多有2^(i-1) 个结点

满二叉树

1层：1 2^1 -1

2层：2+1 2^2 - 1

3层：1+2+4 2^3 -1

4层：1+2+4+8 2^4 -1

深度为k的二叉树之多有(2^k) -1 个结点
n个结点的满二叉树深度为 log2(n+1)
完全二叉树 按结点层序编号对于任意一个i结点

  • i = 1, 则结点i是二叉树的根

  • 2i>max_node, 则无左孩子

  • 2i + 1> max_node，则无有孩子，否则就是右孩子

    image-20221124000004613

遍历二叉树

  • 前序遍历

前提：二叉树不为空

先访问根结点然后前序遍历左子树，在遍历右子树

上述遍历结果为:ABDHIEJCFG

中序：

并不是从根结点开始，中序遍历根结点左子树然后才是根结点最后是右子树

上述遍历结果为:HDIBJEAFCG

层序：

这个就是每层递增来就行了：ABCEDFGHIJ

后续：

先叶结点，然后左右子树最后访问根节点

上述遍历结构：HIDEJBFGCA