数据结构之树与二叉树

文章目录

• 树与二叉树
• • 1、前言
  • 2、树的基本概念
  • • 2.1、树的定义
    • 2.2、基本术语
    • 2.3、树的性质
    • 2.4、对应选择题
    • 2.5、对应综合题
  • 3、二叉树的概念
  • • 3.1、二叉树的定义及其主要特点
    • • 3.1.1、二叉树的定义
      • 3.1.2、特殊的二叉树
      • 3.1.3、二叉树的性质
    • 3.2、二叉树的存储结构
    • • 3.2.1、顺序存储结构
      • 3.2.2、链式存储结构
    • 3.3、对应选择题
    • 3.4、对应综合题
  • 4、二叉树的遍历
  • • 4.1、先序遍历（NLR）
    • 4.2、中序遍历（LNR）
    • 4.3、后序遍历（LRN）
    • 4.4、层序遍历
    • 4.5、深度优先遍历
    • 4.6、由遍历序列构造二叉树
    • 4.7、线索二叉树
    • 4.8、习题整理
    • • 4.8.1、代码部分
      • 4.8.2、对应选择题
  • 5、树、森林
  • • 5.1、树的存储结构
    • 5.2、树、森林与二叉树的转换
    • • 5.2.1、树 ---> 二叉树
      • 5.2.2、森林 ---> 二叉树
      • 5.2.3、二叉树 ---> 树
      • 5.2.4、二叉树 ---> 森林
    • 5.3、树和森林的遍历
    • 5.4、对应选择题
    • 5.5、对应综合题
  • 6、树与二叉树的应用
  • • 6.1、哈夫曼树
    • • 6.1.1、哈夫曼树的定义
      • 6.1.2、哈夫曼树的构造
      • 6.1.3、哈夫曼树编码
      • 6.1.4、代码实现
    • 6.2、并查集
    • • 6.2.1、并查集原理
      • 6.2.2、代码实现
    • 6.3、对应选择题
    • 6.4、对应综合题

树与二叉树 1、前言

对于与二叉树，首先需要了解以下四点：

• 树的基本概念
• 二叉树
  • 二叉树的定义及其主要特征；二叉树的顺序存储结构和链式存储结构；二叉树的遍历；线索二叉树的基本概念和构造。
• 树、森林
  • 树的存储结构；树和森林的遍历；森林与二叉树的转换。
• 数与二叉树的应用
  • 哈夫曼树和哈夫曼编码；并查集及其应用。

【知识框架】

---

2、树的基本概念 2.1、树的定义

 树是 n（n>=0）个结点的有限集。当 n=0 时，称为空树。在任意一棵非空树中应满足：

  1. 根节点必存在且唯一
  2. 当 n > 1时，其余结点可分为 m（m>0）个互不相交的有限集: T₁，T₂，… ，T_m，其中每个集合本身又是一棵被称为根的子树。

 显然，树是一种递归的数据结构。树是一种逻辑结构，也是一种分层结构，具有以下两个特点：

 1）树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱（类比线性表）
 2）树中所有结点可以有零个或多个后继。

 树适合于表示具有层次结构的数据。具有一对多、多对一的关系。n个结点的树有n-1条边。

2.2、基本术语

• 节点的度：一个节点含有的子树的个数（分了几个叉）称为该节点的度

• 树的度：一棵树中，最大的节点的度称为树的度

• 兄弟节点：具有相同父节点的节点互称为兄弟节点

• 堂兄弟节点：其父节点在同一层的节点互为堂兄弟

• 节点祖先：从根到该节点所经分支上的所有节点，除了此节点本身，其余节点均为此节点的祖先节点，（儿子->父亲->父亲的父亲->…->根）

• 子孙节点：以该节点为根的子树中的任一节点均为该节点的子孙节点

• 结点的层次：从树根开始定义，根节点为第一层。

• 节点的深度：是从根节点开始从顶向下逐层累加的，根的深度定为1

• 结点的高度：是从叶节点开始从底向上逐层累加的，所有叶节点的高度为1。树的高度（或深度）是树中节点的最大层数。

• 路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。

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

• 森林：由m（m>=0）棵互不相交的树的集合成为森林

• 有序树： 结点各子树从左至右有序，不能互换

