二叉树上机实验总结

二叉树上机实验总结（精选3篇）

1.二叉树上机实验总结 篇一

浙江大学城市学院实验报告

课程名称

数据结构基础

实验项目名称

实验十

二叉树的基本操作

实验成绩

指导老师（签名）

日期

一.实验目的和要求

1、掌握二叉树的链式存储结构。

2、掌握在二叉链表上的二叉树操作的实现原理与方法。

3、进一步掌握递归算法的设计方法。

二.实验内容

1、按照下面二叉树二叉链表的存储表示，编写头文件binary_tree.h，实现二叉链表的定义与基本操作实现函数；编写主函数文件test4_1.cpp，验证头文件中各个操作。

二叉树二叉链表存储表示如下： struct BTreeNode {

ElemType data;

// 结点值域

BTreeNode *lchild , *rchild;// 定义左右孩子指针 };基本操作如下：

①void InitBTree(BTreeNode *&BT);

//初始化二叉树BT

②void CreateBTree(BTreeNode *&BT, char *a);

//根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构

③int EmptyBTree(BTreeNode *BT);

//检查二叉树BT是否为空，空返回1，否则返回0 ④int DepthBTree(BTreeNode *BT);//求二叉树BT的深度并返回该值

⑤int FindBTree(BTreeNode *BT, ElemType x);

//查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0

⑥void PreOrder(BTreeNode *BT);//先序遍历二叉树BT ⑦void InOrder(BTreeNode *BT);//中序遍历二叉树BT ⑧void PostOrder(BTreeNode *BT);

//后序遍历发二叉树BT

⑨void PrintBTree(BTreeNode *BT);

//输出二叉树BT ⑩void ClearBTree(BTreeNode *&BT);

//清除二叉树BT

2、选做：实现以下说明的操作函数，要求把函数添加到头文件binary_tree.h中，并在主函数文件test4_1.cpp中添加相应语句进行测试。①void LevelOrder(BTreeNode *BT)//二叉树的层序遍历

②int Get_Sub_Depth(BTreeNode *T , ElemType x)//求二叉树中以元素值为x的结点为根的子树的深度

3、填写实验报告，实验报告文件取名为report10.doc。

4、上传实验报告文件report10.doc、源程序文件test4_1.cpp及binary_tree.h到Ftp服务器上自己的文件夹下。

三.函数的功能说明及算法思路

（包括每个函数的功能说明，及一些重要函数的算法实现思路）函数：void InitBTree(BTreeNode *&BT)功能：初始化二叉树BT 思路：将BT指向NULL

函数：void CBTree(BTreeNode *&BT)功能：输入二叉树

思路：按先序次序输入二叉树中结点的值（一个字符）特殊字符 $ 表示空树

函数：void PBTree(BTreeNode *BT,int n)功能：横向打印二叉树

思路：先递归输出右子树，按层次输出空格和“---”控制格式，再输出当前结点值，最后递归左子树

函数：void CreateBTree(BTreeNode *&BT, char *a)功能：根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构

思路：根据广义表表示的”(”,”)”和”,”等字符来构建二叉树，用栈S来存储根结点指针，用p来接收当前结点值数据并链接为栈顶元素的左/右孩子

函数：int EmptyBTree(BTreeNode *BT)功能：检查二叉树BT是否为空，空返回1，否则返回0 思路：返回判断BT是否指向NULL

函数：int DepthBTree(BTreeNode *BT)功能：求二叉树BT的深度并返回该值

思路：若一棵二叉树为空，则它的深度为0，否则它的深度等于左子树和右子树中的最大深度加1

函数：int FindBTree(BTreeNode *BT, ElemType x)功能：查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0

思路：类似于前序遍历，若空树则返回0。若根结点值等于查找值x则返回1，否则先调用函数本身查找左子树，还未找到则再查找右子树，所有操作完成均为找到，则返回0

函数：void PreOrder(BTreeNode *BT)功能：先序遍历二叉树BT 思路：使用“根左右”的顺序遍历二叉树

函数：void InOrder(BTreeNode *BT)功能：中序遍历二叉树BT 思路：使用“左根右”的顺序遍历二叉树

函数：void PostOrder(BTreeNode *BT)

功能：后序遍历二叉树BT 思路：使用“左右根”的顺序遍历二叉树

函数：void PrintBTree(BTreeNode *BT)

功能：输出二叉树BT 思路：按照广义表表示方法输出二叉树（与输入时相同）

函数：void ClearBTree(BTreeNode *&BT)

功能：清除二叉树BT 思路：按照先子树后根结点的顺序删除二叉树

函数（选作）：void LevelOrder(BTreeNode *BT)功能：二叉树的层序遍历

思路：初始化一个空队列，若二叉树为空，则空操作；否则，树根指针入队列。当队列非空时循环：出队首元素，并输出该元素（指针）所指结点的值；且若该结点存在左右孩子，则左右孩子指针进队列。输出结果就是层序遍历序列

函数（选作）：求二叉树中以元素值为x的结点为根的子树的深度 功能：int Get_Sub_Depth(BTreeNode *T , ElemType x)思路：在FindBTree函数的基础上修改，将找到结点时的返回值改为调用DepthBTree求出以该结点为根结点的子树深度即可

四.实验结果与分析

（包括运行结果截图、结果分析等）

测试数据：a(b(c),d(e(f,g),h(,i)))，abc$$$def$$g$$h$i$$ 结果分析：针对该二叉树，程序输出深度为4，正确；查找值f能够找到，正确；先序遍历结果为a b c d e f g h i，正确；中序遍历结果为c b a f e g d h i，正确；后续遍历结果为c b f g e I h d a，正确；输出二叉树的结果与输入一致，正确；使用先序输入二叉树和横向输出部分正确。选作部分，层序遍历结果为a b d c e h f g i，正确；以结点d为根结点的子树深度为3，正确。

五.心得体会

（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）

【附录----源程序】

2.树和二叉树教案1 篇二

一、导入

树是一类重要的非线性数据结构，是以分支关系定义的层次结构。在日常生活同学们经常见到树。树有一个树根。有许多树枝，在树枝上长有很多树叶。就象我们今天要讲的树，是一种层次结构。

二、新授(一)树 1． 树的定义

树（tree）是由 n(n≥0)个结点组成的有限集合。它是树型结构的简称，是一种重要的非线性数据结构，应用广泛。如：磁盘上的文件目录结构、家族成员关系、单位的组织机构、书的内容组织、算术表达式等。任何一棵非空树是一个二元组：

Tree =（root，F）其中：root被称为根结点，F被称为子树森林 2． 基本术语

森

林：是m（m≥0）棵互不相交的树的集合

有 向 树：有确定的根，树根和子树根之间为有向关系（自上到下，自左到右）有 序 树：树中结点的各子树从左到右是有次序的，不能互换 无 序 树：树中结点的各子树从左到右是没有次序的 子 女：结点的子树的根是该结点的孩子 双 亲：孩子结点的根结点 兄 弟：具有同一双亲的结点 堂 兄 弟：双亲在同一层的结点

祖 先：从根到该结点所经历分支上的所有结点 子 孙：以某结点为根的子树中的任一结点

学生活动：请同学门总结树形与线形的异同

(二)二叉树 1.二叉树的定义

二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。

2．二叉树的五种基本形态

二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。

3．二叉树不是树的特例（1）二叉树与无序树不同

二叉树中，每个结点最多只能有两棵子树，并且有左右之分。

二叉树并非是树的特殊情形，它们是两种不同的数据结构。

（2）二叉树与度数为2的有序树不同

在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。

4、满二叉树和完全二叉树是二叉树的两种特殊情形。

a、满二叉树 一棵深度为k且有2k-1个结点的二又树称为满二叉树。满二叉树的特点：

（1）每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。

（2）满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。

b、完全二叉树(Complete BinaryTree)若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。

特点：

（1）满二叉树是完全二叉树，完全二叉树不一定是满二叉树。

（2）在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。

（3）在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。

5、二叉树的性质

性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)。性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。

