考研数据结构与算法（六）树与二叉树

一、树的概念和基础术语

1.1 定义

树是 $n ( n >= 0 )$ 个节点的有限集。当 $n = 0$ 时，称为空树。 在任意－非空树中应满足：

• ①有且仅有一个特定的称为根的结点
• ②当 $n > 1$ 时， 其余节点可分为 $m (m > 0)$个互不相交的 有限集 $T_1,T_2,T_3……,T_m$ ， 其中每个集合本身又是一颗树，并且称为根的子树。

显然，树的定义是递归的，即在树的定义中又用到了其自身，树是一种递归的数据结构。 树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

• 树的根结点没有前驱， 除根结点外的所有结点有且只有一个前驱
• 树中所有结点可以有零个或多个后继

从这个结构上来看的话，树是一个层级的结构，对于每一个非根节点而言，和上层只有一个结点关联，我们称这个上层结点为父节点 ，又由于根节点没有上层结点，那么我们会发现在 $n$ 个结点的树有且仅有 $n-1$ 条边

1.2 基础术语

对于一颗这样的树而言：

• 考虑结点 $K$ 。根 $A$ 到结点 $K$ 的唯一路径上的任意结点，称为结点 $K$ 的 祖先。 如结点 $B$ 是 结点 $K$ 的祖先，而结点 $K$ 是结点 $B$ 的子孙。路径上最接近结点 $K$ 的结点 $E$ 称为 $K$ 的双亲， 而 $K$ 为结点 $E$ 的孩子。根 $A$ 是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟，如结点 $K$ 和结点 $L$ 有相同的双亲 $E$ ， 即 $K$ 和 $L$ 为兄弟。
• 树中一个结点的孩子个数称为该结点的度， 树中结点的最大度数称为树的度。 如结点 $B$ 的 度为 $2$ ，结点 $D$ 的度为 $3$ ，树的度为 $3$ 。
• 度大于 $0$ 的结点称为 分支结点（又称非终端结点)； 度为 $0$ （没有子女结点）的结点称为 叶子结点（又称终端结点)。
• 结点的深度是从根结点开始自顶向下逐层累加的，结点的高度是从叶结点开始自底向上逐层累加的。树的高度（或深度）是树中结点的最大层数。 上图中树的高度为 $4$ 。
• 有序树和无序树。树中结点的各子树从左到右是有次序的，不能互换，称该树为有序树，否则称为无序树 。
• 路径和路径长度。 树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成 ，而路径长度是路径上所经过的边的个数。（注意：由于树中的分支是有向的，即从1又亲指向孩子，所以树中的路径是从上向下的， 同一双亲的两个孩子之间不存在路径）
• 森林是 $m (m>=0)$棵互不相交的树的集合。 森林的概念与树的概念十分相近，因为只要把树的根结点删去就成了森林。

1.3 树的性质

• 树中的结点数等于所有结点的度数加一
• 度为 $m$ 的树中第 $i$ 层上至多有 $m^{i-1}$ 个结点 $(i>=1)$
• 高度为 $h$ 的 $m$ 叉树至多有 $(m^h - 1 )/(m 一 1)$个结点。
• 具有 $n$ 个结点的 $m$ 叉树的最小高度为 $\left \lceil log_m(n(m-1)+1) \right \rceil$

小结：这一部分的考点应该会着重于围绕树的性质，比如第一条，给你某些度的结点数和总结点数，问你叶子节点的个数，类似，以及围绕其他性质可以衍生处更多问题

二、二叉树

2.1 二叉树定义

每一个结点至多只有两棵子树（即度小于等于 $2$ ），并且二叉树是一颗有序树，其子树有左右之分 ，同样的，节点数为 $0$ 的树为空树

二叉树的基本五种形态如下：

这里需要注意二叉树和度为 $2$ 的树的区别：

• ①度为 $2$ 的树至少有 $3$ 个结点，而二叉树可以为空
• ②度为 $2$ 的树没有左右次序的区分，而二叉树是一颗有序树有左右子树的区分

2.2 二叉树性质

在提性质前，先介绍两种特殊的二叉树：

2.2.1 满二叉树

简单理解一下，对于每一层的结点都塞满的树就是二叉树，比如说下图的就是高度为 $2、3$ 的满二叉树

不难发现一个点，一颗深度为 $k$ 且有 $2^k - 1$ 个结点的二叉树为满二叉树

2.2.2 完全二叉树

