一、树和森林的概念

树的基本术语

• 根(root)：一个只有直接后继，但没有直接前驱的结点。
• 根的子树：根以外的其他结点划分为$m(m\geq 0)$个互不相交的有限集合$T_1, T_2, \dots, T_m$，每个集合又是一棵树。
• 子女结点：若结点的子树非空，结点子树的根即为该结点的子女。
• 父结点：若结点有子女，该结点是子女双亲。
• 兄弟结点：同一结点的子女互称为兄弟。
• 度：结点的子女个数即为该结点的度；树中各个结点的度的最大值称为树的度。
• 叶结点：度为0的结点即为叶结点，亦称为终端结点。
• 分支结点：度不为0的结点即为分支结点，亦称为非叶结点。
• 祖先结点：某结点到根结点的路径上的各个结点都是该结点的祖先。
• 子孙结点：某结点的所有下属结点，都是该结点的子孙。
• 结点的层次：规定根结点在第一层，其子女结点的层次等于它的层次加一
• 深度：结点的深度即为结点的层次；离根最远结点的层次即为树的深度。
• 高度：规定叶结点的高度为1，其父结点的高度等于它的高度加一。
• 树的高度：等于根结点的高度，即根结点所有子女高度的最大值加一。
• 有序树：树中结点的各棵子树 $T_0, T_1, \dots$ 是有次序的，即为有序树。
• 无序树：树中结点的各棵子树之间的次序是不重要的，可以互相交换位置。
• 森林：森林是 $m(m \geq 0)$ 棵树的集合

二、二叉树

性质

1. 若二叉树的节点的层次从1开始，则在二叉树的第$i$层最多有$2^{i-1}$个结点。$(i \geq 1)$

2. 深度为k的二叉树最少有k个结点，最多有$2^k-1$个结点。

   二叉树的每层最少1个结点，最多$2^{i - 1}$个节点。

   对等比数列求和可得：$2^0 + 2^1 +\cdots + 2^{k-1} = 2^k - 1$

3. 对任何一棵二叉树，如果其叶结点有$n_0$个, 度为 $2$ 的非叶结点有$n_2$个, 则有 $n_0 = n_2 + 1$.

   若设度为1的节点有$n_1$个，总结点数为$n$，总边树为$e$，根据二叉树的定义：

   $$n = n_0 + n_1 + n_2 \quad e = 2n_2 + n_1 = n - 1.$$

   因此，有$2n_2 + n_1 = n_0 + n_1 + n_2 - 1 \Rightarrow n_2 = n_0 - 1$.

4. 具有$n(n\geq 0)$个结点的完全二叉树的深度为$\lceil \log_2(n+1)\rceil$

   设完全二叉树的深度为$k$，则有$2^{k-1} -1< n \leq 2^k -1$，

   变形成$2^{k-1} < n + 1 \leq 2^k$，取对数：$k - 1 < \log_2(n+1) \leq k$

   有$\lceil \log_2(n+1) \rceil = k$

5. 如果将一棵有$n$个结点的完全二叉树自顶向上，同一层自左向右连续给结点编号$1, 2, \dots, n$，则有以下关系：

   • 若$i = 1$，则$i$无父节点
   • 若$i > 1$，则$i$的父节点为$\lfloor \frac{i}{2} \rfloor$
   • 若$2 * i \leq n$，则$i$的左子女为$2*i$
   • 若$2*i + 1 \leq n$，则$i$的右子女为$2*i + 1$
   • 若$i$为奇数，且$i \neq 1$，则其左兄弟为$i-1$
   • 若$i$为偶数，且$i \neq n$，则其右兄弟为$i + 1$

6. 完全二叉树的总结点数与叶子结点数量的关系：$n_0 = \lceil \frac{n}{2} \rceil$.

   因为$n_0 + n_1 + n_2 = 100$，且$n_0 = n_2 + 1$.

   对于完全二叉树有$n_1 = 0 or 1$.

   因此$n_0 = \lceil \frac{n}{2} \rceil$.

定义

1. 满二叉树（FULL Binary Tree）：一颗深度为$k$且拥有$2^k-1$个结点的二叉树。

2. 完全二叉树（Complete Binary Tree）:一颗深度为$k$且除第$k$层外，其他各层$(1 \sim k- 1)$的结点数都达到了最大个数，第$k$层从右向左连续缺若干节点，这就是完全二叉树。

   度数为1的结点只有0或1个。

链表表示

1. 二叉链表

每个结点有3个数据成员，data域存储结点数据，left_child和right_child分别存放指向左右子女的指针。

2. 三叉链表

相比二叉链表，每个结点增加一个指向双亲的指针parent指向父母节点。

静态结构：

	data	parent	left_child	right_child
0	A	-1	1	-1
1	B	0	2	3
2	C	1	-1	-1
3	D	1	4	5
4	E	3	-1	-1
5	F	3	-1	-1

三、二叉树遍历

设访问根结点记作V，遍历根的左子树记作L，遍历根的右子树记作R。

可能得遍历次序有：

• 前序：VLR
• 中序：LVR
• 后序：LRV