性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。

性质4 具有n个结点的完全二叉树的深度为

3.数据结构平衡二叉树的操作演示 篇三

1.需求分析

本程序是利用平衡二叉树，实现动态查找表的基本功能：创建表，查找、插入、删除。具体功能：

（1）初始，平衡二叉树为空树，操作界面给出创建、查找、插入、删除、合并、分裂六种操作供选择。每种操作均提示输入关键字。每次插入或删除一个结点后，更新平衡二叉树的显示。

（2）平衡二叉树的显示采用凹入表现形式。（3）合并两棵平衡二叉树。

（4）把一棵二叉树分裂为两棵平衡二叉树，使得在一棵树中的所有关键字都小于或等于x，另一棵树中的任一关键字都大于x。

如下图：

2．概要设计

平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。具体步骤：

（1）每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值不超过1，则平衡二叉树没有失去平衡，继续插入结点；

（2）若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；

（3）判断新插入的结点与最小不平衡子树的根结点个关系，确定是那种类型的调整；（4）如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或RL型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；

（5）计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后平衡二叉树中是否存在平衡因子大于1的结点。流程图

3.详细设计

二叉树类型定义： typedefint Status;typedefintElemType;typedefstructBSTNode{

ElemType data;

int bf;

structBSTNode *lchild ,*rchild;} BSTNode,* BSTree;