对于一颗高度为 $k \ (k>1)$ 的二叉树其 $k-1$ 层是一颗满二叉树，并且第 $k$ 层是按照从左到右依次插入的结点就为完全二叉树，很显然一颗满二叉树也是一颗完全二叉树，而一颗完全二叉树不一定是满二叉树，我们看几个完全二叉树的例子：

2.2.3 二叉排序树

递归定义：

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

2.2.4 平衡二叉树

树上任一结点的左子树和右子树的深度之差不超过 $1$ 的二叉树即为平衡二叉树

2.2.5 性质

• 非空二叉树上的叶子结点数等于度为 $2$ 的结点数加 $1$, 即 $n_0 = n_2 + 1$
• 非空二叉树上第 $k$ 层上至多有 $2^{k-1}$ 个结点
• 高度为 $h$ 的二叉树至多有 $2^n - 1$ 个结点
• 对于完全二叉树而言，如果根节点是从 $1$ 开始计算的话，我们能得到一个有用的信息，即如果通过顺序存储二叉树，那么对于某一个分支节点假设为第 $k$ 个元素，那么其左儿子结点位置为： $2k$ 其右儿子结点位置为： $2k+1$ 的

2.3 二叉树存储结构

2.3.1 顺序存储

通过一组连续的地址进行存储每个结点（就是数组存储），我们按照从上到下，从左到右的次序依次将对应的结点放在对应的位置，显然根节点放在第一个位置（假设从 $1$ 开始计算），那么他的左儿子就是第二个位置，右儿子就是第三个位置，那么是一颗完全二叉树的话，就可以直接使用顺序存储，通过结点的位置我们也能很快的定位到

2.3.2 链式存储

因为树的结构不确定，不一定会是完全二叉树那样，所以使用顺序存储可能会造成大量的空间浪费，比如最极端的情况就是二叉树退化成链，那么这个时候，每增加一层，都会浪费 $2^i - 1$ 个空间，于是为了提高空间利用率，我们还可以通过链式存储二叉树的每个结点，对于每新增一个结点我们只需要申请对于的空间，然后将他的父结点指向它即可。

很显然就能得到这个链式的结点形式：

struct Node {
    ElemType data;
    struct Node *lchild,*rchild;
};

2.4 遍历二叉树

对于一个二叉树而言，是由三个部分组成：根结点（ $N$ ），左子树（ $L$ ），右子树（ $R$ ），那么我们对这三部分的访问顺序进行变化就得到了最基础的三种序列访问方式，即先序遍历（ $NLR$ ），中序遍历（ $LNR$ ），后序遍历（ $LRN$ ）

2.4.1 先序遍历

字面意思，遍历方式：

1. 遍历根节点
2. 遍历左子树
3. 遍历右子树

不难得出递归代码：

void PreOrder(Node *root) {
    if(root) {
        visit(root);//访问根节点
        PreOrder(root->lchild);//访问左子树
        PreOrder(root->rchild);//访问右子树
    }
}

2.4.2 中序遍历

字面意思，遍历方式：

1. 遍历左子树
2. 遍历根节点
3. 遍历右子树

不难得出递归代码：

void InOrder(Node *root) {
    if(root) {
        InOrder(root->lchild);//访问左子树
        visit(root);//访问根节点
        InOrder(root->rchild);//访问右子树
    }
}

2.4.3 后序遍历

字面意思，遍历方式：

1. 遍历左子树
2. 遍历右子树
3. 遍历根节点

不难得出递归代码：

void PostOrder(Node *root) {
    if(root) {
        PostOrder(root->lchild);//访问左子树
        PostOrder(root->rchild);//访问右子树
        visit(root);//访问根节点
    }
}

2.4.4 递归转非递归

假设有这样的一颗二叉树：

递归其实也就是利用了栈，我们分析用栈模拟的中序遍历的过程：

• ①沿着根的左孩子，依次入栈，直到左孩子为空，说明己找到可以输出的结点，此时栈内元素依次为 $A、B、D$
• ②栈顶元索出栈并访问：若其右孩子为空，继续执行操作②，若其右孩子不空，将右子树转执行操作①

以上面的二叉树为例，我们可以得到栈的空间使用过程如下：

操作次序	栈内空间	下一步进行的操作
1	NULL	①
2	$A$	①
3	$A、B$	①
4	$A、B、D$	②
5	$A、B$	②
6	$A$	①
7	$A、E$	②
8	$A$	②
9	NULL	①
10	$C$	②
11	NULL

模拟上述步骤即可得到非递归写法：

void InOrder_With_No_Deep(Node *root) {
    stack<Node *> S;
    Node *p = root;
    while(p || !S.empty()) {
        if(p){
            S.push(p);
            p = p->lchild;
        } else {
            p = S.top();
            S.pop();
            visit(p);
            p = p->rchild;
        }
    }
}

