[项目010] 树的的综合应用 显示答案 | 返回首页
作者：欧新宇（Xinyu OU）
当前版本：Release v1.0
开发平台：gcc 13.1.0, g++ 13.1.0, gdb 13.2
运行环境：Intel Core i7-13700KF CPU 3.4GHz, 32GB RAM
本教案所涉及的数据及代码仅用于教学和交流使用，请勿用作商用。
最后更新：2023年11月15日
作业要求：将【课后作业】的题目及程序代码整理成实验报告，并以PDF格式，或直接拍照上传到【雨课堂】（不要使用word文档进行上传）。
【课后作业】
1. 将下面一个由三棵树组成的森林转换为二叉树。
🏷️Project01001A
2. 已知某二叉树的先序序列和中序序列分别为ABDEHCFIMGJKL和DBHEAIMFCGKLJ，请画出这棵二叉树，并画出二叉树对应的森林。
3. 设给定权集 w = {5,7,2,3,6,8,9}，试构造关于w的一棵哈夫曼树，并求其加权路径长度WPL。
4. 【2012统考真题】设有6个有序表A,B,C,D,E,F,分别含有10,35,40,50,60和200个数据元素，各表中的元素按升序排列。要求通过5次两两合并，将6个表最终合并为1个升序表，并使最坏情况下比较的总次数达到最小。请回答下列问题：
1) 给出完整的合并过程，并求出最坏情况下比较的总次数。
2) 根据你的合并过程，描述n(n≥2)个不等长升序表的合并策略，并说明理由。
5. 二叉树按二叉链表形式存储，试编写一个判别给定二叉树是否是完全二叉树的算法。
算法提示（设计思想）：
根据完全二叉树的定义，具有n个结点的完全二叉树与满二叉树的编号从1到n的结点一一对应。因此只需要在遍历结点的时候，判定第一个出现的空结点是否就是最后一个结点。具体实现思路如下：
1.采用层次遍历算法，将所有结点加入队列，包括空结点；
2.在进行入队的过程中，依次从队列中取出结点，并判定该结点是否为空结点。若当前结点为非空结点，则将其左、后子树分别加入队列；若为空结点，则继续判断该结点之后是否存在非空结点。若存在，则二叉树不是完全二叉树。
bool isCompleteTree(BiTree BT){
// 在此处填入代码
}
【选做题】[奖励分：0~1]
已知二叉树以二叉链表存储，编写算法完成：对于树中每个元素值为×的结点，删除以它为根的子树，并释放相应的空间。要求：
1) 给出算法的基本设计思想。
2) 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
算法提示（设计思想）：
- 本题要求删除值为x的结点，同时删除以它为根的子树，并释放空间。可以考虑使用基于二叉链的层次遍历方法来依次将每个结点输入到队列中。
- 在函数定义方面，可以考虑定义两个函数，一个用于删除以BT为根结点的子树，另一个用于遍历子树，并查找与元素值x相等的结点。
- 当某结点的元素值等于x时，就调用删除函数，将该结点的左、右子树都进行删除操作；若不等于则先后入队左、右子树。
// 1. 删除以bt为根的子树
void DeleteXTree(BiTree &BT){
// 在此处填入代码
}
// 2. 在二叉树上查找所有以x为元素值的结点，并删除以其为根的子树
void Search(BiTree BT, ElemType x){
// 在此处填入代码
}
【扩展练习】（不做考核要求）
1. 编程求以孩子兄弟表示法存储的森林的叶结点数。（只需要写主要功能函数）
算法提示（设计思想）：
当森林（树）以孩子兄弟表示法存储时，若结点没有孩子，则它必然是叶子结点；总的叶结点个数是孩子子树上的叶子数和兄弟子树上的叶结点数数之和。因此，可以递归地探测每一个结点，直至它成为没有孩子的叶子结点为止。
// 定义森林的基本数据结构
typedef struct node{
ElemType data;
struct node *lchild, *rightsibling;
}*Tree
int Leaves(Tree f){
// 在此处填入代码
}
2. 编写后序遍历二叉树的非递归算法。
算法提示（设计思想）：
二叉树的后序遍历所使用的线路与先序、中序是一样。但应注意的是，如果要将某个结点出栈，必须保证该结点的左右孩子已经出栈。具体操作如下：
1.将根压入堆栈，并立即执行输出；
2.从根开始访问左孩子，并将左孩子当作新子树的根，进行入栈，直到左孩子为空，退回到根结点，并输出根结点；
3.当退回到当前子树的根时，访问右孩子。若右孩子为空，则退回到当前子树的根，并将根结点出栈；
4.继续执行步骤3，若右孩子不空，则将右孩子当作新子树的根执行步骤2~3。
void PostOrder(BiTree T)
// 在此处填入代码
}
3.假设二叉树采用二叉链表存储结构，设计一个非递归算法求二叉树的高度。
算法提示（设计思想）：
- 考虑使用层次遍历算法，逐层将结点送入一个队列中进行遍历，当所有结点完成遍历后，输出当前层的编号。
- 设置一个全局参数level，用于记录当前结点所在的层；同时，设置一个last变量指向当前层的最后（最右）一个结点，每次进行层次遍历时均与last指针进行对比，若两者相等则将层数level+1，并使得last指向下一层的最后的结点，直到遍历完成。
- 当遍历某一层的时候，依次将当前访问结点的左、右孩子送入队列。在当前访问结点的队头元素进行出栈时，如果该队头元素等于last指针所指的元素，则它前一个元素的右孩子必定为下一层的最后一个元素。此时指向它的队尾指针即为下一层的最后一个结点。
int BTDepth(BiTree BT){
// 在此处填入代码
}
4. 假设二叉树采用二叉链存储结构存储，设计一个算法，求先序遍历序列中第k（1<k<二叉树中结点个数）个结点的值。
算法提示（设计思想）：
- 本题使用二叉树的递归遍历方法相对比较容易。考虑设置一个全局变量i，指向先序遍历时，当前访问的结点编号。
- 在遍历过程中，实时比较当前结点i和目标结点k的编号。当i等于k时，输出当前结点；当i不等于k时，按照先序遍历的规则，遍历二叉树；此外，当树为空时，输出特殊字符#
ElemType Find_KNode_Pre(BiTree BT, int k){
// 在此处填入代码
}
5.在二叉树中查找值为x的结点，试编写算法打印值为x的结点的所有祖先，假设值为x的结点不多于一个。
算法提示（设计思想）：
在树的遍历过程中，最简单的思路是利用非递归的后序遍历，这种方法最后访问根结点，这就意味着当访问值为x的结点时，栈中所有元素均为该结点的祖先。此时只需要依次出栈并输出栈顶元素即可。
// 1. 定义基本数据结构
typedef struct stack{
BiTree BT;
int tag; // tag=0 表示左子树被访问；tag=1表示右子树被访问
} //stack;
// 2. 在二叉树BT中，查找值为x的结点，并打印其所有祖先
void Search(BiTree bt, ElemType x){
}
6.写出在中序线索二叉树里查找指定结点在后序中的前驱结点的算法。
算法提示（设计思想）：
- 对于后序遍历来说，其访问顺序为左右根。因此，若结点p有右孩子，则右孩子是p的前驱；若结点p没有右孩子，但是有左孩子，则左孩子是结点p的前驱。
- 当结点p左、右孩子都不存在时，需要考察该结点在中序线索树中的前驱线索指针。假设存在结点f是p的祖先，根据中序遍历的规则左根右，若p是f的右孩子，并且f的左孩子存在，则p的前驱就指向f的左孩子；若p本身就是f的左孩子，则p的前驱就应该是f的双亲的左孩子，此时若f的双亲的左孩子存在，则该结点即为p的的前驱，若f的双亲的左孩子不存在，则需要一直顺着结点的双亲探测下去，直到找到第一个包含左孩子的结点，此时将该左孩子设置为结点p的前驱。
- 还有一种特殊情况，若p时中序遍历的第一个结点，即根结点的左孩子，或者唯一的根结点，则该结点没有前驱。
BiThrTree InPostPre(BiThrTree t, BiThrTree p){
// 在此处填入代码
}
7.【2014统考真题】二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T，采用二叉链表存储，结点结构为left|weight|right。其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，请设计求T的WPL的算法，要求：
1)给出算法的基本设计思想。
2)使用C或C++语言，给出二叉树结点的数据类型定义。
3)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
算法提示（设计思想）：
0. 求二叉树的带权路径长度WPL，实际上就是计算每个叶结点的深度与叶结点权值的积的累加。
- 使用先序遍历对树进行遍历，定义个静态变量static来统计wpl的值，同时将每个结点的深度作为递归函数的参数进行传递。
- 若结点是叶子结点，则变量wpl加上该结点的深度与权值之积；
- 若该结点是非叶结点，则左子树不为空时，对左子树调用递归算法，右子树不为空时，对右子树调用递归算法，深度参数为本结点的深度+1。
- 遍历结束后，返回wpl值。
typedef struct BiTNode{
// 在此处填入代码
}BiTNode, *BiTree;
bool WPL(BiTree root){
// 在此处填入代码
}