Status SearchBST(BSTreeT,ElemType e)//查找 void R_Rotate(BSTree&p)//右旋 void L_Rotate(BSTree&p)//左旋

void LeftBalance(BSTree&T)//插入平衡调整 void RightBalance(BSTree&T)//插入平衡调整

Status InsertAVL(BSTree&T,ElemTypee,int&taller)//插入 void DELeftBalance(BSTree&T)//删除平衡调整 void DERightBalance(BSTree&T)//删除平衡调整 Status Delete(BSTree&T,int&shorter)//删除操作

Status DeleteAVL(BSTree&T,ElemTypee,int&shorter)//删除操作 void merge(BSTree&T1,BSTree &T2)//合并操作

void splitBSTree(BSTreeT,ElemTypee,BSTree&T1,BSTree &T2)//分裂操作 void PrintBSTree(BSTree&T,intlev)//凹入表显示

附录

源代码：

#include #include //#define TRUE 1 //#define FALSE 0 //#define OK 1 //#define ERROR 0 #define LH +1 #define EH 0 #define RH-1 //二叉类型树的类型定义 typedefint Status;typedefintElemType;typedefstructBSTNode{ ElemType data;int bf;//结点的平衡因子

structBSTNode *lchild ,*rchild;//左、右孩子指针 } BSTNode,* BSTree;/* 查找算法 */ Status SearchBST(BSTreeT,ElemType e){ if(!T){ return 0;//查找失败 } else if(e == T->data){ return 1;//查找成功 } else if(e < T->data){ returnSearchBST(T->lchild,e);} else{ returnSearchBST(T->rchild,e);} }

//右旋

voidR_Rotate(BSTree&p){ BSTreelc;//处理之前的左子树根结点

lc = p->lchild;//lc指向的*p的左子树根结点

p->lchild = lc->rchild;//lc的右子树挂接为*P的左子树 lc->rchild = p;p = lc;//p指向新的根结点

} //左旋