• 无序树： 结点各子树可互换位置

2.3、树的性质

 注意：性质中的 m 叉树经常与度相结合，因为度就是节点分的叉数。与完全m叉树相结合来求最值问题。详见如下第三题。

---

2.4、对应选择题

01、对于一棵具有n个结点、度为4的树来说，（A)
A.树的高度至多是 n-3    C.第 i 层上至多有4 (i-1) 个结点
B.树的高度至多是 n-4    D.至少在某一层上正好有4个结点

解析：给出结点和度，问高度。高度最大时每层的结点数应尽可能少。又因为度为4，则必然至少有一个节点有四个孩子，则剩下的 n-4 个结点排成一串就行了，所以最大高度至多为n-4+1。树的度为4只能说明存在某结点正好（也最多）有4个孩子结点，D错误。

02、度为4、高度为 h 的树，（A）
A.至少有h+3个结点     B.至多有4h-1个结点
C.至多有4h个结点     D.至少有h+4个结点

解析：给出高度和度，问结点。结点最少需要满足（1）至少有一个节点有4个分支；（2）每层节点数尽可能少。所以A对。对于节点数最多，则应使每个非叶节点的度均为4，即为满树，最多为: 1+4+4²+…+ 4^h-1.

03、假定一棵度为3的树中，结点数为50，则其最小高度为（C）
A.3   B.4   C.5   D.6

解析：高度最小，应使每层的节点数最多，度为3，即为完全三叉树即可，再运用性质3即可得出答案。

2.5、对应综合题

01、含有 n 个结点的三叉树的最小高度是多少？

02、已知一棵度为m的树中，有n₁个度为1的结点，有n₂个度为2的结点，有n_m个度为m的结点，问该树有多少个叶子结点？

---

3、二叉树的概念 3.1、二叉树的定义及其主要特点 3.1.1、二叉树的定义

 与树相似，二叉树也以递归的形式定义。二叉树是n（n>=0）个结点的有限集合：
 (1) 或为空二叉树，即 n = 0。
 (2) 或由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树（二叉树的结点次序不是相对的，是确定的）。

 二叉树是有序树，左、右子树不能颠倒。（二叉树和度为 2 的有序树不等价）

  对于任意一棵二叉树，含有 n 个结点，则高度为[（log₂n）下取整 + 1 ] ~ n。

3.1.2、特殊的二叉树

（1）满二叉树。一棵高度为 h 且含有 2^h-1 个结点的二叉树称为满二叉树。可以对满二叉树按层序编号：约定编号从根结点（根结点编号为1)起，自上而下，自左向右。这样，每个结点对应一个编号，对编号为 i 的结点，若有双亲，则其双亲为（i / 2）下取整，若有左孩子，则左孩子为2i， 若有右孩子，则右孩子为2i+ 1。

（2）完全二叉树。

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

（4）平衡二叉树。树上任一结点的左子树和右子树的深度之差不超过1。

3.1.3、二叉树的性质

3.2、二叉树的存储结构 3.2.1、顺序存储结构

 依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适（就是开个数组存），树中结点的序号可以唯一地反映结点之间的逻辑关系，这样既能最大可能地节省存储空间，又能利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。对于一般的二叉树，最坏情况下，一个高度为 h 且只有 h 个结点的单支树却需要占据近 2^h-1 个存储单元，极大浪费空间。

3.2.2、链式存储结构

 由于顺序存储的空间利用率较低，因此二叉树一般都采用链式存储结构，用链表结点来存储二叉树中的每个结点。二叉链表至少包含3个域：数据域data，左指针域 lchild 和右指针域 rchild。而实际上在不同的应用中，还可以增加某些指针域，如增加指向父结点的指针后，变为三叉链表的存储结构。

typedef struct TreeNode{
    TElemType data;//数据域
    struct TreeNode *lchild,*rchild; // 左右孩子指针
    struct TreeNode *parent;
}TreeNode,*BiTree;

  对于二叉链表的重要结论：在含有n个结点的二叉链表中，含有 n + 1个空链域，利用这些空链域可得另一种链表结构-----线索链表。

3.3、对应选择题

 01、设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为【2h-1】

 解析：可采用特例法，举个例子试试。

 02、设二叉树有 2n 个结点，且 m < n，则不可能存在【C】的结点。