中序遍历（Inorder Traversal）

框架：

• 若二叉树为空，则空操作；

• 否则

  • 中序遍历左子树（L）；
  • 访问根结点（V）;
  • 中序遍历右子树（R）。

代码实现：

InOrder(void (*visit)(BinTreeNode<T> *t)){
    stack<BinTreeNode<T>*> S;
    BinTreeNode<T> *p = t;
    do{
        while(p != nullptr){
            S.push(p);
            p = p->leftChild;
        }
        if(!S.empty()){
            visit(p);
            p = p.rightChild;
        }
    }while(p != nullptr || !S.empty())
}

前序遍历（Preorder Traversal）

框架：

• 若二叉树为空，则空操作；

• 否则

  • 访问根结点（V）；
  • 前序遍历左子树（L）；
  • 前序遍历右子树（R）。

代码实现

PreOrder(void (*visit)(BinTreeNode<T> *t)){
    stack<BinTreeNode<T>*> S;
    BinTreeNode<T> *p = t;
    S.push(nullptr);
    while(p != nullptr){
        visit(p);
        if(p->rightChild != nullptr)
            S.push(p->rightChild);
        if(p->leftChild != nullptr)
            p = p->leftChild;
        else S.pop(p);
    }
}

后序遍历（Postorder Traversal）

框架：

• 若二叉树为空，则空操作；

• 否则

  • 后序遍历左子树（L）；
  • 后序遍历右子树（R）；
  • 访问根节点（V）。

代码实现

struct stkNode{
    BinTreeNode<T> *ptr;
    enum tag {L,R};
    stkNode(BinTreeNode<T> *N = nullptr):
    	ptr(N), tag(L){}
};

PostOrder(void (*visit)(BinTreeNode<T> *t)){
    stack<stkNode> S;
    stkNode w;
    BintreeNode<T> *p = t;
    do{
        while(p != nullptr){
            w.ptr = p;
            w.tag = L;
            S.push(w);
            p = p->leftchild;
        }
		int continue1 = 1;
        while(continue1 && !S.empty()){
            w = S.top();
            S.pop();
           	p = w.ptr;
            switch(w.tag){
                case L:{
                    W.tag = R;
                    S.push(w);
                    continue1 = 0;
                    p = p->rightChild;
                    break;
                }
                case R:{
                    visit(p);
                    break;
                }
            }
        }
    }while(!S.empty());
}

层次序遍历

使用先进先出的一个队列

levelOrder(void (*visit)(BinTreeNode<T> *t)){
    if(t == nullptr) return;
    Queue<BinTreeNode<T>*> Q;
    BinTreeNode<T> *p = t;
   	visit(p);
    Q.push_(p);
    while(!Q.empty()){
		Q.DeQueue(p);
        if(p->leftChild != nullptr){
            visit(p->leftChild);
            Q.EnQueue(p.leftChild);
        }
        if(p->rightChild != nullptr){
            visit(p->rightChild);
            Q.EnQueue(p->rightChild);
        }
    }
}

四、线索化二叉树

通过事先处理，将某种遍历顺序下的前驱、后继关系记在树的存储结构中，以后就可以高效地找出某结点的前驱、后继。

中序化线索二叉树

1. 后继：

   • current->rtag == 1：后继为current->right_child
   • 后继为：当前结点右子树的中序下的第一个节点。

2. 前驱：

   • current->ltag == 1：前驱为current->left_child
   • 前驱为：当前结点左子树中序下的最后一个结点。

代码实现

createInThread(){
    ThreadNode *pre = nullptr;
    if(root != nullptr){
        createInThread(root, pre);
        pre->rightChild = nullptr;
        pre->rtag = 1;
    }
};
createInThread(ThreadNode* current, ThreadNode*& pre){	// pre一定要是指针引用
    if(current == nullptr) return;
    createInThread(current->leftChild, pre);
    
    if(current->leftChild == nullptr){
        current->leftChild = pre;
        current->ltag = 1;
    }
    if(pre != nullptr && pre->rightChild == nullptr){
        pre->rightChild = current;
        pre->rtag = 1;
    }
    pre = current;
    
    createInThread(current->rightChild, pre);
}

 

前序线索化二叉树

1. 后继

   • 如果ltag == 1，

     • 如果p->rightChild == nullptr，无后继
     • 如果p->rightChild != nullptr，后继为p->rightChild

   • 如果ltag != 1，则后继为current->leftChild

2. 前驱

   • 如果ltag == 1，则前驱为current->leftChild
   • 如果ltag == 0，则前驱需要向上回溯进行寻找

后续线索化二叉树

1. 后继

   • 如果rtag == 1，则后继为current->rightChild

   • 如果rtag == 0，令pre = current->parent。

     • 如果pre == nullptr，则当前节点是根节点
     • 否则，如果pre->rtag==1 || pre->rightChild == p，则后继为pre
     • 否则后继为pre的右子树中后序下第一个结点

2. 前驱

   • 如果ltag == 1，那么current->leftChild就是前驱
   • 否则，很难找。

五、树与森林

1. 树的存储表示