voidL_Rotate(BSTree&p){ BSTreerc;rc = p->rchild;//rc指向的*p的右子树根结点

p->rchild = rc->lchild;//rc的左子树挂接为*p的右子树 rc->lchild = p;p = rc;//p指向新的根结点 } //对以指针T所指结点为根结点的二叉树作左平衡旋转处理，//本算法结束时指针T指向新的根结点 voidLeftBalance(BSTree&T){ BSTreelc,rd;lc=T->lchild;//lc指向*T的左子树根结点

switch(lc->bf){ //检查*T的左子树的平衡度，并做相应的平衡处理

case LH:

//新结点插入在*T的左孩子的左子树，要做单右旋处理 T->bf = lc->bf=EH;R_Rotate(T);break;case RH:

//新结点插入在*T的左孩子的右子树上，做双旋处理 rd=lc->rchild;//rd指向*T的左孩子的右子树根 switch(rd->bf){ //修改*T及其左孩子的平衡因子 case LH: T->bf=RH;lc->bf=EH;break;case EH: T->bf=lc->bf=EH;break;case RH: T->bf=EH;lc->bf=LH;break;} rd->bf=EH;L_Rotate(T->lchild);//对*T的左子树作左旋平衡处理 R_Rotate(T);//对*T作右旋平衡处理 } } //右平衡旋转处理

voidRightBalance(BSTree&T){ BSTreerc,ld;rc=T->rchild;switch(rc->bf){ case RH: T->bf= rc->bf=EH;L_Rotate(T);break;case LH: ld=rc->lchild;switch(ld->bf){ case LH: T->bf=RH;rc->bf=EH;break;case EH: T->bf=rc->bf=EH;break;case RH: T->bf = EH;rc->bf=LH;break;} ld->bf=EH;R_Rotate(T->rchild);L_Rotate(T);} } //插入结点

Status InsertAVL(BSTree&T,ElemTypee,int&taller){//taller反应T长高与否 if(!T){//插入新结点，树长高，置taller为true T=(BSTree)malloc(sizeof(BSTNode));T->data = e;T->lchild = T->rchild = NULL;T->bf = EH;taller = 1;} else{ if(e == T->data){ taller = 0;return 0;} if(e < T->data){ if(!InsertAVL(T->lchild,e,taller))//未插入 return 0;if(taller)//已插入到*T的左子树中且左子树长高

switch(T->bf){//检查*T的平衡度，作相应的平衡处理 case LH: LeftBalance(T);taller = 0;break;case EH: T->bf = LH;taller = 1;break;case RH: T->bf = EH;taller = 0;break;} } else{ if(!InsertAVL(T->rchild,e,taller)){ return 0;} if(taller)//插入到*T的右子树且右子树增高 switch(T->bf){//检查*T的平衡度 case LH: T->bf = EH;taller = 0;break;case EH: T->bf = RH;taller = 1;break;case RH: RightBalance(T);taller = 0;break;} } } return 1;}

void DELeftBalance(BSTree&T){//删除平衡调整 BSTreelc,rd;lc=T->lchild;switch(lc->bf){ case LH: T->bf = EH;//lc->bf= EH;R_Rotate(T);break;case EH: T->bf = EH;lc->bf= EH;R_Rotate(T);break;case RH: rd=lc->rchild;switch(rd->bf){ case LH: T->bf=RH;lc->bf=EH;break;case EH: T->bf=lc->bf=EH;break;case RH: T->bf=EH;lc->bf=LH;break;} rd->bf=EH;L_Rotate(T->lchild);R_Rotate(T);} }

void DERightBalance(BSTree&T)//删除平衡调整 { BSTreerc,ld;rc=T->rchild;switch(rc->bf){ case RH: T->bf= EH;//rc->bf= EH;L_Rotate(T);break;case EH: T->bf= EH;//rc->bf= EH;L_Rotate(T);break;case LH: ld=rc->lchild;switch(ld->bf){ case LH: T->bf=RH;rc->bf=EH;break;case EH: T->bf=rc->bf=EH;break;case RH: T->bf = EH;rc->bf=LH;break;} ld->bf=EH;R_Rotate(T->rchild);L_Rotate(T);} }

voidSDelete(BSTree&T,BSTree&q,BSTree&s,int&shorter){ if(s->rchild){ SDelete(T,s,s->rchild,shorter);if(shorter)switch(s->bf){ case EH: s->bf = LH;shorter = 0;break;case RH: s->bf = EH;shorter = 1;break;case LH: DELeftBalance(s);shorter = 0;break;} return;}

T->data = s->data;if(q!= T)q->rchild = s->lchild;else q->lchild = s->lchild;shorter = 1;} //删除结点

Status Delete(BSTree&T,int&shorter){ BSTree q;if(!T->rchild){ q = T;T = T->lchild;free(q);shorter = 1;} else if(!T->lchild){ q = T;T= T->rchild;free(q);shorter = 1;} else{ SDelete(T,T,T->lchild,shorter);if(shorter)switch(T->bf){ case EH: T->bf = RH;shorter = 0;break;case LH: T->bf = EH;shorter = 1;break;case RH: DERightBalance(T);shorter = 0;break;} } return 1;}

Status DeleteAVL(BSTree&T,ElemTypee,int&shorter){ int sign = 0;if(!T){ return sign;} else{ if(e == T->data){ sign = Delete(T,shorter);return sign;}

else if(e < T->data){ sign = DeleteAVL(T->lchild,e,shorter);if(shorter)switch(T->bf){ case EH: T->bf = RH;shorter = 0;break;case LH: T->bf = EH;shorter = 1;break;case RH: DERightBalance(T);shorter = 0;break;}

return sign;} else{ sign = DeleteAVL(T->rchild,e,shorter);if(shorter)switch(T->bf){ case EH: T->bf = LH;shorter = 0;break;case RH: T->bf = EH;break;case LH: DELeftBalance(T);shorter = 0;break;} return sign;}

} } //合并

void merge(BSTree&T1,BSTree &T2){ int taller = 0;if(!T2)return;merge(T1,T2->lchild);InsertAVL(T1,T2->data,taller);merge(T1,T2->rchild);} //分裂

void split(BSTreeT,ElemTypee,BSTree&T1,BSTree &T2){ int taller = 0;if(!T)return;split(T->lchild,e,T1,T2);if(T->data > e)InsertAVL(T2,T->data,taller);else InsertAVL(T1,T->data,taller);split(T->rchild,e,T1,T2);} //分裂

voidsplitBSTree(BSTreeT,ElemTypee,BSTree&T1,BSTree &T2){ BSTree t1 = NULL,t2 = NULL;split(T,e,t1,t2);T1 = t1;T2 = t2;return;}

//构建

voidCreatBSTree(BSTree&T){ intnum,i,e,taller = 0;printf(“输入结点个数:”);scanf(“%d”,&num);printf(“请顺序输入结点值n”);for(i = 0;i

voidPrintBSTree(BSTree&T,intlev){ int i;if(T->rchild)PrintBSTree(T->rchild,lev+1);for(i = 0;i data);if(T->lchild)PrintBSTree(T->lchild,lev+1);} void Start(BSTree&T1,BSTree &T2){

intcho,taller,e,k;taller = 0;k = 0;while(1){ system(“cls”);printf(“平衡二叉树操作的演示 nn”);printf(“********************************n”);printf(“平衡二叉树显示区 n”);printf(“T1树n”);if(!T1)printf(“n 当前为空树n”);else{ PrintBSTree(T1,1);}

printf(“T2树n”);if(!T2)printf(“n 当前为空树n”);else PrintBSTree(T2,1);printf(“n******************************************************************************n”);printf(“T1操作：1.创建 2.插入 3.查找 4.删除 10.分裂n”);printf(“T2操作：5.创建 6.插入 7.查找 8.删除 11.分裂n”);printf(“ 9.合并 T1,T2 0.退出n”);printf(“******************************************************************************n”);printf(“输入你要进行的操作：”);scanf(“%d”,&cho);switch(cho){ case 1: CreatBSTree(T1);break;case 2: printf(“请输入要插入关键字的值”);scanf(“%d”,&e);InsertAVL(T1,e,taller);break;case 3: printf(“请输入要查找关键字的值”);scanf(“%d”,&e);

if(SearchBST(T1,e))printf(“查找成功！n”);else printf(“查找失败！n”);printf(“按任意键返回87”);getchar();getchar();break;case 4: printf(“请输入要删除关键字的值”);scanf(“%d”,&e);if(DeleteAVL(T1,e,k))printf(“删除成功！n”);else printf(“删除失败！n”);printf(“按任意键返回”);getchar();getchar();break;case 5: CreatBSTree(T2);break;case 6: printf(“请输入要插入关键字的值”);scanf(“%d”,&e);InsertAVL(T2,e,taller);break;case 7: printf(“请输入要查找关键字的值”);scanf(“%d”,&e);

if(SearchBST(T2,e))printf(“查找成功！n”);else printf(“查找失败！n”);printf(“按任意键返回”);getchar();getchar();break;case 8: printf(“请输入要删除关键字的值”);scanf(“%d”,&e);if(DeleteAVL(T2,e,k))printf(“删除成功！n”);else printf(“删除失败！n”);printf(“按任意键返回”);getchar();getchar();break;case 9: merge(T1,T2);T2 = NULL;printf(“合并成功，按任意键返回”);getchar();getchar();break;case 10: printf(“请输入要中间值字的值”);scanf(“%d”,&e);splitBSTree(T1,e,T1,T2);printf(“分裂成功，按任意键返回”);getchar();getchar();break;case 11: printf(“请输入要中间值字的值”);scanf(“%d”,&e);splitBSTree(T2,e,T1,T2);printf(“分裂成功，按任意键返回”);getchar();getchar();break;case 0: system(“cls”);exit(0);} } }