数据结构 | C 与 C++ 描述 | 五、树与二叉树



树

树是 n(n>=0) 个节点的有限集。n=0 时为空树。树是一种递归的数据结构，也作为逻辑结构，同时也是一种分层结构。树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。树的所有结点可以有零个或多个后继。

  1. 树中一个结点的孩子个数称为该结点的度，树中节点的最大度数称为数的度。度大于 0 的结点称为分支结点，度等于 0 的结点称为叶子结点。
  2. 结点的层次从根开始定义，根为第 1 层。节点的深度是从根结点开始自顶向下逐层累加的。结点的高度是从叶节点开始自底向上逐层累加的。
  3. 树中结点的各子树从左到右是有次序的，不能互换，称该树为有序树，否则为无序树。
  4. 树中两个结点之间的路径是由这两个节点之间所经过的结点序列构成的，路径长度是路径上所经过的边的个数。
  5. 森林是 m(m>=0) 棵互不相交的树的集合。

树的性质

  1. 树中的节点数等于所有结点的度数加 1
  2. 度为 m 的树中第 i 层上至多由 mⁱ⁻¹ 个结点(i>=1)
  3. 高度为 h 的 m 叉树至多有 (mᑋ-1)/(m-1) 个结点
  4. 具有 n 个结点的 m 叉树的最小高度为 ⌈logₘ(n(m-1)+1)⌉

二叉树

二叉树是另一种树形结构，其特点是每个接待你至多只有两棵子树（即二叉树中不存在度大于 2 的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。

满二叉树

一颗高度为 h，且含有 2ᑋ-1 个结点的二叉树称为满二叉树。

  1. 满二叉树的叶子结点都集中在二叉树的最下一层
  2. 除叶子结点之外的每个结点度数均为 2，不存在度为 1 的情况
  3. 对于编号为 i 的结点，若有双亲，则其双亲为 ⌊i/2⌋，若有左孩子，则左孩子为 2i，若有有孩子，则右孩子 2i+1

完全二叉树

高度为 h、有 n 个结点的二叉树，当且仅当其每个结点都与高度为 h 的满二叉树中编号为 1~n 的结点一一对应时，称为完全二叉树。

  1. 若 i<=⌊n/2⌋ ，则结点 i 为分支结点，否则为叶子结点
  2. 叶子结点只可能在层次最大的两层上出现
  3. 若有度为 1 的结点，则只可能有一个，且该结点只有左孩子而无右孩子
  4. 按层序编号后，一旦出现某结点 i 为叶子结点或只有左孩子，则编号大于 i 的结点均为叶子结点
  5. n 为奇数，则每个分支节点都有左孩子和右孩子；若 n 为偶数，则编号最大的分支结点（编号为n/2）只有左孩子，没有右孩子，其余分支结点左、右孩子都有。

二叉排序树

左子树上所有结点的关键字均小于根节点的关键字；右子树上的所有结点的关键字均大于根节点的关键字；左子树和右子树又各是一棵二叉排序树。

平衡二叉树

树上任一结点的左子树和右子树的深度之差不超过 1

二叉树的性质

  1. 非空二叉树上的结点总数可以通过两种计算方式算得：n=n₀+n₁+n₂（结点数）或 n=n₁+2n₂+1（分支数）
  2. 非空二叉树上的叶子节点数等于度为 2 的节点树加 1，即 n₀=n₂+1
  3. 非空二叉树上第 k 层上至多有 2ᵏ⁻¹ 个结点
  4. 高度为 h 的二叉树至多有 2ᑋ-1 个结点(h>=1)
  5. 当完全二叉树有 2k（偶数）个结点，则必有 n₁
  6. 具有 n(n>0) 个结点的完全二叉树的高度为 ⌈log₂(n+1)⌉ 或 ⌊log₂n⌋+1
    1) 高 h-1 层的满二叉树有 2ᑋ⁻¹-1 个结点，高 h 层的满二叉树有 2ᑋ-1 个结点，因此得到 n 的区间 (2ᑋ⁻¹-1, 2ᑋ-1]
    2) 根据高 h-1 层满二叉树结点数，可得知高 h 层的完全二叉树结点数至少 2ᑋ⁻¹，同样高 h+1 层的完全二叉树结点数至少 2ᑋ，因此得到 n 的区间 [2ᑋ⁻¹, 2ᑋ)

二叉树的存储结构

顺序存储

二叉树的顺序存储是指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。完全二叉树和满二叉树采用顺序存储比较合适，既可最大可能地节省存储空间，又能利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。

链式存储

一般的二叉树采用顺序存储的空间利用率较低。

1
2
3
4
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

二叉树的遍历

二叉树的遍历是指按某条搜索路径访问树中每个结点，使得每个节点均被访问一次，而且仅被访问一次。常见的遍历次序有先序（NLR）、中序（LNR）、后序（LRN），其中序指根节点在何时被访问。

  • 递归算法比较明了，非递归遍历一般借助栈实现。
  • 二叉树的先序、后序、层次遍历可以和中序遍历可以唯一地确定一棵二叉树，抛开中序遍历其他任意两个均不能确定唯一的二叉树