​ A. n 个度为0  B. 2m 个度为0  C. 2m 个度为1   D. 2m 个度为2

 03、一棵有 124 个叶子结点的完全二叉树，最多有【248】个结点。

 04、已知一棵完全二叉树的第 6 层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是【111】。

 05、若一棵完全二叉树有 768 个结点，则该二叉树中叶结点的个数是【384】

3.4、对应综合题

01、已知完全二叉树的第 9 层有 240 个结点，则整个完全二叉树有多少个结点？有多少个叶子结点？

02、一棵高度为 h 的满 m 叉树有如下性质：根结点所在层次为第 1 层，第 h 层上的结点都是
叶结点，其余各层上每个结点都有 m 棵非空子树，若按层次自顶向下，同一层自左向右，顺序从 1 开始对全部结点进行编号，试问：
1）各层的结点个数是多少？
2）编号为 i 的结点的双亲结点（若存在）的编号是多少？
3）编号为 i 的结点的第 k 个孩子结点（若存在）的编号是多少？
4）编号为 i 的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？

---

4、二叉树的遍历

Java参考博客：二叉树的遍历

4.1、先序遍历（NLR）

 先序遍历操作过程如下：
  若二叉树为空，则什么也不做，否则：
   1） 访问根结点
   2） 先序遍历左子树
   3） 先序遍历右子树
递归实现

void preOrder(TreeNode* root){
    if(root != NULL){
        cout << root->val << " ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

非递归实现

void preOrder(TreeNode* root){
    if(root == NULL) return;
    stack S;    // 初始化栈
    TreeNode* node = root; // 声明遍历指针
    while(node || !S.empty()){
    	if(node != NULL)}{  // 不断访问树的根节点，并且存储左子树（若存在的话）
       		cout << node->val << " ";   
 			S.push(node);
        	node = node->left;
    	}
    	else{ // 遇到空指针，访问栈顶指针指向的右子树结点
        	node = S.top()->right;
            S.pop();
    	}  
    }
}

4.2、中序遍历（LNR）

递归实现

void inOrder(TreeNode* root){
    if(root != NULL){
        inOrder(root->left);
        cout << root->val << " ";
        inOrder(root->right);
    }
}

非递归实现

void inOrder(TreeNode* root){
    if(root == NULL) return;
    stack S;
    TreeNode* node = root;
    while(node!=NULL || !S.empty()){
    	if(node != NULL)}{
    	     // cout << node->val << " ";  先序遍历：在push时访问结点值
 			 S.push(node);
        	 node = node->left;
    	}
    	else{
        	node = S.top();
            S.pop();
            cout << node->val << " ";   // 中序遍历：在弹出栈顶指针时访问
            node = node->right;
    	}  
    }
}

4.3、后序遍历（LRN）

递归实现

void postOrder(TreeNode* root){
    if(root != NULL){
        postOrder(root->left);
        postOrder(root->right);
        cout << root->val << " ";
    }
}

非递归实现

// 先访问左子树，然后访问右子树，再访问根节点
// 使用堆栈来存储结点指针,需要分清返回根结点时是左子树或者右子树
// 我们使用一个辅助指针r来指向最近访问的结点,借助这个指针来区分根节点是从左子树还是右子树返回的。 
void postOrder(TreeNode* root){
    // 初始化一个栈 S
    initStack(S);
    // 声明一个遍历指针 p
    TreeNode* p = root;
    // 声明一个空的辅助指针
    TreeNode* r = NULL;
    while(p ||! S.empty()){
        if(p){ // 非空结点，压栈
            push(S, p); // 压栈，走左子树
            p = p->left;
        }
        else{ // 空结点
            getTop(S, p);    // 取出栈顶结点赋值给p
            if(p->right && p->right != r){  // 存在右子树，并且未访问过
                p = p->right;   // 取右子树根结点，入栈
                push(S,  p);
                p = p->left;
            }
            else{  // 不存在右子树或者 已经访问完右子树
                pop(S, p);      // 弹出栈顶指针并赋值给p
                visit(p->val);  // 访问结点值
                r = p;          // 记录最近访问的结点
                p = NULL;       // 将p置为空
            }
        }
    }
}

