数据结构“树与二叉树”的学习

一些学习心得

树：包含n个结点的有限集

  • 有且仅有一个 root 结点
  • 除了 root 结点以外的其余结点可以分为许多的不相交的有限集，而这些有限集本身也是一棵树，因此可以称为 root 的子树。

    二叉树：一种特殊的树

  • 同样有且只有一个 root 结点
  • 但是不同于树，其每一个结点只有两个互不相交的子集，分别称为左子树和右子树（不能颠倒顺序），且左，右子树本身也属于二叉树。

    二叉树的性质

  • 二叉树的第 i 层最多有 $2^{i-1}$ 个结点
  • 深度为 k 的二叉树至多有 $2{i-2}$ 个结点
  • 任何一颗二叉树，叶子结点 $n_0$ 的个数等于度为 2 的结点 $n_2$ 个数 + 1。

    二叉树的两种特殊形态：

  • 满二叉树
  • 完全二叉树

满二叉树的特点

  • 每一层的结点数都是最大结点数，即 $2^{i-1}$ 个

    完全二叉树的特点

  • 首先对满二叉树的结点进行编号，以root结点开始，从上往下，从左往右。假设深度为 k d，有 n 个结点的二叉树，当且仅当其中每一个结点都与深度为 k 的满二叉树中的编号从 1 至 n 的结点一一对应使，才称为完全二叉树。

两种特殊二叉树的重要特性

  • 具有 n 个结点的完全二叉树的深度为 $\lfloor log_2n\rfloor$ +1。

  • 如果对一棵有 n 个结点的完全二叉树（ 其深度为 $\lfloor log_2n\rfloor$ +1 ）的结点按层序编号，则对任一结点 i（ $1\leq i \leq n$ ），有

    1. 如果 i = 1，则结点 i 是二叉树的根，无双亲；如果 $i>1$，则其双亲PARENT（i）是结点 $\lfloor i/2 \rfloor$。
    2. 如果 2i>n，则结点 i 无左孩子；否则其左孩子是结点 2i。
    3. 如果 2i+1>n，则结点 i 无右孩子；否则其右孩子是结点 2i+1。

      二叉树的存储结构

  • 顺序存储

  • 链式存储

    顺序存储

    1
    2
    3
    4
    #define MAXISIEZE 100;
    typedef TElemType SqBiTree[MAXSIZE];
    // TElemType 在实际编程中换成所需的类型
    SqBiTree bt;

  • 这种存储结构仅适用于完全二叉树，对于结点数很少的树来说是非常浪费存储空间的

链式存储

1
2
3
4
typedef struct BiTNode{
    TElemType data;
    struct BiTNode *lchild, *rchild;  // 用于指向前驱和后继
}BiTNode, *BiTree;
  • 在含有 n 个结点的二叉链表中有 n+1 个空链域
    1
    2
    n 个节点，每个结点 2 个指针域，共 2n 个指针域，
    用掉 n-1 个指针域，剩下 2n - ( n - 1 ) 个指针域。

遍历二叉树

二叉树遍历的关键在于递归思想。

规定先先左后右，分为三种情况：

  • 先（根）序遍历（DLR）
    1. 先访问根结点
    2. 先序遍历左子树
    3. 先序遍历右子树
  • 中（根）序遍历（LDR）
    1. 中序遍历左子树
    2. 访问根结点
    3. 中序遍历右子树
  • 后（根）序遍历（LRD）
    1. 后序遍历左子树
    2. 后续遍历右子树
    3. 访问根节点

例：中序遍历的递归算法

1
2
3
4
5
6
7
void InOrderTraverse(BiTree T) {
    if(T) {
        InOrderTraverse(T->lchild);
        std::cout<<T->data<<std::ends;
        InOrderTraverse(T->rchild);
    }
}

例：中序遍历的非递归算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void InOrderTraverse_N(BiTree T) {
    StackNode *S;
    BiTNode *p,*q;
    Initalize_Link(S);
    p = T;
    q = new BiTNode;
    while(p||S) { // S表示存储二叉树data的栈不为空
        if(p) {
            Push_Link(S, p->data);
            p = p->lchild;
        } else {
            Pop_Link(S, q->data);
            std::cout<<q->data;
            p=q->rchild;
        }
    }
}

无论是递归还是非递归算法，对于 n 个结点的二叉树，其时间复杂度均为O(n)，空间复杂度也为O(n)。

根据遍历序列确定二叉树

  • 中序遍历 + 先序遍历
  • 中序遍历 + 后序遍历

方法：先利用先(后)序序列，找到根结点。然后根据中序序列找到根节点的左，右子树，再在先序序列中取第二个结点（后序序列取倒数第二个结点），根据同样的方式，继续分割中序序列，一直递归直至完成。
注意：先序序列第一个结点就是根结点，后序序列最后一个结点是根结点。

例如：已知一棵二叉树的中序序列和后序序列分别是 BDCEAFHG 和 DECBHGFA，请画出这棵二叉树

  • 第一步：根据后续序列 DECBHGFA 的最后一个结点，可以得到根结点为 A 为根结点
  • 第二步：在中序序列中找到 根结点 A 两侧的左，右子树 E 和 F。此时中序序列被分成两部分 左子树部分 BDCE，和右子树部分 FHG。后序序列也被分成左，右子树两部分，DECB 和 HGF。
  • 第三步：先看左子树的中序序列 BDCE，得到这部分的根节点是 B（A已经考虑完了，不再考虑），左子树的中序序列 BDCE 表示 B 结点只有右子树，是 CDE。同理，按这种方法不断递归，就可以得到一棵完整的二叉树。

二叉树遍历算法的应用

先序遍历的顺序建立二叉链表

1
2
3
4
5
6
7
8
9
10
11
void CreateBiTree(BiTree &T) {
    char ch;
    std::cin>>ch;
    if(ch=='#') T=NULL;
    else {
        T = new BiTNode;
        T->data=ch;              // 输出根节点    
        CreateBiTree(T->lchild); // 递归创建左子树 
        CreateBiTree(T->rchild); // 递归创建右子树     
    }
}

中序遍历和后序遍历只需要改变最后三个语句的顺序即可

复制二叉树

1
2
3
4
5
6
7
8
9
10
11
void Copy(BiTree T, BiTree &NewT) {
    if(T==NULL) {
        NewT = NULL;
        return;
    } else {
        NewT = new BiTNode;
        NewT->data = T->data;
        Copy(T->lchild, NewT->lchild);
        Copy(T->rchild, NewT->rchild);
    }
}

计算二叉树的深度

1
2
3
4
5
6
7
8
9
10
11
12
//二叉树的深度等于左右子树深度较大的加 1
int Depth(BiTree T) {
    int m, n;
    m = n = 0;
    if(T==NULL) return 0;
    else {
        m = Depth(T->lchild);
        n = Depth(T->rchild);
        if(n>m) return(n+1);
        else return (m+1);
    }
}

统计二叉书的结点个数

1
2
3
4
5
// 二叉树的个数等于左右子树结点数 + 1。
int NodeCount(BiTree T) {
    if(T==NULL) return 0;
    else return NodeCount(T->lchild) + NodeCount(T->rchild) +1;
}