西南交通大学 报告仅供参考，请独立完成作业

数据结构树与二叉树.cpp

第3章 第2节 树及二叉树(C++版)-2021-02-17.pdf

１本程序在vc++6.0编译通过并能正常运行。 ２主界面 程序已经尽量做到操作简便了，用户只需要根据提示一步步进行操作就行了。 六思考和总结： 这个课程设计的各个基本操作大部分都在我的综合性实验中实现了，所以做这个主要攻克插入和删除这两个算法！其中插入在书本上已经有了，其中的右平衡算法虽然没有给出，但通过给出的左平衡算法很容易就可以写出右平衡算法。所以最终的点就在于删除算法的实现！做的过程中对插入算法进行了非常非常多次的尝试！花了非常多的时间，这其中很多时候是在对程序进行单步调试，运用了ＶＣ６。０的众多良好工具，也学到了很多它的许多好的调试手段。 其中删除算法中最难想到的一点是：在用叶子结点代替要删除的非叶子结点后，应该递归的运用删除算法去删除叶子结点！这就是整个算法的核心，其中很强烈得体会到的递归的强大，递归的最高境界（我暂时能看到的境界）！ 其它的都没什么了。选做的那两个算法很容易实现的： １合并两棵平衡二叉排序树：只需遍历其中的一棵，将它的每一个元素插入到另一棵即可。 ２拆分两棵平衡二叉排序树：只需以根结点为中心，左子树独立为一棵，右子树独立为一棵，最后将根插入到左子树或右子树即可。 BSTreeEmpty(BSTree T) 初始条件：平衡二叉排序树存在。 操作结果：若T为空平衡二叉排序树，则返回TRUE,否则FALSE. BSTreeDepth(BSTree T) 初始条件：平衡二叉排序树存在。 操作结果：返回T的深度。 LeafNum(BSTree T) 求叶子结点数，非递归中序遍历 NodeNum(BSTree T) 求结点数，非递归中序遍历 DestoryBSTree(BSTree *T) 后序遍历销毁平衡二叉排序树T R_Rotate(BSTree *p) 对以*p为根的平衡二叉排序树作右旋处理，处理之后p指向新的树根结点 即旋转处理之前的左子树的根结点 L_Rotate(BSTree *p) 对以*p为根的平衡二叉排序树作左旋处理，处理之后p指向新的树根结点， 即旋转处理之前的右子树的根结点 LeftBalance(BSTree *T) 对以指针Ｔ所指结点为根的平衡二叉排序树作左平衡旋转处理， 本算法结束时，指针Ｔ指向新的根结点 RightBalance(BSTree *T) 对以指针Ｔ所指结点为根的平衡二叉排序树作右平衡旋转处理， 本算法结束时，指针Ｔ指向新的根结点 Insert_AVL(BSTree *T, TElemType e, int *taller) 若在平衡的二叉排序树Ｔ中不存在和e有相同的关键字的结点， 则插入一个数据元素为e的新结点，并返回OK,否则返回ERROR. 若因插入而使二叉排序树失去平衡，则作平衡旋转处理 布尔变量taller反映Ｔ长高与否 InOrderTraverse(BSTree T) 递归中序遍历输出平衡二叉排序树 SearchBST(BSTree T, TElemType e, BSTree *f, BSTree *p) 在根指针Ｔ所指的平衡二叉排序树中递归的查找其元素值等于e的数据元素， 若查找成功，则指针p指向该数据元素结点，并返回TRUE，否则指针p 指向查找路径上访问的最后一个结点并返回FALSE，指针f指向Ｔ的双亲， 其初始调用值为NULL Delete_AVL(BSTree *T, TElemType e, int *shorter) 在平衡二叉排序树中删除元素值为e的结点,成功返回OK,失败返回ERROR PrintBSTree_GList(BSTree T) 以广义表形式打印出来 PrintBSTree_AoList(BSTree T, int length) 以凹入表形式打印,length初始值为0 Combine_Two_AVL(BSTree *T1, BSTree T2) 合并两棵平衡二叉排序树 Split_AVL(BSTree T, BSTree *T1, BSTree *T2) 拆分两棵平衡二叉树 } (2)存储结构的定义： typedef struct BSTNode { TElemType data; int bf; //结点的平衡因子 struct BSTNode *lchild, *rchild;//左.右孩子指针 }BSTNode, *BSTree;

广义表与森林相互转换，森林与二叉树相互转换，二叉树与遍历序列（先序/中序）相互转换，森林先根遍历和后根遍历

java语言实现的二叉树的各种操作(包括递归与非递归遍历二叉树,求二叉树的高度，节点总数，叶子节点等)

编写程序，用先序递归遍历法建立二叉树的二叉链表存储结构，然后输出其先序、中序、后序遍历第k个访问结点。二叉树结点数据类型建议选用字符类型且各结点数据域值互不相同；输出用结点数据域的字符表示；求第k个访问结点的三个子函数中，需使用函数返回值和引用型形参带回所求(即每种方式至少使用一次)。

1. 一棵二叉树的顺序存储情况如下： 树中，度为2的结点数为（ ）。 A．1 B．2 C．3 D．4 2. 一棵“完全二叉树”结点数为25，高度为（ ）。 A．4 B．5 C．6 D．不确定 3．下列说法中，（ ）是正确的。 A. 二叉树就是度为2的树 B. 二叉树中不存在度大于2的结点 C. 二叉树是有序树 D. 二叉树中每个结点的度均为2 4.一棵二叉树的前序遍历序列为ABCDEFG,它的中序遍历序列可能是（ ）。 A. CABDEFG B. BCDAEFG C. DACEFBG D. ADBCFEG 5．线索二叉树中的线索指的是（ ）。 A．左孩子 B.遍历 C.指针 D.标志 6. 建立线索二叉树的目的是（ ）。 A. 方便查找某结点的前驱或后继 B. 方便二叉树的插入与删除 C. 方便查找某结点的双亲 D. 使二叉树的遍历结果唯一 7. 有abc三个结点的右单枝二叉树的顺序存储结构应该用（ ）示意。 A. a b c B. a b ^ c C. a b ^ ^ c D. a ^ b ^ ^ ^ c 8. 一颗有2046个结点的完全二叉树的第10层上共有（ ）个结点。 A. 511 B. 512 C. 1023 D. 1024 9. 一棵完全二叉树一定是一棵（ ）。 A. 平衡二叉树 B. 二叉排序树 C. 堆 D. 哈夫曼树 10．某二叉树的中序遍历序列和后序遍历序列正好相反，则该二叉树一定是（ ）的二叉树。 A．空或只有一个结点 B．高度等于其结点数 C．任一结点无左孩子 D．任一结点无右孩子 11．一棵二叉树的顺序存储情况如下： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E 0 F 0 0 G H 0 0 0 X 结点D的左孩子结点为（ ）。 A．E B．C C．F D．没有 12．一棵“完全二叉树”结点数为25，高度为（ ）。 A．4 B．5 C．6 D．不确定 二、填空题（每空3分，共18分）。 1. 树的路径长度：是从树根到每个结点的路径长度之和。对结点数相同的树来说，路径长度最短的是 完全 二叉树。 2. 在有n个叶子结点的哈夫曼树中，总结点数是 2n-1 。 3. 在有n个结点的二叉链表中，值为非空的链域的个数为 n-1 。 4. 某二叉树的中序遍历序列和后序遍历序列正好相反，则该二叉树一定是 任一结点无左孩子 的二叉树。 5. 深度为 k 的二叉树最多有 个结点，最少有 k 个结点。 三、综合题（共58分）。 1. 假定字符集{a，b，c，d，e，f }中的字符在电码中出现的次数如下： 字符 a b c d e f 频度 9 12 20 23 15 5 构造一棵哈夫曼树（6分），给出每个字符的哈夫曼编码（4分），并计算哈夫曼树的加权路径长度WPL（2分）。 （符合WPL最小的均为哈夫曼树，答案不唯一） 哈夫曼编码: 2. 假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字符构成，它们在电文中出现的频率分别为{0.31,0.16,0.10,0.08,0.11,0.20,0.04}。要求： (1)为这7个字符设计哈夫曼树（6分）。 (2)据此哈夫曼树设计哈夫曼编码（4分）。 (3)假设电文的长度为100字符，使用哈夫曼编码比使用3位二进制数等长编码使电文总长压缩多少？（4分） (1) 为这7个字符设计哈夫曼树为（符合WPL最小的均为哈夫曼树，答案不唯一）： (2) 哈夫曼编码为： a:01;b:001;c:100;d:0001;e:101;f:11;g:0000 (3) 假设电文的长度为100字符，使用哈夫曼编码比使用3位二进制数等长编码使电文总长压缩多少？ 采用等长码，100个字符需要300位二进制数，采用哈夫曼编码发送这100个字符需要261二进制位，压缩了30

数据结构课程设计 二叉树的各种遍历算法及树与二叉树的转换程序及报告 可以按照树的形状输出

数据结构-树与二叉树算法汇总,考研面试等很多常见的题型.