4.4、层序遍历

void levelOrder(TreeNode* root){
    if(root == NULL) return;
    queue Q;
    Q.push(root);
    while(!Q.empty()){
        TreeNpde* node = Q.front();
        Q.pop();
        cout << node->val << " ";
        if(node->left != NULL)
            Q.push(node->left);
        if(node->right != NULL)
            Q.push(node->right);
    }
}

4.5、深度优先遍历

void depthOrder(TreeNode* root){
    if(root == NULL) return;
    stack S;
    S.push(root);
    while(!S.empty()){
       	TreeNode* node = S.pop();
       	cout << node->val << " ";
        if(node->left != NULL)
            S.push(node->left);
        if(node->right != NULL)
            S.push(node->right);
    }
}

4.6、由遍历序列构造二叉树

 （1）先序序列和中序序列可以唯一地确定一棵二叉树。
 在先序遍历序列中，第一个结点一定是二叉树的根结点；而在中序遍历中，根结点必然将中序序列分割成两个子序列，前一个子序列是根结点的左子树的中序序列，后一个子序列是根结点的右子树的中序序列．根据这两个子序列，在先序序列中找到对应的左子序列和右子序列。在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。如此递归地进行下去，便能唯一地确定这棵二又树。
 （2）后序序列和中序序列也可以唯一地确定一棵二叉树。
 因为后序序列的最后一个结点就如同先序序列的第一个结点，可以将中序序列分割成两个子序列，然后采用类似的方法递归地进行划分，进而得到一棵二叉树。
 （3）由二叉树的层序序列和中序序列也可以唯一地确定一棵二叉树。

4.7、线索二叉树

 关于线索二叉树限于篇幅可以参考如下几篇博客，讲解的很明白了。

1. 线索二叉树原理及前序、中序线索化（Java实现）
2. 理解线索二叉树

4.8、习题整理 4.8.1、代码部分

1. 二叉树的深度
2. 二叉树习题篇[java]
3. 平衡二叉树
4. 从前序与中序遍历序列构造二叉树
5. 从中序与后序遍历序列构造二叉树

4.8.2、对应选择题

01、线索二叉树是一种【C】结构。

A. 逻辑 B. 逻辑和存储 C. 物理 D. 线性
解析：线索二叉树本质是加上线索后的链表结构，它是二叉树在计算机内部的一种存储结构，所以是一种物理结构。

02、n 个节点的线索二叉树含有线索数【C】。

A. 2n  B. n - 1  C. n + 1  D. n

解析: n个节点的一棵树一共有 2n 个指针，原生就有 n - 1 个指针了，那么就剩下 n + 1 个指针没有利用，在描绘线索的时候会全部利用起来（第一个节点的前序和最后一个节点的后序会指向空值）。

03、在下列关于二叉树遍历的说法中，正确的是【C】。
A. 若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。
B. 若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。
C. 若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。
D. 若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。

04、在二叉树中有两个结点 m 和 n，若 m 是 n 的祖先，则使用【C】可以找到从 m 到 n 的路径。
A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历

05、在二叉树的前序序列、中序序列和后序序列中，所有叶子结点的先后顺序【B】。
A. 都不相同 B. 完全相同

C. 前序和中序相同，而与后序不同 D. 中序和后序相同，而与前序不同

解析：在三种遍历方式中，访问左右子树的先后顺序是不变的，只是访问根结点的顺序不同，因此叶子结点的先后顺序完全相同。

06、对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左、右孩子中，其左孩子的编号小于其右孩于的编号，可采用【C】次序的遍历实现编号。
A. 先序遍历  B. 中序遍历  C. 后序遍历  D. 层次遍历

解析：对每个顶点从 1 开始按序编号，要求结点编号大于其左、右孩子编号，并且左孩子编号小于右孩子编号。编号越大说明遍历顺序越靠后，因此，三者遍历顺序为先左子树、再右子树、后根结点，即后序遍历。

07、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是【B】。
A. 空或只有一个结点   B. 高度等于其结点数
C. 任一结点无左孩子   D. 任一结点无右孩子

08、先序序列为a，b，c，d 的不同二叉树的个数是【B】。

A. 13   B. 14   C. 15   D. 16

