树

无根树

无根树是一个具有 $n$ 个结点, $n-1$ 条边的连通无向无环图。在无根树的基础上设定一个根节点，则形成一个有根树, 同时规定了树的结点的上下层关系。

关于树的定义:

森林(Forest): 每个连通分支为树的图结构。
生成树(Spanning tree): 基于一个连通无环无向图生成的树。生成的最小树称为最小生成树(Minimal Spanning Tree, MST)。
有序树与无序树: 如果兄弟节点的顺序是自左到右有次序的,则称为有序树,反之称为无序树。

关于有根树的定义:

父节点(Parent Node): 上一层结点,根节点没有父节点。
祖先(Ancestor): 从当前结点到根结点的除自身以外的所有结点。
子结点(Child Node): 下一层结点
结点深度(Depth): 从当前结点到根结点的图距离
树的深度(Height): 最深结点的结点深度
度(Degree): 不同于传统图论定义, 树的结点的度定义为连接的子结点个数
叶结点(Learf): 度为0的结点,同时是没有子结点的结点

树的存储结构

双亲表示法

双亲表示法使用一个顺序表存放树结点，每个结点由数据域与父结点的数组下标的"伪指针域"构成。

双亲表示法的存储结构为

struct PTNode{
    int data;
    int parent;
};
struct PTree{
    PTNode nodes[MAX_TREE_SIZE];
    int n;
};

双亲表示法寻找指定结点的父结点的时间复杂度和顺序表定位元素相同, 为 $\mathcal{O}(1)$ 。寻找指定结点的子结点的时间复杂度需要遍历整个顺序表，时间复杂度为 $\mathcal{O}(n)$ 。

孩子表示法

孩子表示法将所有结点存入一个顺序表，每个元素作为头结点，指向首元子结点指针，然后指向子结点的兄弟结点。

struct ChildPtr {
    int child;              
    ChildPtr* next;         
};
struct CTBox {
    int data;               
    ChildPtr* firstChild;   
};
struct CTree {
    CTBox<int> nodes[MAX_TREE_SIZE];
    int root;                      
    int numNodes;                  
};

孩子兄弟表示法

孩子兄弟表示法的每个结点有数据域、指向第一个孩子的指针与指向兄弟的指针，在每一层实现先向下后向右的指针移动方式。这个指针规则也成为左孩子-右兄弟原则

struct CSNode{
    int data;
    CSNode *firstchild;
    CSNode *nextsibling;
};

二叉树

二叉树是一种任何结点的度至多为 $2$ 的树。

二叉树的性质

性质1: 在二叉树的第 $i$ 层至多有 $2^{i-1}$ 个结点

Proof:

由归纳法，当 $i = 1$ 时，根结点个数为 $1$ 。假设当 $i= j-1$ 时，结点数至多为 $2^{j-2}$ , 则当 $i = j$ 时, 由于二叉树的结点度至多为 $2$ , 故第 $i$ 层的结点至多为 $2\times 2^{j-2} = 2^{j-1}$

性质2: 深度为 $k$ 的二叉树至多有 $2^{k}-1$ 个结点

Proof:

由性质1,总节点数至多为

$\sum_{i=1}^k 2^{i-1} = 2^k-1$

性质3: 对于任何一棵二叉树 $\mathcal{T}$ ，如果其叶结点数为 $n_0$ , 度为 $2$ 的结点数为 $n_2$ , 则 $n_0=n_2+1$

Proof:

二叉树由度为 $0,1,2$ 的结点构成，有

$n = n_0+n_1+n_2$

根据分支数计算总结点数, 每个度为 $2$ 的结点贡献 $2$ 个分支, 度为 $1$ 的结点贡献 $1$ 个分支, 最后加上根结点。

$n = 2n_2+n_1+1$

故

$n_0 = n_2+1$

性质4: $n$ 个结点的完全二叉树的深度为 $\left \lfloor \log_2n \right \rfloor +1$

Proof:

完全二叉树满足:

$2^{k-1}-1<n\leq 2^{k}-1$

即

$2^{k-1}\leq n < 2^k$

$k-1\leq \log_2 n < k$

因此

$k = \lfloor\log_2n\rfloor+1$

二叉树的存储结构

顺序存储结构