先序遍历其实和中序遍历的递归方式是相似的，只需要将 visit() 函数放在前面即可，于是不难得到如下代码：

void PreOrder_With_No_Deep(Node *root) {
    stack<Node *> S;
    Node *p = root;
    while(p || !S.empty()) {
        if(p){
            visit(p);
            S.push(p);
            p = p->lchild;
        } else {
            p = S.top();
            S.pop();
            p = p->rchild;
        }
    }
}

对于后序遍历的递归写法要麻烦得多，还是结合上面的二叉树图来分析

• ①沿着根的左孩子，依次入栈， 直到左孩子为空。 此时栈内元素依次为 $A 、B 、D$
• ②读取栈顶元素： 若其右孩子不空且未被访问过，将右子树转执行①；否则，栈顶元素出栈并访问。

接下来的时间线如下：

栈顶 $D$ 的右孩子为空，出栈并访问 ，它是后序序列的第一个结点

栈顶 $B$ 的右孩子不空且未被访问过， $E$ 入栈

栈顶 $E$ 的左右孩子均为空， 出栈并访问

栈顶 $B$ 的右孩子不空但己被访问， $B$ 出栈并访问

栈顶 $A$ 的右孩子不为空且未被访问过， $C$ 入栈

栈顶 $C$ 的左右孩子均为空，出栈并访问

栈顶 $A$ 的右孩子不空但己被访问， $A$ 出栈并访问

由此得到后序序列 $DEBCA$

我们会发现和上面的先序、中序相比，多了一个是否被访问，这里只会发生在再次回到根节点，查看和右子树的关系的时候，也就是上一个访问的结点

所以我们可以有两种方式进行存储是否被访问

• 第一种使用哈希存储每一个被访问过的结点
• 第二种只需要记录上一个访问的结点

显然，第二种效率会更高，而且占用的资源更少，于是哦我们能得到如下代码：

void PostOrder_With_No_Deep(Node * root) {
    stack<Node *> S;
    Node *p = root;
    Node *last = NULL;
    while(p | !S.empty()) {
        if(p) {//一直往左下走
            S.push(p);
            p = p->lchild;
        } else {
            p = S.top();
            if(p->rchild && p->rchild != last) {
                p = rchild;//处理没访问过的右子树
            } else {
                visit(p);//访问结点
                last = p;//上一个访问的结点更新
                S.pop();//将当前访问的结点从栈中删除
                p = NULL;//重置P指针
            }
        }
    }
}

关于代码中第 $17$ 行重置P指针：每次出栈访问完一个结点就相当于遍历完以该结点为根的子树

2.4.5 层序遍历

层序遍历依靠队列的数据结构，不断从上往下将结点加入队列，操作流程如下：

• ①将根节点加入队列
• ②将队首元素出队，并且将队首结点的左右儿子（结点不为空的话）加入队列
• ③重复①、②的操作直到队列为空

这个出队的序列就是我们层序遍历的结果

void Level_Order(Node *root) {
    queue<Node *> que;
    que.push(root);
    while(!que.empty()) {
        Node *p = que.front();
        visit(p);
        que.pop();
        if(p->lchild) que.push(p->lchild);
        if(p->rchild) que.push(p->rchild);
    }
}

2.5 通过遍历序列构造二叉树

有的时候会给你两种不同遍历方式，然后让你构造出指定的二叉树

2.5.1 先序序列和中序序列构造二叉树

因为先序遍历的特点，序列中第一个元素一定是整个二叉树的根，那么我们在中序遍历中找到这个二叉树的根的位置，然后在中序遍历中二叉树的左边就是左子树，而右边就是右子树，然后我们在先序遍历中第二个位置就是左子树的根，于是我们在中序遍历中找到了左子树的根，然后由于我们知道了左子树大概占了多少位置，于是我们直接往后移动相同的位置就找了右子树的根，然后递归的重复上面的操作就能构建出整个二叉树的结构

参考例题：

题目链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

Solution ：

class Solution {
private:
    unordered_map<int, int> index;

public:
    TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return nullptr;
        }

        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = index[preorder[preorder_root]];

        // 先把根节点建立出来
        TreeNode* root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        // 构造哈希映射，帮助我们快速定位根节点
        for (int i = 0; i < n; ++i) {
            index[inorder[i]] = i;
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
};

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9/

2.5.2 中序序列和后序序列构造二叉树