解析：根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前
序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。

因为前序序列和中序序列可以唯一地确定一棵二叉树，所以题意相当于“以序列a，b，c，d为入栈次序，则出栈序列的个数为？”，对于 n个不同元素进栈，出栈序列的个数为：

23、二叉树在线索化后，仍不能有效求解的问题是【D】。
A. 先序线索二叉树中求先序后继   B. 中序线索二叉树中求中序后继
C. 中序线索二叉树中求中序前驱   D. 后序线索二叉树中求后序后继

31、若 X 是后序线索二叉树中的叶结点，且 X 存在左兄弟结点 Y，则 X 的右线索指向的是【A】。

A. X 的父结点        B. 以 Y 为根的子树的最左下结点
C. X 的左兄弟结点Y     D. 以 Y 为根的子树的最右下结点

---

5、树、森林 5.1、树的存储结构

 双亲表示法、孩子表示法、孩子兄弟表示法。
详情可参考该篇博客，写的很详细：树的三种存储结构

5.2、树、森林与二叉树的转换 5.2.1、树 —> 二叉树

树转换成二叉树的步骤如下：
（1）加线。就是在所有兄弟结点之间加一条连线；
（2）抹线。就是对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线；
（3）旋转。就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。

5.2.2、森林 —> 二叉树

森林是由若干棵树组成，可以将森林中的每棵树的根结点看作是兄弟，由于每棵树都可以转换为二叉树，所以森林也可以转换为二叉树。

将森林转换为二叉树的步骤是：
（1）先把每棵树转换为二叉树；
（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。

5.2.3、二叉树 —> 树

二叉树转换为树是树转换为二叉树的逆过程，其步骤是：
（1）若某结点的左孩子结点存在，将左孩子结点的右孩子结点、右孩子结点的右孩子结点……都作为该结点的孩子结点，将该结点与这些右孩子结点用线连接起来；
（2）删除原二叉树中所有结点与其右孩子结点的连线；
（3）整理（1）和（2）两步得到的树，使之结构层次分明。

5.2.4、二叉树 —> 森林

二叉树转换为森林比较简单，其步骤如下：
（1）先把每个结点与右孩子结点的连线删除，得到分离的二叉树；
（2）把分离后的每棵二叉树转换为树；
（3）整理第（2）步得到的树，使之规范，这样得到森林。

5.3、树和森林的遍历

 （1）树的遍历是指用某种方式访问树中的每个结点，且仅访问一次。主要有两种方式：
  a) 先根遍历。b）后根遍历

 （2）森林的遍历主要有两种方式：
  a) 先序遍历森林。b）中序遍历森林

    树和森林的遍历与二叉树遍历的对应关系

树	森林	二叉树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历

5.4、对应选择题

01、设 F 是一个森林，B 是由 F 变换来的二叉树。若 F 中有 n 个非终端结点，则 B 中右指针域为空的结点有【 n + 1】个。

02、设 X 是树 T 中的一个非根结点，B 是 T 所对应的二叉树。在 B 中，X 是其双亲结点的右孩子，下列结论中正确的是【D】。
A. 在树 T 中，X 是其双亲结点的第一个孩子
B. 在树 T 中，X 一定无右边兄弟
C. 在树 T 中，X 一定是叶子结点
D. 在树 T 中，X 一定有左边兄弟

03、将森林转换为对应的二叉树，若在二叉树中，结点 u 是结点 v 的父结点的父结点，则在原来的森林中，u 和 v 可能具有的关系是【B】。
I. 父子关系 II. 兄弟关系 III. u 的父结点与 v 的父结点是兄弟关系
A. 只有II B. I和II C. I和III D. I,II和III

04、已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是【1896】。

05、将森林 F 转换为对应的二叉树，F 中叶结点的个数等于【C】。
A. T 中叶结点的个数 B. T 中度为 1 的结点个数
C. T 中左孩子指针为空的结点个数 D. T 中右孩子指针为空的结点个数

解析：在二叉树中，节点的左指针指向其孩子，节点的右指针指向其兄弟。所以在一颗二叉树中，如果某个节点的左指针为NULL，就说明这个节点在原来的森林中没有孩子，是叶结点，如果某个节点的右指针为NULL，就说明这个节点在原来的森林中没有兄弟。