先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 递归
void PreOrder(BiTree T) {
    if(T != NULL) {
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

// 循环
void PreOrder2(BiTree T) {
    InitStack(S); BiTree p = T;
    while(p || !IsEmpty(S)) {
        if(p) {
            visit(p); Push(S, p); // 先访问结点，入栈，接着走左子树
            p = p->lchild;
        } else {
            Pop(S, p); // 等到左树走完了，开始弹出结点，访问右数，依次就为 NLR
            p = p->rchild;
        }
    }
}

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 递归
void InOrder(BiTree T) {
    if(T != NULL) {
        PreOrder(T->lchild);
        visit(T);
        PreOrder(T->rchild);
    }
}

// 循环
void InOrder2(BiTree T) {
    InitStack(S); BiTree p = T;
    while(p || !IsEmpty(S)) {
        if(p) {
            Push(S, p); // 走左子树，将结点逐一入栈
            p = p->lchild;
        } else {
            Pop(S, p); visit(p); // 等到左树遍历完了，再弹出栈顶结点，开始遍历该结点的右子树
            p = p->rchild;
        }
    }
}

后序遍历

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
32
// 递归
void PostOrder(BiTree T) {
    if(T != NULL) {
        PreOrder(T->lchild);
        PreOrder(T->rchild);
        visit(T);
    }
}

// 循环
void PostOrder2(BiTree T) {
    InitStack(S); BiTree p = T, r = NULL;
    while(p || !IsEmpty(S)) {
        if(p) {
            Push(S, p); // 走左子树，将结点逐一入栈
            p = p->lchild;
        } else {
            GetTop(S, p); // 左子树走到底，读取此时栈顶结点，检查其是否有右子树
            //有就继续往下遍历，没有就弹出并读取栈顶结点，用指针 r 记录该结点，重置 p 指针
            if(p->rchild && p->rchild != r) {
                p = p->rchild;
                Push(S, p); // 将右树根结点入栈
                p = p->lchild; // 继续走左子树，循环
            } else {
                pop(S, p);
                visit(p);
                r = p;
                p = NULL; // 当前 p 指向的结点没有右子树，那么读取 p 后退回上层结点
            }
        }
    }
}

层次遍历

层次遍历是按层对每层结点进行访问。层次遍历的实现需要借助一个队列，从根结点开始入队，再出队访问，读取下一层子节点，入队，再依次出队访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
void LevelOrder(BiTree T) {
    InitQueue(Q);
    BiTree p;
    EnQueue(Q, T); // 根节点入队
    while(!isEmpty(Q)) {
        DeQueue(Q, p);
        visit(p);
        if(p->lchild != NULL)
            EnQueue(Q, p->lchild); // 先左子树结点
        if(p->rchild != NULL)
            EnQueue(Q, p->rchild); // 再右子树结点
    }
}

线索二叉树

遍历二叉树是以一定规则将二叉树中的节点排列成一个线性序列，而传统二叉链表不能之间得到结点在遍历中的前驱和后继。对于一棵 n 个节点的二叉链表，其空指针有 n+1，因此利用空指针来指向结点的前驱与后继，加快查找的速度。给结点存储结点多加左右两个 tag 标记，令不空（指向左/右孩子结点）的指针 tag=0，用来做前驱后继线索的 tag=1

1
2
3
4
5
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
}ThreadNode, *ThreadTree;

中序线索二叉树

构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void InThread(ThreadTree p, ThreadTree &pre) {
  if(p != NULL) {
    InThread(p->lchild, pre);
    if(p->lchild == NULL) {
      p->child = pre;
      p->ltag = 1;
    }
    if(pre != NULL && pre->rchild == NULL) {
      pre->rchild =p;
      pre->rtag = 1;
    }
    pre = p;
    InThread(p->rchild, pre);
  }
}

遍历

1
2


先序线索二叉树

后序线索二叉树

树、森林

树的存储结构

  1. 双亲表示法
  • 采用一组连续空间来存储每个结点，同时在每个节点中增设一个尾指针，指示其双亲节点在数组中的位置。
  • 优点：可以很快得到每个结点的双亲结点
  • 缺点：求结点的孩子时需要遍历整个结构
1
2
3
4
5
6
7
8
9
10
11
#define MAX_TREE_SIZE 100

typedef struct{
  ElemType data;
  int parent;
}PTNode;

typedef struct{
  PTNode nodes[MAX_TREE_SIZE];
  int n;
}PTree;
  1. 孩子表示法
  • 将每个结点的孩子节点都用单链表链接起来形成一个线性结构，此时 n 个结点就有 n 个孩子链表（叶子节点的孩子链表为空表）
  • 优点：寻找子女操作非常直接
  • 缺点：寻找双亲操作需要遍历 n 个节点中孩子链表指针域所指向的 n 个孩子链表
  1. 孩子兄弟表示法★
  • 又称二叉树表示法。即以二叉链表作为树的存储结构，根节点的左结点为子结点，右结点为空；下一层结点的左结点为该结点最左边的子节点，右结点为该结点右边的兄弟结点。
  • 优点：方便的实现树转换为二叉树的操作，易于查找结点的孩子
  • 缺点：从当前结点找其双亲比较麻烦，可为每个结点增设一个parent指针指向父结点

树、森林与二叉树的转换

  1. 树转换成二叉树的规则：左孩子右兄弟
  2. 森林转换为二叉树的规则：先将森林中的每棵树都转换为二叉树，再将森林第二棵树作为第一棵树根的右子树，以此类推