使用一维数组,按从上到下，从左到右的方式存储。对于完全二叉树,每一个节点都存入了元素,对于一般的二叉树, 存在节点需要存入Null或其他占位符。

链式存储结构

二叉树的链式存储结构分为

二叉链表
三叉链表

二叉链表为每个结点赋予左子指针与右子指针，用以指向下一个子结点。三叉链表的每一结点比二叉链表多一个前驱指针，用以实现类似于双向链表搜索前序元素的功能，

struct BTree{
    int data;
    BTree *LChild; 
    BTree *RChild;
    BTree *Parent; // 前驱指针
}

二叉树的应用

遍历二叉树

树的DFS有三种形式

先序遍历 -- 遵从从根结点到叶结点，从左到右的准则。
中序遍历 -- 遵从从左侧叶结点向右侧叶结点DFS，经过叶结点后返回分支的父结点，访问根结点后访问右子树的准则。
后序遍历 -- 遵从从左子树的叶结点后序遍历，经过根结点后后序遍历右子树。
也可以按照从上到下，从左到右的方式进行遍历。

// 递归法
void pre_order_recursive(BTree *root) {
    if (root == NULL) return;
    func(root);                    
    pre_order_traversal_recursive(root->LChild);
    pre_order_traversal_recursive(root->RChild); 
}
// 迭代法
void pre_order_traversal_iterative(BTree *root){
    if (root == NULL) return;
    BTree *curr = root;
    BTree *prev = NULL;
    while (curr!=NULL){
        if(prev == curr->Parent){
            func(curr);
            if (curr->LChild != NULL){
                prev = curr;
                curr = curr->LChild;
            }
            else if (curr->RChild != NULL){
                prev = curr;
                curr = curr->RChild;
            }
            else{
                prev = curr;
                curr = curr->Parent;
            }
        }
        else if (prev == curr->LChild){
            if (curr->RChild != NULL){
                prev = curr;
                curr = curr->RChild;
            } 
            else{
                prev = curr;
                curr = curr->Parent;
            }
        }
        else{
            prev = curr;
            curr = curr->Parent;
        }
    }
}

线索二叉树

线索二叉树的单个结点含有五个对象

$\text{node = [LChild,LTag,data,RTag,RChild]}$

LChild/RChild作为指向子结点的指针还是前驱指针依赖于LTag/RTag的值, LTag/RTag称为二叉树的线索

森林

树、二叉树与森林的转换

树与二叉树的转换

遵循 左孩子右兄弟原则。树转换为二叉树将右侧兄弟接在右子树。

在树转换为二叉树的情况下，因为根结点没有兄弟结点，所以转换的二叉树没有右子树，

森林与二叉树的转换

将森林的每一棵树都转换为二叉树后，将后一个二叉树的根结点拼接在前一个二叉树的右子结点上，以此类推形成完整的二叉树。

二叉树转换为森林

和森林转换为二叉树的原则相对应。将二叉树的右子树拆解为新二叉树，新二叉树的左子树与右子树分别构成子树，以此类推形成森林。

Huffman树

Huffman树的定义

带权路径长度WPL

定义每一个结点的权重为 $w_i$ , 距离根结点的图距离为 $l_i$ , 则带权路径长度定义为

$\mathrm{WPL} =\sum_{i=1}^n w_il_i$

加权平均长度定义为

$\bar{L} =\frac{\mathrm{WPL}}{\sum_{i=1}^n w_i}$

称在含有 $n$ 个带权结点的二叉树中，具有最小 $\mathrm{WPL}$ 的二叉树为 哈夫曼(Huffman)树, 也称最优二叉树

Huffman树的构建

将权值最小的结点拼接为左右子树，作为一个整体结点再添加倒数第三大的结点作为左子树，以此原则遍历结点生成Huffman树

并查集

并查集是用于合并与查询集合元素的树结构工具。实现方式为树的双亲表示法。

并查集的操作

集合结构

原子元素的初始位置域为 $-1$ , 形成一个集合时，子结点元素指向父结点(代表元)，父结点的位置域存入集合元素的个数的相反数，子结点的位置域存入父结点的位置

集合并运算

，将并入的集合的代表元插入另外一个集合的代表元的子结点上，位置域存入那个集合的代表元的位置。

集合查找运算

沿着伪指针向上搜索根结点

数据结构算法图论

树