所以森林中的叶结点数 = 二叉树中左指针为NULL的个数。

06、若森林 F 有 15 条边、25 个结点，则 F 包含树的个数是【10】。

解析： 树有一个很重要的性质，即在 n 个结点的树中有 n - 1 条边，那么对于每棵树，其结点数比边数多1。题中的森林中的结点数比边数多 10（即25-15=10),显然共有10棵树。

5.5、对应综合题

01、编程求以孩子兄弟表示法存储的森林的叶子结点数。

 当森林（树）以孩子兄弟表示法存储时，若结点没有孩子(fch=null)，则它必是叶子，总的叶子结点个数是孩子子树(fch)上的叶子数和兄弟子树(nsib)上的叶结点个数之和。
算法代码如下：

typedef struce node{
    ElemType data;  // 数据域
    struct node *fch,*nsib;  // 孩子与兄弟域
}*Tree；

// 计算以孩子兄弟表示法存储的森林的叶子数
int Leaves(Tree t){
    if(t == NULL) return 0; // 树空返回0
    if(t—>fch==NULL)        // 若结点无孩了，则该结点必是叶子
        return 1+Leaves(t->nsib);//返回叶子结点和其兄弟子树中的叶子结点数
								  //孩子子树和兄弟子树中叶子数之和
    else
        return Leaves(t—>fch) + Leaves(t—>nsib)
}

02、以孩子兄弟链表为存储结构，请设计递归算法求树的深度。

  由孩子兄弟链表表示的树，求高度的算法思想如下：采用递归算法，若树为空，高度为零；否则，高度为第一子女树高度加 1 和兄弟子树高度的大者。其非递归算法使用队列，逐层遍历树，取得树的高度。算法代码如下，

int Height(CSTree(t){
	//递归求以孩子兄弟链表表示的树的深度
	int hc，h5;
    if(bt==NULL）
		return 0;
	else{	//否则，高度取子女高度 +1 和兄弟子树高度的大者
		hc=height(bt—>firstchild);   //第一子女树高
		hs=height(bt—>nextsibling);  //兄弟树高
		if(hc+l>hs)
			return hc+l;
		else 
            return hS;
    }
}

03、若一棵非空 k（k>=2）叉树 T 中的每个非叶结点都有 k 个孩子，则称 T 为正则 k 叉树。请回答下列问题并给出推导过程。
1）若 T 有 m 个非叶结点，则 T 中的叶结点有多少个？
2）若 T 的高度为 h （单结点的树 h = 1），则 T 的结点数最多为多少个？最少为多少个？

---

6、树与二叉树的应用 6.1、哈夫曼树 6.1.1、哈夫曼树的定义

 权 即树中结点被赋予的数值。从树的根到任意结点经过的边数与该结点上权值的乘积，称为该结点的带权路径长度。树中所有叶结点的带权路径长度之和称为该树的带权路径长度，记为：
W P L = ∑ i = 1 n w i l i WPL = sum_{i=1}^{n}{w_il_i} WPL=i=1∑n​wi​li​
式中，w_i 是第 i 个叶结点所带的权值，l_i 是该叶结点到根结点经过的边数。

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

6.1.2、哈夫曼树的构造

给定 n 个权值分别为 w₁，w₂，…，w_n的结点，构造哈夫曼树的算法描述如下：
1）将 n 个结点分别作为 n 棵仅含一个结点的二叉树，构成森林 F。
2）构造一个新结点，从 F 中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
3〉从 F 中删除刚才选出的两棵树，同时将新得到的树加入 F 中。
4）重复步骤 2）和 3), 直至 F 中只剩下一棵树为止。
从上述构造过程中可以看出哈夫曼树具有如下特点：
1）每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。
2）构造过程中共新建了 n - 1 个结点（双分支结点),因此哈夫曼树的结点总数为 2n - 1。
3）每次构造都选择 2 棵树作为新结点的孩子，因此哈夫曼树中不存在度为 1 的结点。

6.1.3、哈夫曼树编码

若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。

哈夫曼编码可解释为从根至该字符的路径上边标记的序列，其中边标记为0表示“转
向左孩子”，标记为1表示“转向右孩子”。

