下载文档原格式
HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY Array
数据结构
实验五二叉树基本操作的编程实现
【实验目的】
内容：二叉树基本操作的编程实现
要求：
二叉树基本操作的编程实现（2学时，验证型），掌握二叉树的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找等操作，存储结构主要采用顺序或链接结构。
也鼓励学生利用基本操作进行一些应用的程序设计。
【实验性质】
验证性实验（学时数：2H）
【实验内容】
以下的选题都可以作为本次实验的推荐题目
1.建立二叉树，并以前序遍历的方式将结点内容输出。
2.将一个表示二叉树的数组结构转换成链表结构。
3.将表达式二叉树方式存入数组，以递归方式建立表达式之二叉树状结构，再分别输出前序、中序
及后序遍历结果，并计算出表达式之结果。
【注意事项】
1.开发语言：使用C。
2.可以自己增加其他功能。
【实验分析、说明过程】
【思考问题】
【实验小结】 (总结本次实验的重难点及心得、体会、收获)
【附录-实验代码】。
二叉树结点计算公式二叉树结点的计算公式及解释1. 二叉树的节点个数•公式：N = 2^h - 1，其中 N 表示二叉树的节点个数，h 表示二叉树的高度。
•解释：二叉树的高度 h 可以通过树的层数来确定，根节点所在的层数为 1，依次往下递增。
每个节点都可以有两个子节点，所以二叉树的节点个数 N 可以通过计算 2 的 h 次方再减去 1 来得出。
例如：A/ \B C/ \ / \D E F G根据上面的二叉树来计算节点个数：h = 3，2^3 - 1 = 8 - 1 = 7所以，该二叉树的节点个数为 7。
2. 二叉树的叶子节点个数•公式：L = (N + 1) / 2，其中 L 表示二叉树的叶子节点个数，N 表示二叉树的节点个数。
•解释：在二叉树中，叶子节点是指没有子节点的节点。
根据二叉树的性质，每个节点最多有两个子节点，所以二叉树的叶子节点个数可以通过节点个数加 1 再除以 2 来计算。
例如：A/ \B C/ \ / \D E F G根据上面的二叉树来计算叶子节点个数：N = 7，(7 + 1) / 2 = 8 / 2 = 4所以，该二叉树的叶子节点个数为 4。
3. 二叉树的高度•公式：h = log2(N + 1)，其中 h 表示二叉树的高度，N 表示二叉树的节点个数。
•解释：由于二叉树中每个节点都可以有两个子节点，所以可以通过节点个数 N 加 1 后取对数以 2 为底的对数来计算二叉树的高度。
例如：A/ \B C/ \ / \D E F G根据上面的二叉树来计算高度：N = 7，log2(7 + 1) ≈ log2(8) ≈ 3所以，该二叉树的高度为 3。
以上就是关于二叉树结点的计算公式及解释。
通过这些公式，我们可以更方便地计算二叉树的相关属性，进而优化算法或者进行更深入的研究。
信息学奥赛培训之『树——二叉树』树——二叉树为何要重点研究二叉树？ 引 ： 为何要重点研究二叉树 ？ （1）二叉树的结构最简单，规律性最强； （2）可以证明，所有树都能转为唯一对应的二叉树，不失一般性。
一、二叉树基础1. 二叉树的定义 二叉树是一类非常重要的树形结构，它可以递归地定义如下： 二叉树 T 是有限个结点的集合，它或者是空集，或者由一个根结点以及分别称为左 子树和右子树的两棵互不相交的二叉树。
因此，二叉树的根可以有空的左子树或空的右子树，或者左、右子树均为空。
二叉树有 5 种基本形态，如图 1 所示。
图1 二叉树的 5 种基本形态在二叉树中，每个结点至多有两个儿子，并且有左、右之分。
因此任一结点的儿子 不外 4 种情况：没有儿子；只有一个左儿子；只有一个右儿子；有一个左儿子并且有一 个右儿子。
注意：二叉树与树和有序树 的区别 二叉树与度数不超过 2 的树不同，与度数不超过 2 的有序树也不同。
在有序树中，11如果将树中结点的各子树看成从左至右是有次序的，则称该树为有序树，否则称为无序树。
-1-信息学奥赛培训之『树——二叉树』虽然一个结点的儿子之间是有左右次序的，但若该结点只有一个儿子时，就无须区分其 左右次序。
而在二叉树中，即使是一个儿子也有左右之分。
例如图 2-1 中(a)和(b)是两棵 不同的二叉树。
虽然它们与图 2-2 中的普通树(作为无序树或有序树)很相似，但它们却 不能等同于这棵普通的树。
若将这 3 棵树均看作是有序树，则它们就是相同的了。
图2-1 两棵不同的二叉树图2-2 一棵普通的树由此可见，尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。
不是 ．．2. 二叉树的性质图3 二叉树性质１： 在二叉树的第 i 层上至多有 2 i −1 结点(i>=1)。
性质２： 深度为 k 的二叉树至多有 2 k − 1 个结点(k>=1)。
性质３： 对任何一棵二叉树 T，如果其终端结点数为 n0,度为 2 的结点数为 n2,则 n0=n2+1。
二叉树结点计算方法二叉树是一种常见的数据结构，它由结点和连接结点的边组成。
每个结点最多有两个子结点，称为左子结点和右子结点。
在二叉树中，每个结点都有一个值，可以用来存储任何类型的数据。
计算二叉树结点的方法主要有以下几种：1.求二叉树的结点个数：-递归法：计算二叉树的结点个数可以使用递归的方式，首先判断根结点是否为空，如果为空，则返回0；否则，返回左子树的结点个数加上右子树的结点个数再加1，即根结点自身的个数。
递归地计算左右子树的结点个数，直到叶子结点为空，递归结束。
2.求二叉树的叶子结点个数：-递归法：计算二叉树的叶子结点个数也可以使用递归的方式，首先判断根结点是否为空，如果为空，则返回0；否则，如果根结点的左右子树都为空，则返回1，表示根结点为叶子结点。
递归地计算左右子树的叶子结点个数，通过累计求和的方式得到最终的结果。
3.求二叉树的深度：-递归法：计算二叉树的深度可以使用递归的方式，首先判断根结点是否为空，如果为空，则返回0；否则，分别计算左子树和右子树的深度，然后取两者中的较大值，再加上根结点自身的深度，即可得到二叉树的深度。
递归地计算左右子树的深度，直到叶子结点为空，递归结束。
4.求二叉树的最小深度：-递归法：计算二叉树的最小深度可以使用递归的方式，首先判断根结点是否为空，如果为空，则返回0；否则，如果根结点的左右子树都为空，则返回1，表示根结点为叶子结点。
如果根结点的左子树为空，则取右子树的最小深度；如果根结点的右子树为空，则取左子树的最小深度；否则，取左右子树中的较小深度。
递归地计算左右子树的最小深度，通过取较小值的方式得到最终的结果。
以上是常见的计算二叉树结点的方法，它们都可以通过递归的方式实现。
在实际应用中，可以根据具体的需求选择适当的方法来计算二叉树的结点。
第六章树和二叉树PROC Postorder-eval(t:ptrType)BEGIN IF (t!=NULL)BEGIN (1)_______; (2)_______;CASE t^.data:‘+’: t^.Val:=t^. Lchild^. Val + t^. Rchild ^. Val; BREAK;‘-’: t^.Val:=t^. Lchild^. Val - t^. Rchild ^. Val; BREAK;‘*’: t^.Val:=t^. Lchild^. Val * t^. Rchild ^. Val; BREAK;‘/’: t^.Val:=t^. Lchild^. Val / t^. Rchild ^. Val; BREAK;otherwise: (3)___; BREAK;ENDCASE ENDEND;②PROC Delete(x:datatype,A:tree)BEGIN tempA:= (4)___;WHILE (tempA^.Item!=x) AND (tempA!=NULL) DOIF (x<tempA^.item) BEGIN r:=tempA; tempA:= (5)___; ENDELSE BEGIN r:=tempA;tempA:=tempA^.Rchild;END;//tempA为要删结点，r为tempA的父亲IF (6)___ return(x);IF (tempA^.Lchild!=NULL) AND (tempA^.rchild!=NULL)BEGIN t:=tempA; q:=tempA^.Rchild;WHILE (q^.Lchild!=NULL) DO BEGIN t:=q; q:=q^.Lchild; END;t^.Lchild:= (7)___; //删去qq^.Lchild :=tempA^.Lchild; q^.Rchild:=tempA^.Rchild;IF (tempA^.item< r^.item) r^.Lchild := (8)_ ELSE r^.Rchild:=q //用q代替 tempAEND;ELSE IF(tempA^.Lchild!=NULL) IF(tempA^.item<r^.item) r^.Lchild:=tempA^.LchildELSE r^.Rchild:=tempA^.LchildELSE IF(tempA^.Rchild!=NULL) IF(tempA^.item<r^.item) r^.Rchild:= (9)___ELSE r^.Lchild:=tempA^.Rchild ELSE //tempA为树叶IF(10)_ r^.Lchild:=NULL ELSE r^.Rchild:=NULLEND; 【中山大学 1999 四、 (20分)】58．下面的类PASCAL语言递归算法的功能是判断一棵二叉树（采用二叉链表存贮结构）是否为完全二叉树。
习题6解答判断题：1.二叉树中每个结点有两个子女结点，而对一般的树则无此限制，因此二叉树是树的特殊情形。
( ╳ )2.二叉树就是结点度为2的树。
( ╳ )( (哈工大2000年研究生试题)3.二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树之分。
( ╳ ) (陕西省1998年自考试题)4.当k≥1时，高度为k的二叉树至多有21 k个结点。
( ╳ )5.完全二叉树的某结点若无左孩子，则它必是叶结点。
(√)(中科院软件所1997年研究生试题)6.用一维数组存放二叉树时，总是以前序遍历顺序存储结点。
( ╳ )7.若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。
( ╳ )8.存在这样的二叉树，对它采用任何次序的遍历，结果相同。
(√)(哈工大2000年研究生试题)9.中序线索二叉树的优点之一是便于在中序下查找前驱结点和后继结点。
(√)10.将一棵树转换成二叉树后，根结点没有左子树，( ╳ )(北邮1999年研究生试题。
)11.由树转换成二叉树，其根结点的右子树总是空的。
(√)12.前序遍历森林和前序遍历与该森林对应的二叉树其结果不同。
( ╳ )13.在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。
( ╳ )14.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。
( ╳ )15.霍夫曼树一定是满二叉树。
( ╳ )16.树的度是树内各结点的度之和。
( ╳ )17.由二叉树的结点构成的集合可以是空集合。
(√)18.一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。
( ╳ )选择题：19.树最适合用来表示( C )。
A．有序数据元素 B. 无序数据元素C．元素之间具有分支层次关系的数据 D. 元素之间无联系的数据20.如果结点A有3个兄弟，而且B是A的双亲，则B的度是( D )。
第6章树和二叉树自测卷解答一、下面是有关二叉树的叙述，请判断正误（√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。
（×）2.二叉树中每个结点的两棵子树的高度差等于1。
（√）3.二叉树中每个结点的两棵子树是有序的。
（×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。
（×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。
（应当是二叉排序树的特点）（×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。
（应2i-1）（×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
（×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。
（应2i-1）（√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
（正确。
用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。
由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。
）即有后继链接的指针仅n-1个。
（√）10. 具有12个结点的完全二叉树有5个度为2的结点。
最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5二、填空（每空1分，共15分）1．由３个结点所构成的二叉树有5种形态。
2. 一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。
注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。
3．一棵具有２５７个结点的完全二叉树，它的深度为9。
（注：用⎣ log2(n) ⎦+1= ⎣ 8.xx ⎦+1=94.设一棵完全二叉树有700个结点，则共有350个叶子结点。
数据结构习题7树和二叉树一、判断题1. 树结构中每个结点最多只有一个直接前驱。
（√）2. 完全二叉树一定是满二叉树。
（×）3. 在中序线索二叉树中，右线索若不为空，则一定指向其双亲。
（×）4. 一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。
（√）5. 二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。
（√）6. 由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。
（√）7. 在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。
（√）8. 在哈夫曼编码中，当两个字符出现的频率相同，其编码也相同，对于这种情况应该做特殊处理。
（×）9. 含多于两棵树的森林转换的二叉树，其根结点一定无右孩子。
（×）10. 具有n个叶子结点的哈夫曼树共有2n-1个结点。
（√）二、填空题1. 在树中，一个结点所拥有的子树数称为该结点的度。
2. 度为零的结点称为叶（或叶子，或终端）结点。
3. 树中结点的最大层次称为树的深度（或高度）。
4. 对于二叉树来说，第i层上至多有 2i-1个结点。
5. 深度为h的二叉树至多有 2h-1 个结点。
6. 由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。
7. 有20个结点的完全二叉树，编号为10的结点的父结点的编号是 5 。
8. 哈夫曼树是带权路径长度的最小的二叉树。
9. 由二叉树的后序和中序遍历序列，可以唯一确定一棵二叉树。
10. 某二叉树的中序遍历序列为：DEBAC，后序遍历序列为：EBCAD。
则前序遍历序列为 DABEC 。
11. 设一棵二叉树结点的先序遍历序历为：ABDECFGH，中序遍历序历为：DEBAFCHG，则二叉树中叶结点是： E、F、H 。
12. 已知完全二叉树的第8层有8个结点，则其叶结点数是 68 。
13. 由树转换二叉树时，其根结点无右子树。
14. 采用二叉链表存储的n个结点的二叉树，一共有 2n 个指针域。
7数据结构复习题（二叉树）一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）树结构中每个结点最多只有一个直接前驱。
（ㄨ）（2）完全二叉树一定是满二查树。
（ㄨ）（3）在中序线索二叉树中，右线索若不为空，则一定指向其双亲。
（√）（4）一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。
（√）（5）二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。
（√）（6）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。
（√）（7）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。
（ㄨ）（8）在哈夫曼编码中，当两个字符出现的频率相同，其编码也相同，对于这种情况应该做特殊处理。
（ㄨ）（9）含多于两棵树的森林转换的二叉树，其根结点一定无右孩子。
（√）（10）具有n个叶子结点的哈夫曼树共有2n-1个结点。
二．填空题（1）在树中，一个结点所拥有的子树数称为该结点的度。
（2）度为零的结点称为叶（或叶子，或终端）结点。
（3）树中结点的最大层次称为树的深度（或高度）。
（4）对于二叉树来说，第i层上至多有2i-1个结点。
（5）深度为h的二叉树至多有2h-1 个结点。
（6）由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。
（7）有20个结点的完全二叉树，编号为10的结点的父结点的编号是 5 。
（8）哈夫曼树是带权路径长度最小的二叉树。
（9）由二叉树的后序和中序遍历序列，可以唯一确定一棵二叉树。
（10）某二叉树的中序遍历序列为: DEBAC，后序遍历序列为：EBCAD。
则前序遍历序列为：DABEC 。
（11）设一棵二叉树结点的先序遍历序历为：ABDECFGH，中序遍历序历为：DEBAFCHG，则二叉树中叶结点是：E、F、H 。
（12）已知完全二叉树的第8层有8个结点，则其叶结点数是68 。
（13）由树转换成二叉树时，其根结点无右子树。
（14）采用二叉链表存储的n个结点的二叉树，一共有2n 个指针域。
实验五二叉树
一、实验目的
1、掌握二叉树的基本特性
2、掌握二叉树的先序、中序、后序的递归遍历算法
3、理解二叉树的先序、中序、后序的非递归遍历算法
4、通过求二叉树的深度、叶子结点数和层序遍历等算法，理解二叉树的基本特性
二、实验预习
说明以下概念
1、二叉树：
2、递归遍历：
1、非递归遍历：
4、层序遍历：
三、实验内容和要求
1、阅读并运行下面程序，根据输入写出运行结果，并画出二叉树的形态。
#include<stdio.h>
#include<malloc.h>
#define MAX 20
typedef struct BTNode{ /*节点结构声明*/
char data ; /*节点数据*/
struct BTNode *lchild;
struct BTNode *rchild ; /*指针*/
}*BiTree;
void createBiTree(BiTree *t){ /* 先序遍历创建二叉树*/ char s;
BiTree q;
printf("\nplease input data:(exit for #)");
s=getche();
if(s=='#'){*t=NULL; return;}
q=(BiTree)malloc(sizeof(struct BTNode));
if(q==NULL){printf("Memory alloc failure!"); exit(0);} q->data=s;
*t=q;
createBiTree(&q->lchild); /*递归建立左子树*/
createBiTree(&q->rchild); /*递归建立右子树*/
}
void PreOrder(BiTree p){ /* 先序遍历二叉树*/
if ( p!= NULL ) {
printf("%c", p->data);
PreOrder( p->lchild ) ;
PreOrder( p->rchild) ;
}
}
void InOrder(BiTree p){ /* 中序遍历二叉树*/
if( p!= NULL ) {
InOrder( p->lchild ) ;
printf("%c", p->data);
InOrder( p->rchild) ;
}
}
void PostOrder(BiTree p){ /* 后序遍历二叉树*/
if ( p!= NULL ) {
PostOrder( p->lchild ) ;
PostOrder( p->rchild) ;
printf("%c", p->data);
}
}
void Preorder_n(BiTree p){ /*先序遍历的非递归算法*/
BiTree stack[MAX],q;
int top=0,i;
for(i=0;i<MAX;i++) stack[i]=NULL;/*初始化栈*/
q=p;
while(q!=NULL){
printf("%c",q->data);
if(q->rchild!=NULL) stack[top++]=q->rchild; if(q->lchild!=NULL) q=q->lchild;
else
if(top>0) q=stack[--top];
else q=NULL;
}
}
void release(BiTree t){ /*释放二叉树空间*/
if(t!=NULL){
release(t->lchild);
release(t->rchild);
free(t);
}
}
int main(){
BiTree t=NULL;
createBiTree(&t);
printf("\n\nPreOrder the tree is:");
PreOrder(t);
printf("\n\nInOrder the tree is:");
InOrder(t);
printf("\n\nPostOrder the tree is:");
PostOrder(t);
printf("\n\n先序遍历序列（非递归）:");
Preorder_n(t);
release(t);
return 0;
}
运行程序
输入：
ABC##DE#G##F###
运行结果：
2、在上题中补充求二叉树中求结点总数算法（提示：可在某种遍历过程中统计遍历的结点数），并在主函数中补充相应的调用验证正确性。
算法代码：
3、在上题中补充求二叉树中求叶子结点总数算法（提示：可在某种遍历过程中统计遍历的叶子结点数），并在主函数中补充相应的调用验证正确性。
算法代码：
4、在上题中补充求二叉树深度算法，并在主函数中补充相应的调用验证正确性。
算法代码：
选做实验：（代码可另附纸）
2、补充二叉树层次遍历算法。
（提示：利用队列实现）
5、补充二叉树中序、后序非递归算法。
四、实验小结
五、教师评语。