中序+后序其实和先序+后序并没有太大差别，只不过我们定位根是从后往前定位了，也就是整个树的根在后序遍历的末尾位置，然后不断向前推进

参考例题：

题目链接：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

Solution：

class Solution {
    int post_idx;
    unordered_map<int, int> idx_map;
public:
    TreeNode* helper(int in_left, int in_right, vector<int>& inorder, vector<int>& postorder){
        // 如果这里没有节点构造二叉树了，就结束
        if (in_left > in_right) {
            return nullptr;
        }

        // 选择 post_idx 位置的元素作为当前子树根节点
        int root_val = postorder[post_idx];
        TreeNode* root = new TreeNode(root_val);

        // 根据 root 所在位置分成左右两棵子树
        int index = idx_map[root_val];

        // 下标减一
        post_idx--;
        // 构造右子树
        root->right = helper(index + 1, in_right, inorder, postorder);
        // 构造左子树
        root->left = helper(in_left, index - 1, inorder, postorder);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // 从后序遍历的最后一个元素开始
        post_idx = (int)postorder.size() - 1;

        // 建立（元素，下标）键值对的哈希表
        int idx = 0;
        for (auto& val : inorder) {
            idx_map[val] = idx++;
        }
        return helper(0, (int)inorder.size() - 1, inorder, postorder);
    }
};

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/solution/cong-zhong-xu-yu-hou-xu-bian-li-xu-lie-gou-zao-14/

2.5.3 先序序列和后序序列构造二叉树

先序遍历和后序遍历在有的时候不能唯一的确定一颗二叉树，因为先序和后续没有明确的规定左右子树和根节点的关系，所以你可以说这是左子树，你也可以说这是右子树，所以通过这两种遍历方式进行构造的话，需要人为的拟定左右子树的分界点

参考例题：

题目链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/

三、线索二叉树

3.1 概念

前面的遍历二叉树让树形结构变成了链式结构，在链式结构中，对于出了第一个和最后一个结点外的其他结点而言，每一个结点都有一个前驱和后继，又由于我们之前提到，在一个 $n$ 个结点的二叉树上有 $n+1$ 个空指针，那么我们通过这些空指针来存储链式结构中的前驱和后继的关系这就是线索二叉树，能加快查找结点的前驱和后继。

我们对之前定义的结点结构做出一点改变：

若结点有左子树，则其 $lchild$ 指向的是左儿子结点，否则 $lchild$ 指向的是其前驱结点，若结点有有儿子，则其 $rchild$ 指向的是其有儿子结点，否则指向的是其后继结点，为了避免混淆，我们新增两个标志域来区分，于是新的结点结构如下：

struct Node {
    ElemType data;
    struct Node *lchild, *rchild;
    int ltag,rtag;
};

3.2 中序线索二叉树构造

假设指针 pre 是上一次访问的结点，而指针 p 为当前访问的结点，即 pre 指针是 p 的前驱，在中序遍历过程中

• 检查 p 的左指针是否为空，若为空，则将 p 的左指针指向 pre
• 检查 pre 的右指针是否为空，若为空，则将 pre 的右指针指向 p

如下图所示：

于是得到递归代码：