1. 广义表表示：

   $A(B(E, F),C, D(G))$

2. 双亲表示：

   按照树的层次次序进行存放，并且存它的parent

3. 子女链表表示：

   有序树必须自左向右链接各个子女结点。

4. 子女指针表示：

   在结点中存放指向每一个子女结点的指针。

   每个结点包含的指针个数相等，等于树的度。

5. 子女-兄弟表示：

   data. firstChild, nextSibling

2. 森林转化为二叉树的规则

1. 若$F$为空，即$n = 0$，则对应的二叉树$B$为空树

2. 若$F$不空，则

   • 二叉树$B$的根是$F$的一棵树$T_1$的根
   • 其左子树为$B(T_{11}, T_{12}, \cdots, T_{1m})$，其中，$T_{11}, T_{12}, \cdots, T_{1m}$是$T_1$的根的子树
   • 其右子树为$B(T_2, T_3, \cdots, T_n)$，其中，$T_2, T_3, \cdots, T_n$是除$T_1$外其他树构成的森林

3. 二叉树转化为森林的规则

1. 若$B$为空，则对应的森林$F$也为空

2. 如果$B$非空，则

   • $F$中第一棵树$T_1$的根为$B$的根
   • $T_1$的根的子树森林$\{T_{11}, T_{12},\cdots, T_{1m} \}$是由$B$的根的左子树$LB$转换而来的
   • $F$中除了$T_1$之外其余的树组成的森林$\{T_2, T_3, \cdots, T_n \}$是由$B$的根的右子树$RB$转换而来的森林

4.树的遍历

1. 深度优先

• 先根次序遍历

  • 先遍历根节点自身，再遍历它的所有孩子
  • 与对应二叉树表示的前序遍历结果相同

• 后根次序遍历

  • 先遍历它的所有孩子，再遍历根结点自身
  • 与对应二叉树表示的中序遍历结果相同

2. 广度优先遍历

template <class T>
void Tree<T>::
LevelOrder(void (*visit)(BinTreeNode<T> *t)){
    Queue<TreeNode<T>*>Q;
    TreeNode<T>*p;
    if(current != NULL){
        p = current;
        Q.EnQueue(current);
        while(!Q.IsEmpty()){
            Q.DeQueue(current);
            visit(current);
            current = current->firstChild;
        }
        while(current != nullptr){
            Q.EnQueue(current);
            current = current->nextSibling;
        }
    }
    current = p;
}

 

六、堆（Heap）

1. 定义

完全二叉树顺序表示

最小堆：

父节点小于任意一个子女结点：$K_i \leq K_{2i+1} and k_{i} \leq K_{2i + 2}$

最大堆：

父节点大于任意一个子女结点：$K_i \geq K_{2i+1} and K_i \geq K_{2i+2}$

2. 下标计算

堆存储在下标从$0$开始计数的一维数组中，因此在堆中给定下标为$i$的节点时

• 父节点为$\lfloor \frac{i - 1}{2} \rfloor$
• 左子女为$2i + 1$
• 右子女为$2i+2$

3. 调整算法（自上而下）

从最后一个分支结点开始调整

void siftDown(int start, int m){
   	// 从结点 start 开始到 m 为止，自上向下比较，如果子的值小于父节点的值，则关键码小饿的上浮，继续向下层比较
    int i = start, j = 2 * i + 1; // j指向 i 的左子女
    int temp = heap[i];
    while(j <= m){
        if(j < m && heap[j] > heap[j+1]) j++;	// 让j指向i最小的子女
        
        if(temp <= heap[j]) break;
        else{
            heap[i] = heap[j];
            i = j;
            j = 2 * j + 1;
        }
    }
    heap[i] = temp;
}

4. 最小堆的插入（自下而上）

每次插入都加到堆的最后，然后自下而上执行调整

bool Insert(const int& x){
	heap[currentSize] = x;
    siftUp(currentSize);
    currentSiz++;
    return true;
}
void siftUp(int start){
    int j = start, i = (j - 1) / 2;
    int temp = heap[j];
    while(j > 0){
        if(heap[i] <= temp) break;
        else{
            heap[j] = heap[i];
            j = i;
            i = (i - 1) / 2;
        }
    }
    heap[j] = temp;
}

5. 删除堆顶

把最后一个元素置于堆顶，然后自上而下地进行调整

七、Huffman 树

1. 路径长度

• 两个结点之间的路径长度$PL$是连接两结点的路径上的分支数
• 树的外部路径长度是各叶节点到根节点的路径长度之和$EPL$
• 树的内部路径长度是各非叶节点到根节点的路径长度之和$IPL$
• 树的路径长度：$PL = EPL + IPL$

$n$个结点的二叉树的路径长度不小于下述数列的前$n$项和：$PL = \sum_{i=1}^n \lfloor \log_2 i \rfloor$

完全二叉树或理想平衡树满足这个要求。

2. 带权路径长度

扩充二叉树的带权路径长度定义为数的各外节点到根的带权路径长度之和

3. Huffman 树

带权路径长度最小的扩充二叉树即为Huffman树。

可以用在压缩中