注意点：0 和 1 究竟是表示左子树还是右子树没有明确规定。构造出的哈夫曼树并不唯一，但各哈夫曼树的带权路径长度 WPL 相同且为最优。此外，如有若干权值相同的结点，则构造出的哈夫曼树更可能不同，但WPL必相同且是最优的。

6.1.4、代码实现

参考博客1：哈夫曼树及哈夫曼编码详解c++实现

参考博客2：Java编程内功-数据结构与算法「赫夫曼编码」

参考博客3：Huffman编码算法之Java实现

6.2、并查集 6.2.1、并查集原理

并查集是一种简单的集合表示，它支持以下3种操作：
 1）lnit（s）：将集合 S 中的每个元素都初始化为只有一个单元索的子集合。
 2）Union(s,Root1,Root2)：把集合s中的子集合Root2并入子集合Root1。要求Root1和Root2互不相交，否则不执行合并。
 3）Find(S,x)：查找集合 S 中单元素 x 所在的子集合，并返回该子集合的根结点。
通常用树（森林）的双亲表示法作为并查集的存储结构，每个子集合以一棵树表示。所有表示子集合的树，构成表示全集合的森林，存放在双亲表示数组内。通常用数组元素的下标代表元素名，用根结点的下标代表子集合名，根结点的双亲结点为负数。

6.2.2、代码实现

 之前看AcWing做了部分总结，参考另一篇博客：数据结构之并查集

6.3、对应选择题

01、若度为 m 的哈夫曼树中，叶子结点个数为 n，则非叶子结点的个数为【C】。

A. n-1    B. ⌊ n / m ⌋ lfloor n / m rfloor ⌊n/m⌋ -1   C. ⌈ ( n − 1 ) / ( m − 1 ) ⌉ lceil (n-1)/(m-1)rceil ⌈(n−1)/(m−1)⌉   D. ⌈ n / ( m − 1 ) ⌉ lceil n/(m-1)rceil ⌈n/(m−1)⌉ -1

解析：一棵度为 m 的哈夫曼树应只有度为 0 和 m 的结点，设度为 m 的结点有n_m个，度为 0 的结点有n₀个，又设结点总数为 n，n = n₀+n_m。因为 n 个结点的哈夫曼树有 n-1 条分支，则由 分支总数 = n - 1 = n₀ + n₁ + 2n₂ 得 mn_m = n - 1 = n₀+n_m-1

02、下列选项给出的是从根分别到达两个叶结点路径上的权值序列，属于同一棵哈夫曼树的是【D】。
A. 24，10，5 和 24，10，7 B. 24，10，5 和 24，12，7
C. 24，10，10 和 24，14，11 D. 24，10，5 和 24，14，6

解析：参考博客：哈弗曼树的路径问题

6.4、对应综合题

01、设有 6 个有序表 A，B，C，D，E，F，分别含有10，35，40，50，60和200个数据元素，各表中的元素按升序排列。要求通过 5 次两两合并，将6个表最终合并为 1 个升序表，并使最坏情况下比较的总次数达到最小。请回答下列问题：
1）给出完整的合并过程，并求出最坏情况下比较的总次数。
2）根据你的合并过程，描述 n（n >= 2）个不等长升序表的合并策略，并说明理由。

 由于最先合并的表中的元素在后续的每次合并中都会再次参与比较，因此求最小合并次数类似于求最小带权路径长度，此时可立即想到哈夫曼树。根据哈夫曼树的构造过程，每次选择表集合中长度最小的两个表进行合并。6个表的合并顺序如下图所示。

根据图中的哈夫曼树，6个序列的合并过程如下：

1. 在表集合{10，35，40，50，60，200}中，选择表A与表B合并，生成含45个元素的表AB。

02、若任意一个字符的编码都不是其他字符编码的前缀，则称这种编码具有前缀特性。现有某字符集（字符个数 >= 2）的不等长编码，每个字符的编码均为二进制的 0、1序列，最长为 L 位，且具有前缀特性。请回答下列问题：
1）哪种数据结构适宜保存上述具有前缀特性的不等长编码？
2）基于你所设计的数据结构，简述从0/1串到字符串的译码过程。
3）简述判定某字符集的不等长编码是否具有前缀特性的过程。

---