void InThread(Node *p,Node *pre) {
    if(p) {
        InThread(p->lchild,p);
        if(!p->lchild) {//检查p指针
            p->lchild = pre;
            p->ltag = 1;
        }
        if(pre && pre->rchild == NULL) {//检查pre指针
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;
        InThread(p->rchild,pre);
    }
}

3.3 先序线索二叉树构造

假设给定如下二叉树：

先序序列为 $A、B 、C 、D 、F$，然后依次判断每个结点的左右链域， 如果为空则将其改造为线索。

• 结点 $A、 B$ 均有左右孩子

• 结点 $C$ 无左孩子，将左链域指向前驱 $B$ ，无右孩子，将右链域指向后继 $D$

• 结点 $D$ 无左孩子，将左链域指 向前驱 $C$，无右孩子，将右链域指向后继 $F$
• 结点 $F$ 无左孩子，将左链域指向前驱 D， 无右孩子， 也无后继故置空
• 得到的先序线索二叉树如下图

如何在先序线索二叉树中找结点的后继？

• 如果有左孩子，则左孩子就是其后继
• 如果无左孩子但有右孩子，则右孩子就是其后继
• 如果为叶结点，则右链域直接指示了结点的后继。

3.4 后序线索二叉树构造

还是使用上面先序线索二叉树的图

后序序列 为 $CDBFA$

• 结点 $A、B$ 都有左右儿子

• 结点 $C$ 无左孩子，也无前驱故置空，无右孩子，将右链域指向后继 D

• 结点 $D$ 无左孩子，将左链域指向前驱 $C$ ，无右孩子，将右链域指向后继 $B$
• 结点 $F$ 无左孩子，将左链域指向前驱 $B$ ，无右孩子，将右链域指向后继 $A$
• 得到的后序线索二叉树如下图

如何在后序线索二叉树中找结点的后继？

在后序线索二叉树中找结点的后继较为复杂，可分 3 种情况：

• ①若结点 $X$ 是二叉树的根， 则其后继为空
• ②若结点 $X$ 是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲结点
• ③若结点 $X$ 是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历列出的第一个结点。

四、树和森林

4.1 树的存储结构

4.1.1 双亲表示法

使用一组连续的空间来存储每个结点，对于每一个结点除了要保存的元素值外还有一个 parent 伪指针指向该结点的父结点，结构如下图：

代码结构：

struct Node {
    ElemType data;
    int parent;
};

使用这个方式存储优点显然是方便找到每个元素的父结点，缺点就是要求一个结点的孩子结点的时候，需要遍历整个树形结构，这个存储方式其实就是我们后面的 并查集

4.1.2 孩子表示法

将每个结点的子节点用单链表链接起来，比如一个 $n$ 个结点的树形结构就有 $n$ 个单链表，很显然这种方式寻找子结点很容易，而寻找双亲的操作需要遍历 $n$ 个结点中孩子链表指针域所指向的 $n$ 个孩子链表，结构如下图：

4.1.3 孩子兄弟表示法

孩子兄弟表示法又称 二又树表示法 ，即以二叉链表作为树的存储结构。

孩子兄弟表示法使每个结点包括三部分内容： 结点值、 指向结点第一个孩子结点的指针，及指向结点下一个兄弟结点的指针（沿此域可以找到结点的所有兄弟结点）

存储结构描述如下：

struct Node {
    ElemType data;
    struct Node *firstchild,*nextsibling;
};

4.2 树、森林与二叉树互相转换

4.2.1 树转化为二叉树

规则：每个结点左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟，这个规则又称“左孩子右兄弟”。由于根结点没有兄弟 ， 所以对应的二叉树没有右子树,，如下图所示

树转换成二叉树的画法：

• ①在兄弟结点之间加一连线
• ②对每个结点，只保留它与第一个 孩子的连线，而与其他孩子的连线全部抹掉
• ③以树根为轴心，顺时针旋转 45°

4.2.2 森林转化为二叉树

森林转化为二叉树和树转化二叉树类似

我们先将森林中每一颗树转化为二叉树

因为一颗从树转化为二叉树的根的右子树为空，所以我们把第一个二叉树的根当作整个森林的根，然后把第二颗二叉树的根当作第一颗树的右儿子，然后把第三颗二叉树的根当作第二颗的右儿子，然后以此类推，这样就将一个森林转化为一颗二叉树

森林转换成二叉树的画法：

• ①将森林中的每棵树转换成相应的二叉树
• ②每棵树的根也可视为兄弟关系，在每颗树的根之间加一根连线
• ③以第一棵树的根为轴心顺时针旋转 45°

4.2.3 二叉树转化为森林

规则：若二叉树非空，则二叉树的根及其左子树为第一棵树的二叉树形式，故将根的右链断开。 二叉树根的右子树又可视为一个由除第一棵树外的森林转换后的二叉树， 应用同样的方法，直到最后只剩一颗没有右子树的二叉树为止，最后再将每颗二叉树依次转换成树，就得到了原森林，如下图所示，二叉树转化为森林是唯一的

4.3 树和森林的遍历

4.3.1 树的先根遍历

若树非空 ，先的问根结点，再依次遍历根结点的每颗子树，遍历子树时仍遵循先根后子树的规则。其遍历序列与这颗树相应二叉树的先序序列相同。

4.3.2 树的后根遍历

若树非空，先依次遍历根结点的每颗子树，再出问根结点，遍历子树时仍遵循先子树后根的规则。其遍历序列与这颗树相应二叉树的中序序列相同

4.3.3 森林的先序遍历

若森林为非空，则按如下规则进行遍历 ：

• 询问森林中第一棵树的根结点
• 先序遍历第一棵树中根结点的子树森林
• 先序遍历除去第一棵树之后剩余的树构成的森林

4.3.4 森林的中序遍历

森林为非空时，技如下规则进行遍历

• 中序遍历森林中第一棵树的根结点的子树森林
• 出问第一棵树的根结点
• 中序遍历除去第一棵树之后剩余的树构成的森林

五、二叉排序树

5.1 定义

二叉排序树（也称二叉查找树）或者是一棵空树，或者是具有下列特性的二叉树：

• 若左子树非空，则左子树上所有结点的值均小于根结点的值。
• 若右子树非空， 则右子树上所有结点的值均大于根结点的值
• 左、右子树也分别是一棵二叉排序树。

5.2 查找操作

如果我们想查找某个值的元素是否存在在树中，我们可以从根节点的元素进行比较，然后我们将查找元素和根节点进行比较，如果根节点和查找元相等的话那么就找到了，如果查找元素比根节点大的话我们就往右子树走，否则往左子树走，直到找到了就返回找到的结点

Node *BST_Search(Node *root,ElemType key) {
    while(root != NULL && root->data != key) {
        if(root->data < key) root = root->rchild;
        else root = root->lchild;
    }
    return root;
}

5.3 插入操作

插入操作其实和查找类似，我们从根节点开始不断与之比较，最后找到一个空结点的位置，当然如果在查找的过程中找到了这个元素，那么说明插入失败，因为已经存在了

Node * Create_Node(ElemType key) {
    Node *p = (Node)malloc(sizeof(Node));
    p->data = key;
    p->lchild = p->rchild = NULL;
}

int BST_insert(Node *root,ElemType key) {
    if(!root) {//如果是根节点元素为空的话
        root = Create_Node(key);
        return 1;
    }
    if(root->data == key)
        return 0;//已经存在，插入失败
    else if(root->data < key) {//插入到右子树
        if(root->rchild == NULL) {
            Node *p = Create_Node(key);
            root->rchild = p;
            return 1;//成功插入
        } else {
            return BST_insert(root->rchild,key);
        }
    }
    else {//插入到左子树
        if(root->lchild == NULL) {
            Node *p = Create_Node(key);
            root->lchild = p;
            return 1;//成功插入
        } else {
            return BST_insert(root->lchild,key);
        }
    }
}

5.4 构造操作

不断将序列中的元素加入到二叉树即可

Node *Create_BST(Node *root,ElemType vec[],int n) {
    root = NULL;
    for(int i = 0;i < n; ++i) {
        BST_insert(root,vec[i]);
    }
    return root;
}

5.5 删除操作

关于删除操作因为考虑到删除的结点不一定都是叶结点，于是我们需要对删除的结点进行分类讨论：

• ①若被删除结点 $z$ 是叶结点，则直接删除，不会破坏二叉排序树的性质
• ②若结点 $z$ 只有一棵左子树或右子树，则让 $z$ 的子树成为 $z$ 父结点的子树，替代 $z$ 的位置
• ③若结点 $z$ 有左、右两棵子树， 则令 $z$ 的直接后继（或直接前驱）替代 $z$ ，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况

下图则是三种不同情况的删除操作绘图：

5.6 效率分析

效率取决于二叉树的高度。

最坏效率：二叉树退化成链，复杂度为 $O(N)$

一般效率：二叉树的左右子树高度差的绝对值不超过 $1$ ，这样的树其实就是后面提到的平衡二叉树，他的平均查找复杂度为 $O(log_2n)$

从查找过程看， 二叉排序树与二分查找相似。 就平均时间性能而言， 二叉排序树上的查找和二分查找差不多 。 但二分查找的判定树唯一，而二叉排序树的查找不唯一，相同的关键字其插入顺序不同可能生成不同的二叉排序树 ，如下图所示

六、哈夫曼树（最优二叉树）

6.1 哈夫曼树的定义

树中结点常常被赋予一个表示某种意义的数值，称为该结点的权。从树的根到任意结点的路径长度（经过的边数）与该结点上权值的乘积，称为该结点的带权路径长度。 树中所有叶结点的带权路径长度之和称为该树的带权路径长度，记为：

$$WPL \ = \sum_{i=1}^n W_iL_i$$

在含有 $n$ 个带权叶结点的二叉树中 ， 其中带权路径长度（ $WPL$ ） 最小的二叉树称为哈夫曼树、也称最优二又树。

例如下图中图 $C$ 的 $WPL$ 最小，并且恰好为哈夫曼树

6.2 哈夫曼树构造

构造其实是有一点贪心的思想，不断的将两个权值最低的集合合并为一棵树，具体的构造如下：

• ①将这 $n$ 个结点分别作为 $n$ 颗仅含一个结点的二叉树，构成森林 $F$
• ②构造一个新结点，从 $F$ 中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
• ③ 从 $F$ 中删除刚才选出的两棵树，同时将新得到的树加入 $F$ 中
• ④重复步骤②和③， 直至 $F$ 中只剩下一棵树为止

从上述构造过程中可以看出哈夫曼树具有如下特点：

• 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
• 构造过程中共新建了 $n - 1$ 个结点（双分支结点），因此哈夫曼树的结点总数为 $2n - 1$
• 每次构造都选择 $2$ 棵树作为新结点的孩子，因此哈夫曼树中不存在度为 $1$ 的结点

6.3 哈夫曼编码

简单点说，因为我们发现了真实有用的结点是哈夫曼树的叶结点，那么这其实就是一颗前缀树，我们将每一个叶结点当作一个编码元素的话，那么一颗叶子结点为 $n$ 的哈夫曼树就能编码出 $n$ 个字符

我们将哈夫曼树的每一个结点指向左子树的边定为 $0$ （也可以定为1），然后将指向右子树的边定义为 $1$ ，那么从根节点到叶子节点的这一条路径组成的 $01$ 字符串自然是不存在前缀歧义的，所以将字符转化为 $01$ 编码放在一起也不会有二义性，这就是哈夫曼编码

举个例子，我们将每一个字符出现的次数作为叶节点的权重，然后构建一颗哈夫曼树：

可以看到这颗哈夫曼树的 $WPL$ 为 $WPL = 1 ×45 + 3×( 13 + 12 + 16) + 4×(5 + 9) = 224$

此处的 $WPL$ 可视为最终编码得到二进制编码的长度， 共 $224$ 位。若采用 $3$ 位固定长度编码，则得到的二进制编码长度为 $300$ 位，因此哈夫曼编码共压缩了 $25\%$ 的数据。 利用哈夫曼树可以设计出总长度最短的二进制前缀编码。

七、平衡二叉树

可以参考我的另一篇博客 算法小讲堂之平衡二叉树|AVL树（超详细~）: https://acmer.blog.csdn.net/article/details/126641989

八、并查集

并查集其实是一个很简单的结构，能够让我们快速判断集合间的关系，并处理，这个可以查看我之前写的博客

传送门： https://acmer.blog.csdn.net/article/details/118559983

九、错题

9.1 选择题

树的路径长度是指树根到每个结点的路径长的总和，根到每个结点的路径长度的最大值应是树的高度减 $1$ 。 注意与哈夫曼树的带权路径长度相区别

• A：在二叉树中，若某个结点只有一个孩子，则这个孩子的左右次序是确定的；而在度为 $2$ 的有序树中，若某个结点只有一个孩子，则这个孩子就无须区分其左右次序
• B：仅当是完全二叉树时才有意义
• D：在二叉排序树中插入结点时，一定插入在叶结点的位置，故若先删除 分支结点 再插入，则会导致二叉排序树的重构， 其结果就不再相同

由二叉树的性质一可知 $n_0 = n_2 + 1$

$结点总数 \ ＝ \ 2_n = n_0+ n_1 + n_2 = n_1 + 2n_2 + 1$

则 $n_1 = 2(n - n_2)- 1$

所以 $n_1$ 为奇数，说明该二叉树中不可能有 $2m$ 个度为 $1$ 的结点。

可采用特殊值法求解。

如下图所示，对应的二叉树中仅有前 $115$ 个叶结点有右孩子结点，其余 $1896$ 个结点均无右孩子结点。

在后序遍历退回时访问根结点，就可以从下向上把从 $n$ 到 $m$ 的路径上的结点输出，若采用非递归的算法， 则当后序遍历出栈到 $n$ 时，栈中把从根到 $n$ 的父指针的路径上的结点都记忆下来， 也可以找到从 $m$ 到 $n$ 的路径。

前序序列为 $NLR$， 后序序列为 $LRN$ ，由于前序序列和后序序列刚好相反，故不可能存在一个结点同时有左右孩子，即二叉树的高度为 $4$ 。 $1$ 为根结点，由于根结点只能有左孩子（或右孩子），因此在中序序列中， $l$ 或在序列首或在序列尾， $A,B,C, D$ 皆满足要求。仅考虑以 $1$ 的孩子结点 $2$ 为根结点的子树，它也只能有左孩子（或右段子）， 因此在中序序列中 ， $2$ 或在序列首或在序列尾，$A,B,D$ 皆满足要求，故选 C

先序序列先父结点，接着左子树，然后右子树。 中序序列先左子树，接着父结点，然后右子树，递归进行。若所有非叶结点只有右子树，则先序序列和中序序列都是先父结点，然后右子树，递归进行，因此边项 B 正确。

二叉树是一种逻辑结构，但线索二叉树是加上线索后的链表结构，即它是二叉树在讨算机内部的一种存储结构，所以是一种物理结构。

$n$ 个结点共有链域指针 $2n$ 个，其中 ，除根结点外，每个结点都被一个指针指向

剩余的链域建立线索，共 $2n - (n - 1) = n + 1$个线索。

对左子树为空的二叉树进行先序线索化，根结点的左子树为空并且也没有前驱结点（先遍历根结点），先序遍历的最后一个元素为叶结点 ，左、 右子树均为空且有前驱无后继结点，故线索化后，树中空链域有 $2$ 个

后序线索二叉树不能有效解决求后序后继的问题。 如下图所示， 结点 $E$ 的右指针指向右孩子，而在后序序列中 $E$ 的后继结点为 $B$ ，在查找 $E$ 的后继时后序线索不能起到任何作用，只能按常规方法来查找

在二叉中序线索树中，某结点若有左孩子，则按照中序 “左根右”的顺序，该结点的前驱结点为左子树中最右的一个结点（注意 ，并不一定是最右叶子结点）

后序线索树遍历时，最后访问根结点，若从右孩子 $x$ 返回访问父结点，则由于结点 $x$ 的右孩子不一定为空（右指针无法指向其后继），因此通过指针可能无法遍历整棵树。

如下图所示，结点中的数字表示遍历的顺序，图（c）中结点 $6$ 的右指针指向其右孩子 $5$，而不指向其后序后继结点 $7$，因此后序遍历还需要栈的支持，而图（a）和图（b）均可遍历

根据后序线索二叉树的定义 ， $X$ 结点为叶子结点且有左兄弟，因此这个结点为右孩子结点，利用后序，遍历的方式可知 $X$ 结点的后序后继是其父结点， 即其右线索指向的是父结点。为了更加形象 ，在解题的过程中可以画出如下所示的草图

根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：

前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。

因为前序序列和中序序列可以唯一地确定一颗二叉树

所以题意相当于“以序列 $a, b , c, d$ 为入栈次序，则出栈序列的个数为？”

对于 n 个不同元素进枝，出栈序列的个数为 $\frac{1}{n+1}C_{2n}^n = 14$

将森林转化为二叉树相当于用孩子兄弟表示法来表示森林。在变化过程中，原森林某结点的第一个孩子结点作为它的左子树，它的兄弟作为它的右子树。森林中的叶结点由于没有孩子结点，转化为二叉树时，该结点就没有左结点，所以 $F$ 中叶结点的个数等于 $T$ 中左孩子指针为空的结点 个数，选 C。此题还可通过一些特例来排除 A、 B、 D 选项

在二叉排序树上查找时，先与根结点值进行比较， 若相同，则查找结束，否则根据比较结果，沿着左子树或右子树向下继续查找。 根据二叉排序树的定义，有 $左子树结点值 <=根结点值 <= 右子树结点值$。 $C$ 序列中， 比较 $911$ 关键字后，应转向其左子树比较 $240$ ， 左子树中不应出现比 $911$ 更大的数值，但 $240$ 竟有一个右孩子结点值为 $912$，所以不可能是正确的序列。

平衡二叉树结点数的边推公式为 $n_0 = 0, n_1 = 1 ，n_2＝ 2, n_h = 1 ＋ n_{h-1} + n_{h-2}$ 为平衡二叉树高度， $n_h$, 为构造此高度的平衡二叉树所需的最少结点数）。 通过边推公式可得 ， 构造 $5$ 层平衡二叉树至少需 $12$ 个结点，构造 $6$ 层至少需要 $20$ 个结点。

设 $n_h$ 表示高度为 $h$ 的平衡二叉树中含有的最少结点数，则有 $n_1 ＝ 1$ $n_2 = 2, n_h, = n_{h-1}+n_{h-1}+1$ ,由此可以求出 $n_5 = 12$ ,对应的 $AVL$ 如下图所示（当然不唯一）

一棵度为 $m$ 的哈夫曼树应只有度为 $0$ 和 $m$ 的结点，设度为 $m$ 的结点有 $n_m$ 个， 度为 $0$ 的结点有$n_0$ 个， 又设结点总数为 $n$ , $n = n0 + n_m$。因有 $n$ 个结点的哈夫曼树有 $n - 1$ 条分支

则 $mn_m= n - 1 = n_m + n_0 -1$ ， 整理得

$$（m - 1) n_m = n_0 - 1 \\ n_m = (n - 1 )/(m - 1 )$$

9.2 简答题

---

最后更新: 2022-09-18 09:51:05

评论