广工数据结构实验报告平衡二叉树

实验报告课程名称数据结构实验学院计算机学院专业班级计科9班学号学生姓名指导教师苏庆2015年 7 月6 日1.题目:平衡二叉树ADT BBSTree{数据对象：D＝{ ai | ai∈ElemSet, i=1,2,...,n, n≥0 }数据关系：R1＝{ <ai-1, ai>|ai-1, ai∈D, i=2,...,n }基本操作：BBSTree MakeBBSTree( )操作结果：创建好一棵树返回：将创建好的树返回Status InsertAVL(BBSTree &T, RcdType e, Status &taller)初始条件：树T已存在，e存在，taller为真操作结果：将e插入到T中返回：成功TRUE，失败FALSEStatus DeleteAVL(BBSTree &t, RcdType e, Status &shorter) 初始条件：树T已存在，e存在，shorter为真操作结果：将e从T中删除返回：成功TRUE，失败FALSEBBSTree SearchAVL(BBSTree T, RcdType e)初始条件：树T已存在，e存在操作结果：从T中找到e返回：以e为根节点的树void L_Rotate(BBSTree &p)初始条件：树p存在操作结果：对p左旋操作void R_Rotate(BBSTree &p)初始条件：树p存在操作结果：对p右旋操作void LeftBalance(BBSTree &T)初始条件：树T存在操作结果：对T左平衡操作void RightBalance(BBSTree &T)初始条件：树T存在操作结果：对T右平衡操作void ExchangeSubTree(BBSTree &T)初始条件：树T存在操作结果：对T所有左右孩子交换int BBSTreeDepth(BBSTree T)初始条件：树T已存在操作结果：求树T的深度返回：树的深度BBSTree Combine2Tree(BBSTree T1, BBSTree T2)初始条件：树T1和T2已存在操作结果：将T1和T2合并返回：合并后的树Status SplitBBSTree(BBSTree Tt1, BBSTree &Tt2,BBSTree &Tt3, int x)初始条件：树Tt1，Tt2，Tt3已存在，x存在操作结果：将Tt1分裂成Tt2和Tt3返回：以e为根节点的树Status PreOrder_RecTraverse(BBSTree T)初始条件：树T已存在操作结果：对树T进行递归先序遍历输出返回：成功TRUE 失败FALSEStatus InOrder_RecTraverse(BBSTree T)初始条件：树T已存在操作结果：对树T进行递归中序遍历输出返回：成功TRUE 失败FALSEStatus LastOrder_RecTraverse(BBSTree T)初始条件：树T已存在操作结果：对树T进行递归后序遍历输出返回：成功TRUE 失败FALSEvoid PreOrderTravese_I(BBSTree T)初始条件：树T已存在操作结果：对树T进行非递归先序遍历输出void InOrderTraverse_I(BBSTree T)初始条件：树T已存在操作结果：对树T进行非递归中序遍历输出void LastOrderTravese_I(BBSTree T)初始条件：树T已存在操作结果：对树T进行非递归后序遍历输出void LevelOrederTraverse_Print(BBSTree T)初始条件：树T已存在操作结果：对树T进行非递归层次遍历输出void BraNotationPrint(BBSTree T)初始条件：树T已存在操作结果：对树T用括号表示法输出}ADT BBSTree2.存储结构定义#include<stdio.h>#include<malloc.h>#define OVERFLOW -1#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define LH +1 //左高#define EH 0 //等高#define RH -1 //右高typedef int RcdType;typedef int Status;/*平衡二叉树结构体*/typedef struct BBSTNode{RcdType data;int bf;BBSTNode *lchild, *rchild;}BBSTNode,*BBSTree;3.算法设计/*求平衡二叉树的深度*/int BBSTreeDepth(BBSTree T){int depthLeft, depthRight;if(NULL==T) return 0;else{depthLeft = BBSTreeDepth(T->lchild);depthRight = BBSTreeDepth(T->rchild);return 1+(depthLeft > depthRight ? depthLeft : depthRight);}}/*交换二叉树所有结点的左右子树*/void ExchangeSubTree(BBSTree &T){BBSTree temp;if(NULL!=T){ExchangeSubTree(T->lchild); //使用递归交换左子树ExchangeSubTree(T->rchild); //使用递归交换右子树if((T->lchild!=NULL)||(T->rchild!=NULL)){ //如果T的子树有一个不为空，则交换左右子树temp = T->lchild;T->lchild = T->rchild;T->rchild = temp;}}}/*左旋调整*/void L_Rotate(BBSTree &p){BBSTree rc = p->rchild;p->rchild = rc->lchild;rc->lchild = p;p = rc;}/*右旋调整*/void R_Rotate(BBSTree &p){BBSTree lc = p->lchild;p->lchild = lc->rchild;lc->rchild = p;p = lc;}/*左平衡处理操作*/void LeftBalance(BBSTree &T){BBSTree lc, rd;lc = T->lchild;switch(lc->bf){case LH:T->bf = 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);break;}}/*右平衡处理操作*/void RightBalance(BBSTree &T){BBSTree rd,lc;rd=T->rchild;switch(rd->bf){case RH:T->bf=rd->bf=EH; L_Rotate(T); break;case LH:lc=rd->lchild;switch(lc->bf){case RH:T->bf=LH;rd->bf=EH;break;case EH:T->bf=rd->bf=EH;break;case LH:T->bf=EH;rd->bf=RH;break;}lc->bf=EH;R_Rotate(T->rchild);L_Rotate(T);break;}}/*平衡二叉树的插入操作*/Status InsertAVL(BBSTree &T, RcdType e, Status &taller){ if(NULL==T){T = (BBSTree)malloc(sizeof(BBSTNode));T->data = e;T->bf = EH;T->lchild = NULL;T->rchild = NULL;}else if(e==T->data){ //书中已存在和e相等的结点taller = FALSE; return FALSE;}else if(e<T->data){if(FALSE==InsertA VL(T->lchild, e, taller)) return FALSE;if(TRUE==taller){switch(T->bf){case LH: LeftBalance(T); taller = FALSE; break;case EH: T->bf = LH; taller = TRUE; break;case RH: T->bf = EH; taller = FALSE; break;}}}else{if(FALSE==InsertA VL(T->rchild, e, taller)) return FALSE;if(TRUE==taller){switch(T->bf){case LH: T->bf = EH; taller = FALSE; break;case EH: T->bf = RH; taller = TRUE; break;case RH: RightBalance(T); taller = FALSE; break;}}}return TRUE;}/*平衡二叉树的删除操作*/Status DeleteA VL(BBSTree &t, RcdType e, Status &shorter){//当被删结点是有两个孩子，且其前驱结点是左孩子时，tag=1 static int tag = 0;if(t == NULL){return FALSE; //如果不存在元素，返回失败}else if(e==t->data){BBSTNode *q = NULL;//如果该结点只有一个孩子，则将自子树取代该结点if(t->lchild == NULL){q = t;t = t->rchild;free(q);shorter = TRUE;}else if(t->rchild == NULL){q = t;t = t->lchild;free(q);shorter = TRUE;}//如果被删结点有两个孩子，则找到结点的前驱结点，//并将前驱结点的值赋给该结点，然后删除前驱结点else{q = t->lchild;while(q->rchild){q = q->rchild;}t->data = q->data;if(t->lchild->data==q->data){tag = 1;}DeleteA VL(t->lchild, q->data, shorter);if(tag==1){BBSTree r = t->rchild;if(NULL==r) t->bf = 0;else{switch(r->bf){case EH: t->bf=-1;break;default: RightBalance(t);break;}}}}}else if(e<t->data){ //左子树中继续查找if(!DeleteA VL(t->lchild, e, shorter)){return FALSE;}//删除完结点之后，调整结点的平衡因子if(shorter&&(tag==0)) {switch(t->bf){case LH:t->bf = EH;shorter = TRUE;break;case EH:t->bf = RH;shorter = FALSE;break;//如果本来就是右子树较高，删除之后就不平衡，需要做右平衡操作case RH:RightBalance(t); //右平衡处理if(t->rchild->bf == EH)shorter = FALSE;elseshorter = TRUE;break;}}}else if(e>t->data){ //右子树中继续查找if(!DeleteA VL(t->rchild, e, shorter)){return FALSE;}//删除完结点之后，调整结点的平衡因子if(shorter&&(tag==0)) {switch(t->bf){case LH:LeftBalance(t); //左平衡处理if(t->lchild->bf == EH)//注意这里，画图思考一下shorter = FALSE;elseshorter = TRUE;break;case EH:t->bf = LH;shorter = FALSE;break;case RH:t->bf = EH;shorter = TRUE;break;}}if(tag==1){int depthLeft = BBSTreeDepth(t->lchild);int depthRight = BBSTreeDepth(t->rchild);t->bf = depthLeft - depthRight;}}return TRUE;}/*平衡二叉树的查找操作*/BBSTree SearchA VL(BBSTree T, RcdType e){if(T==NULL) return NULL;if(e==T->data){return T;}else if(e>T->data){return SearchA VL(T->rchild, e);}else {return SearchA VL(T->lchild, e);}}/*获取输入存到数组a*/Array GetInputToArray(){Array head, p, q;char k;head = p = q = NULL;int m;if(k!='\n'){scanf("%d",&m);p = (ArrayNode*)malloc(sizeof(ArrayNode));head = p;p->data = m;k = getchar();}while(k!='\n'){scanf("%d",&m);q = (ArrayNode*)malloc(sizeof(ArrayNode));q->data = m;p->next = q;p = p->next;k = getchar();}if(p!=NULL){p->next = NULL;}return head; //返回存放数据的头指针}/*根据输入的字符串建一棵平衡二叉树*/BBSTree MakeBBSTree( ){int i=0;Status taller = TRUE;BBSTree T = NULL;Array a;a = GetInputToArray();while(a!=NULL){taller = TRUE;InsertA VL(T, a->data, taller);a = a->next;}return T;}/*递归先序遍历*/Status PreOrder_RecTraverse(BBSTree T){ if(NULL==T) return OK;printf("%d ",T->data);PreOrder_RecTraverse(T->lchild);PreOrder_RecTraverse(T->rchild);}/*递归中序遍历*/Status InOrder_RecTraverse(BBSTree T){ if(T->lchild)InOrder_RecTraverse(T->lchild);printf("%d ",T->data);if(T->rchild)InOrder_RecTraverse(T->rchild);}/*递归后序遍历*/Status LastOrder_RecTraverse(BBSTree T){ if(T->lchild)LastOrder_RecTraverse(T->lchild);if(T->rchild)LastOrder_RecTraverse(T->rchild);printf("%d ",T->data);}/*找到最左结点*/BBSTree GoFarLeft(BBSTree T, LStack &S){ if(NULL==T) return NULL;while(T->lchild!=NULL){Push_LS(S, T);T = T->lchild;}return T;}/*非递归中序遍历*/void InOrderTraverse_I(BBSTree T){LStack S;InitStack_LS(S);BBSTree p = NULL;p = GoFarLeft(T, S);while(p!=NULL){printf("%d ",p->data);if(p->rchild!=NULL){p = GoFarLeft(p->rchild, S);}else if(StackEmpty_LS(S)!=TRUE) Pop_LS(S, p);else p = NULL;}}BBSTree VisitFarLeft(BBSTree T, LStack &S){if(NULL==T) return NULL; //如果T为空，则返回空printf("%d ",T->data); //先序，先读取结点数据while(T->lchild!=NULL){Push_LS(S, T); //入栈T = T->lchild; //遍历下一个左子树printf("%d ", T->data); //下一个结点的读取数据}return T;}/*非递归先序遍历*/void PreOrderTravese_I(BBSTree T){LStack S;InitStack_LS(S);BBSTree p;p = VisitFarLeft(T, S); //先将左边的数据先序读取while(p!=NULL){if(p->rchild!=NULL) //如果最左下结点的右子树不为空p = VisitFarLeft(p->rchild, S); //执行遍历该结点的左子树else if(StackEmpty_LS(S)!=TRUE) Pop_LS(S,p); //如果S不为空栈，出栈else p = NULL; //如果为空栈，p赋予空}}/*非递归后序遍历*/void LastOrderTravese_I(BBSTree root){BBSTree p = root;BBSTree stack[30];int num=0;BBSTree have_visited = NULL;while(NULL!=p||num>0){while(NULL!=p){stack[num++]=p;p=p->lchild;}p=stack[num-1];if(NULL==p->rchild||have_visited==p->rchild){printf("%d ",p->data);num--;have_visited=p;p=NULL;}else{p=p->rchild;}}printf("\n");}/*非递归层次遍历输出一棵二叉树*/void LevelOrederTraverse_Print(BBSTree T){if(T==NULL){printf("The tree is empty!");}if(T!=NULL){LQueue Q;InitQueue_LQ(Q);BBSTree p = T;printf("%d ",p->data);EnQueue_LQ(Q,p);while(DeQueue_LQ(Q,p)){if(p->lchild!=NULL){printf("%d ", p->lchild->data);EnQueue_LQ(Q, p->lchild);}if(p->rchild!=NULL){printf("%d ", p->rchild->data);EnQueue_LQ(Q, p->rchild);}}}}/*括号表示法输出平衡二叉树*/void BraNotationPrint(BBSTree T){if(NULL==T){printf(" 空!");}else{if(T!=NULL){if(T!=NULL){printf("%i",T->data);if(T->lchild||T->rchild){printf("(");}}}if(T->lchild||T->rchild){if(T->lchild){BraNotationPrint(T->lchild);}else if(T->rchild){printf("#");}printf(",");if(T->rchild){BraNotationPrint(T->rchild);}else if(T->lchild){printf("#");}printf(")");}}}/*将一棵树转换为一个数组*/Array GetArrayFromTree(BBSTree T){Status firstTime = TRUE;Array head = NULL;ArrayNode *b = NULL;ArrayNode *q = NULL;if(T==NULL){printf("The tree is empty!");}if(T!=NULL){LQueue Q;InitQueue_LQ(Q);BBSTree p = T;q = (Array)malloc(sizeof(ArrayNode));q->data = p->data;if(firstTime==TRUE){head = q;firstTime = FALSE;b = q;}else{b->next = q;b = b->next;}EnQueue_LQ(Q,p);while(DeQueue_LQ(Q,p)){if(p->lchild!=NULL){q = (Array)malloc(sizeof(ArrayNode));q->data = p->lchild->data;b->next = q;b = b->next;EnQueue_LQ(Q, p->lchild);}if(p->rchild!=NULL){q = (Array)malloc(sizeof(ArrayNode));q->data = p->rchild->data;b->next = q;b = b->next;EnQueue_LQ(Q, p->rchild);}}if(b!=NULL){b->next = NULL;}}return head;}/*将两棵平衡二叉树合并成一颗平衡二叉树*/ BBSTree Combine2Tree(BBSTree T1, BBSTree T2){ Status taller = TRUE;Array a = NULL;a = GetArrayFromTree(T2);while(a!=NULL){taller = TRUE;InsertA VL(T1, a->data, taller);a = a->next;}return T1;}/*将一棵平衡二叉树分裂成两棵平衡二叉树*//*参数1：要进行分裂的树参数2：分裂出来的小于等于x的子树参数3：分裂出来的大于x的子树参数4：关键字x*/Status SplitBBSTree(BBSTree Tt1, BBSTree &Tt2, BBSTree &Tt3, int x){ Array a = NULL;Status taller;a = GetArrayFromTree(Tt1);if(Tt1==NULL) return FALSE;else{while(a!=NULL){if(a->data<=x){taller = TRUE;InsertA VL(Tt2, a->data, taller);a = a->next;}else {taller = TRUE;InsertA VL(Tt3, a->data, taller);a = a->next;}}}return TRUE;}4.测试(1)建树操作测试代码:测试数据：1 2 3 4 5 6测试结果：(2)插入操作测试代码：测试数据：1 2 3 4 5 6 插入8测试结果：测试数据：1 2 3 4 5 6 插入4测试结果：(3)删除操作测试代码：测试数据：1 2 3 4 5 6 删除6测试结果：测试数据：1 2 3 4 5 6 删除2测试结果：测试数据：1 2 3 4 5 6 删除4测试结果：(4)查找操作测试代码：测试数据：1 2 3 4 5 6 查找5测试结果：(5)输出测试代码：测试数据：1 2 3 4 5 6测试结果：5.思考与小结在完成平衡二叉树实验的过程中，所遇到的最大问题就是如何实现平衡二叉树删除结点的接口，因为课本没有涉及到这个知识点，所以自己只能通过阅读其他书籍和通过参考网上的资料来对这个过程有了进一步的理解。

数据结构实验报告二叉树数据结构实验报告：二叉树引言：数据结构是计算机科学中的重要基础，它为我们提供了存储和组织数据的方式。

二叉树作为一种常见的数据结构，广泛应用于各个领域。

本次实验旨在通过实践，深入理解二叉树的概念、性质和操作。

一、二叉树的定义与性质1.1 定义二叉树是一种特殊的树结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树可以为空树，也可以是由根节点和左右子树组成的非空树。

1.2 基本性质（1）每个节点最多有两个子节点；（2）左子树和右子树是有顺序的，不能颠倒；（3）二叉树的子树仍然是二叉树。

二、二叉树的遍历2.1 前序遍历前序遍历是指首先访问根节点，然后按照先左后右的顺序遍历左右子树。

在实际应用中，前序遍历常用于复制一颗二叉树或创建二叉树的副本。

2.2 中序遍历中序遍历是指按照先左后根再右的顺序遍历二叉树。

中序遍历的结果是一个有序序列，因此在二叉搜索树中特别有用。

2.3 后序遍历后序遍历是指按照先左后右再根的顺序遍历二叉树。

后序遍历常用于计算二叉树的表达式或释放二叉树的内存。

三、二叉树的实现与应用3.1 二叉树的存储结构二叉树的存储可以使用链式存储或顺序存储。

链式存储使用节点指针连接各个节点，而顺序存储则使用数组来表示二叉树。

3.2 二叉树的应用（1）二叉搜索树：二叉搜索树是一种特殊的二叉树，它的左子树上的节点都小于根节点，右子树上的节点都大于根节点。

二叉搜索树常用于实现查找、插入和删除等操作。

（2）堆：堆是一种特殊的二叉树，它满足堆序性质。

堆常用于实现优先队列，如操作系统中的进程调度。

（3）哈夫曼树：哈夫曼树是一种带权路径最短的二叉树，常用于数据压缩和编码。

四、实验结果与总结通过本次实验，我成功实现了二叉树的基本操作，包括创建二叉树、遍历二叉树和查找节点等。

在实践中，我进一步理解了二叉树的定义、性质和应用。

二叉树作为一种重要的数据结构，在计算机科学中有着广泛的应用，对于提高算法效率和解决实际问题具有重要意义。

[精品]【数据结构】二叉树实验报告二叉树实验报告一、实验目的：1.掌握二叉树的基本操作；2.理解二叉树的性质；3.熟悉二叉树的广度优先遍历和深度优先遍历算法。

二、实验原理：1.二叉树是一种树形结构，由n(n>=0)个节点组成；2.每个节点最多有两个子节点，称为左子节点和右子节点；3.二叉树的遍历分为四种方式：前序遍历、中序遍历、后序遍历和层次遍历。

三、实验环境：1.编程语言：C++；2.编译器：Dev-C++。

四、实验内容：1.定义二叉树节点结构体：struct BinaryTreeNode{int data; // 节点数据BinaryTreeNode *leftChild; // 左子节点指针BinaryTreeNode *rightChild; // 右子节点指针};2.初始化二叉树：queue<BinaryTreeNode *> q; // 使用队列存储节点q.push(root);int i = 1; // 创建子节点while (!q.empty() && i < length){BinaryTreeNode *node = q.front();q.pop();if (data[i] != -1) // 创建左子节点 {BinaryTreeNode *leftChild = new BinaryTreeNode;leftChild->data = data[i];leftChild->leftChild = nullptr;leftChild->rightChild = nullptr;node->leftChild = leftChild;q.push(leftChild);}i++;if (data[i] != -1) // 创建右子节点 {BinaryTreeNode *rightChild = new BinaryTreeNode;rightChild->data = data[i];rightChild->leftChild = nullptr;rightChild->rightChild = nullptr;node->rightChild = rightChild;q.push(rightChild);}i++;}return root;}3.前序遍历二叉树：五、实验结果：输入：int data[] = {1, 2, 3, 4, -1, -1, 5, 6, -1, -1, 7, 8};输出：前序遍历结果：1 2 4 5 3 6 7 8中序遍历结果：4 2 5 1 6 3 7 8后序遍历结果：4 5 2 6 8 7 3 1层次遍历结果：1 2 3 4 5 6 7 8通过本次实验，我深入理解了二叉树的性质和遍历方式，并掌握了二叉树的基本操作。

数据结构二叉树的实验报告数据结构二叉树的实验报告一、引言数据结构是计算机科学中非常重要的一个领域，它研究如何组织和存储数据以便高效地访问和操作。

二叉树是数据结构中常见且重要的一种，它具有良好的灵活性和高效性，被广泛应用于各种领域。

本实验旨在通过实际操作和观察，深入了解二叉树的特性和应用。

二、实验目的1. 理解二叉树的基本概念和特性；2. 掌握二叉树的创建、遍历和查找等基本操作；3. 通过实验验证二叉树的性能和效果。

三、实验过程1. 二叉树的创建在实验中，我们首先需要创建一个二叉树。

通过输入一系列数据，我们可以按照特定的规则构建一棵二叉树。

例如，可以按照从小到大或从大到小的顺序将数据插入到二叉树中，以保证树的有序性。

2. 二叉树的遍历二叉树的遍历是指按照一定的次序访问二叉树中的所有节点。

常见的遍历方式有前序遍历、中序遍历和后序遍历。

前序遍历是先访问根节点，然后再依次遍历左子树和右子树；中序遍历是先遍历左子树，然后访问根节点，最后再遍历右子树；后序遍历是先遍历左子树，然后遍历右子树，最后访问根节点。

3. 二叉树的查找二叉树的查找是指在二叉树中寻找指定的节点。

常见的查找方式有深度优先搜索和广度优先搜索。

深度优先搜索是从根节点开始，沿着左子树一直向下搜索，直到找到目标节点或者到达叶子节点；广度优先搜索是从根节点开始，逐层遍历二叉树，直到找到目标节点或者遍历完所有节点。

四、实验结果通过实验，我们可以观察到二叉树的特性和性能。

在创建二叉树时，如果按照有序的方式插入数据，可以得到一棵平衡二叉树，其查找效率较高。

而如果按照无序的方式插入数据，可能得到一棵不平衡的二叉树，其查找效率较低。

在遍历二叉树时，不同的遍历方式会得到不同的结果。

前序遍历可以用于复制一棵二叉树，中序遍历可以用于对二叉树进行排序，后序遍历可以用于释放二叉树的内存。

在查找二叉树时，深度优先搜索和广度优先搜索各有优劣。

深度优先搜索在空间复杂度上较低，但可能会陷入死循环；广度优先搜索在时间复杂度上较低，但需要较大的空间开销。

数据结构实验报告—二叉树数据结构实验报告—二叉树引言二叉树是一种常用的数据结构，它由节点和边构成，每个节点最多有两个子节点。

在本次实验中，我们将对二叉树的基本结构和基本操作进行实现和测试，并深入了解它的特性和应用。

实验目的1. 掌握二叉树的基本概念和特性2. 熟练掌握二叉树的基本操作，包括创建、遍历和查找等3. 了解二叉树在实际应用中的使用场景实验内容1. 二叉树的定义和存储结构：我们将首先学习二叉树的定义，并实现二叉树的存储结构，包括节点的定义和节点指针的表示方法。

2. 二叉树的创建和初始化：我们将实现二叉树的创建和初始化操作，以便后续操作和测试使用。

3. 二叉树的遍历：我们将实现二叉树的前序、中序和后序遍历算法，并测试其正确性和效率。

4. 二叉树的查找：我们将实现二叉树的查找操作，包括查找节点和查找最大值、最小值等。

5. 二叉树的应用：我们将探讨二叉树在实际应用中的使用场景，如哈夫曼编码、二叉搜索树等。

二叉树的定义和存储结构二叉树是一种特殊的树形结构，它的每个节点最多有两个子节点。

节点被表示为一个由数据和指向其左右子节点的指针组成的结构。

二叉树可以分为三类：满二叉树、完全二叉树和非完全二叉树。

二叉树可以用链式存储结构或顺序存储结构表示。

- 链式存储结构：采用节点定义和指针表示法，通过将节点起来形成一个树状结构来表示二叉树。

- 顺序存储结构：采用数组存储节点信息，通过计算节点在数组中的位置来进行访问和操作。

二叉树的创建和初始化二叉树的创建和初始化是二叉树操作中的基础部分。

我们可以通过手动输入或读取外部文件中的数据来创建二叉树。

对于链式存储结构，我们需要自定义节点和指针，并通过节点的方式来构建二叉树。

对于顺序存储结构，我们需要定义数组和索引，通过索引计算来定位节点的位置。

一般来说，初始化一个二叉树可以使用以下步骤：1. 创建树根节点，并赋初值。

2. 创建子节点，并到父节点。

3. 重复步骤2，直到创建完整个二叉树。

实习报告一、需求分析1、问题描述利用平衡二叉树实现一个动态查找表。

（1）实现动态查找表的三种基本功能：查找、插入和删除。

（2）初始时，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供选择。

每种操作均要提示输入关键字。

在查找时，如果查找的关键字不存在，则把其插入到平衡二叉树中。

每次插入或删除一个结点后，应更新平衡二叉树的显示。

（3）每次操作的关键字都要从文件中读取，并且关键字的集合限定为短整型数字{1，2，3······}，关键字出现的顺序没有限制，允许出现重复的关键字，并对其进行相应的提示。

（4）平衡二叉树的显示采用图形界面画出图形。

2、系统功能打开数据文件，用文件中的关键字来演示平衡二叉树操作的过程。

3、程序中执行的命令包括：（1）(L)oad from data file //在平衡的二叉树中插入关键字；（2）(A)ppend new record //在平衡的二叉树中查找关键字；（3）(U)pate special record //显示调整过的平衡二叉树；（4）(D)elete special record //删除平衡二叉树中的关键字；（5）(Q)uit //结束。

4、测试数据：平衡二叉树为：图 1 插入关键字10之前的平衡二叉树插入关键字：10；调整后：图 2 插入关键字10之后的平衡二叉树删除关键字：14；调整后：图 3 删除关键字14后的平衡二叉树查找关键字：11；输出：The data is here!图 3 查找关键字11后的平衡二叉树二、概要设计本次实验目的是为了实现动态查找表的三种基本功能：查找、插入和删除。

动态查找表可有不同的表示方法，在此次实验中主要是以平衡二叉树的结构来表示实现的，所以需要两个抽象数据类型：动态查找表和二叉树。

1、动态查找表的抽象数据类型定义为：ADT DynamicSearchTable{数据对象D ：D是具有相同特性的数据元素的集合。

数据结构二叉树实验报告二叉树是一种常用的数据结构，它在计算机科学中有着广泛的应用。

本文将介绍二叉树的定义、基本操作以及一些常见的应用场景。

一、二叉树的定义和基本操作二叉树是一种特殊的树形结构，它的每个节点最多有两个子节点。

一个节点的左子节点称为左子树，右子节点称为右子树。

二叉树的示意图如下：```A/ \B C/ \D E```在二叉树中，每个节点可以有零个、一个或两个子节点。

如果一个节点没有子节点，我们称之为叶子节点。

在上面的示例中，节点 D 和 E 是叶子节点。

二叉树的基本操作包括插入节点、删除节点、查找节点和遍历节点。

插入节点操作可以将一个新节点插入到二叉树中的合适位置。

删除节点操作可以将一个指定的节点从二叉树中删除。

查找节点操作可以在二叉树中查找指定的节点。

遍历节点操作可以按照一定的顺序遍历二叉树中的所有节点。

二、二叉树的应用场景二叉树在计算机科学中有着广泛的应用。

下面将介绍一些常见的应用场景。

1. 二叉搜索树二叉搜索树是一种特殊的二叉树，它的每个节点的值都大于其左子树中的节点的值，小于其右子树中的节点的值。

二叉搜索树可以用来实现快速的查找、插入和删除操作。

它在数据库索引、字典等场景中有着重要的应用。

2. 堆堆是一种特殊的二叉树，它的每个节点的值都大于或小于其子节点的值。

堆可以用来实现优先队列，它在任务调度、操作系统中的内存管理等场景中有着重要的应用。

3. 表达式树表达式树是一种用来表示数学表达式的二叉树。

在表达式树中，每个节点可以是操作符或操作数。

表达式树可以用来实现数学表达式的计算，它在编译器、计算器等场景中有着重要的应用。

4. 平衡二叉树平衡二叉树是一种特殊的二叉树，它的左子树和右子树的高度差不超过1。

平衡二叉树可以用来实现高效的查找、插入和删除操作。

它在数据库索引、自平衡搜索树等场景中有着重要的应用。

三、总结二叉树是一种常用的数据结构，它在计算机科学中有着广泛的应用。

本文介绍了二叉树的定义、基本操作以及一些常见的应用场景。

数学与计算机科学学院数据结构程序设计报告平衡二叉树学生姓名:学号:班级:指导老师:报告日期:1.题目与要求1). 问题的提出编写已个平衡二叉树，主要是对插入一个元素导致树不平衡的情况进行平衡化处理以及相关的处理。

2）设计的知识点队列的插入，删除，二叉树的建立于销毁，平衡树的平衡化，以及C语言中基础应用于结构等。

3）功能要求(1).通过不断插入的方式创建一棵平衡二叉树，包括输入结点的关键字和相关信息。

(2)按要求输出创建的平衡二叉树结点，包括顺序（中序）输出和按层次输出。

(3)插入新增的结点，若结点不存在则插入平衡二叉树，并进行相关调整。

(4)销毁二叉树。

(5)退出菜单界面如下：2.功能设计算法设计选择创建平衡二叉树后，利用循环不断插入结点，并进行调整，当输入节点为0时停止进入菜单界面。

在平横二叉树排序树BSTree上插入一个新的数据元素ｅ的递归算法可如下描述：（１）若BSTree为空树，则插入一个数据元素为e的新结点作为BSTree的根结点，树的深度增1；（２）若e的关键字和BSTree的根节点的关键字相等，则不进行插入；（３）若e的关键字小于BSTree的根结点的关键字，而且在其左子树中不存在和e形同的关键字的结点，则将e插入在其左子树上，并且当插入之后的左子树的深度加1时，分别就下列不同情况处理之：a.BSTree的跟结点的平衡因子为-1（右子树的深度大于左子树的深度）：则将跟结点的平衡因子更改为0，BBST的深度不变；b.BBST的根结点的平衡因子为0（左，右子树的深度相等）：则将根结点的平衡因子更改为1，BBST的深度增1；c.BBST的根结点的平衡因子为1（左子树的深度大于右子树的深度）：若BBST的左子树根结点的平衡因子为1，则需进行向左旋平衡处理，并且在右旋之后，将根节点和其右子树根节点的平衡因子更改为0，树的深度不变；若BBST的左子树根结点的平衡因子为-1，则需进行向左，向右的双向旋转平衡处理，并且在旋转处理之后，修改根结点和其左右子树的平衡因子，数的深度不变；（４）若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e有相同的关键字的的节点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加（+1）时，分别就不同情况处理之。

数据结构二叉树实验报告1. 引言二叉树是一种常见的数据结构，由节点（Node）和链接（Link）构成。

每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树在计算机科学中被广泛应用，例如在搜索算法中，二叉树可以用来快速查找和插入数据。

本实验旨在通过编写二叉树的基本操作来深入理解二叉树的特性和实现方式。

2. 实验内容2.1 二叉树的定义二叉树可以用以下方式定义：class TreeNode:def__init__(self, val):self.val = valself.left =Noneself.right =None每个节点包含一个值和两个指针，分别指向左子节点和右子节点。

根据需求，可以为节点添加其他属性。

2.2 二叉树的基本操作本实验主要涉及以下二叉树的基本操作：•创建二叉树：根据给定的节点值构建二叉树。

•遍历二叉树：将二叉树的节点按照特定顺序访问。

•查找节点：在二叉树中查找特定值的节点。

•插入节点：向二叉树中插入新节点。

•删除节点：从二叉树中删除特定值的节点。

以上操作将在下面章节详细讨论。

3. 实验步骤3.1 创建二叉树二叉树可以通过递归的方式构建。

以创建一个简单的二叉树为例：def create_binary_tree():root = TreeNode(1)root.left = TreeNode(2)root.right = TreeNode(3)root.left.left = TreeNode(4)root.left.right = TreeNode(5)return root以上代码创建了一个二叉树，根节点的值为1，左子节点值为2，右子节点值为3，左子节点的左子节点值为4，左子节点的右子节点值为5。

3.2 遍历二叉树二叉树的遍历方式有多种，包括前序遍历、中序遍历和后序遍历。

以下是三种遍历方式的代码实现：•前序遍历：def preorder_traversal(root):if root:print(root.val)preorder_traversal(root.left)preorder_traversal(root.right)•中序遍历：def inorder_traversal(root):if root:inorder_traversal(root.left)print(root.val)inorder_traversal(root.right)•后序遍历：def postorder_traversal(root):if root:postorder_traversal(root.left)postorder_traversal(root.right)print(root.val)3.3 查找节点在二叉树中查找特定值的节点可以使用递归的方式实现。

数据结构二叉树综合实验报告数据结构二叉树综合实验报告1.引言在计算机科学中，二叉树是一种常见的数据结构，它由节点组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树具有广泛的应用场景，如在搜索算法、图形处理和编译器设计中等。

本报告旨在介绍我们进行的二叉树综合实验，包括实验目的、实验过程中的具体步骤和实验结果分析等。

2.实验目的本实验的主要目的是通过设计和实现二叉树的基本操作，加深对二叉树的理解，并掌握二叉树的基本算法和应用。

具体的实验目标包括：- 熟悉二叉树的基本概念和性质；- 掌握二叉树的创建、插入和删除操作；- 实现二叉树的遍历算法，包括前序、中序和后序遍历；- 实现二叉树的搜索功能；- 进行基于二叉树的排序实验。

3.实验步骤3.1 二叉树的创建首先，我们需要创建一个空的二叉树。

通过定义二叉树的节点结构和指针，可以动态地分配内存空间用于创建节点，并建立节点之间的连接关系。

3.2 节点的插入在已有的二叉树中，我们可以向其中插入新的节点。

插入操作通常涉及到比较节点的键值大小，然后根据比较结果决定插入新节点的位置。

3.3 节点的删除除了插入节点，我们也可能需要从二叉树中删除节点。

删除操作通常需要考虑节点的子节点情况，例如，被删除的节点是否有左子节点、右子节点或者同时存在。

3.4 二叉树的遍历二叉树的遍历操作可以按照不同的顺序进行，包括前序（根-左-右）、中序（左-根-右）和后序（左-右-根）遍历。

在实验中，我们需要实现这三种遍历算法，并观察它们的输出结果。

3.5 二叉树的搜索在已有的二叉树中，我们可根据节点的键值进行搜索操作。

通过比较键值，我们可以判断在左子树或右子树中进行进一步的搜索，直至找到目标节点或确定目标节点不存在于二叉树中。

3.6 基于二叉树的排序二叉树可以作为一种排序算法的基础结构。

在实验中，我们可以通过节点的插入操作构建一个包含数据集的二叉树，并通过中序遍历获取有序的数据。

数据结构二叉树实验报告总结一、实验目的本次实验的主要目的是通过对二叉树的学习和实践，掌握二叉树的基本概念、性质和遍历方式，加深对数据结构中树形结构的理解。

二、实验内容1. 二叉树的基本概念和性质在本次实验中，我们首先学习了二叉树的基本概念和性质。

其中，二叉树是由节点组成的有限集合，并且每个节点最多有两个子节点。

同时，我们还学习了二叉树的高度、深度、层数等概念。

2. 二叉树的遍历方式在了解了二叉树的基本概念和性质之后，我们开始学习如何遍历一个二叉树。

在本次实验中，我们主要学习了三种遍历方式：前序遍历、中序遍历和后序遍历。

其中，前序遍历指先访问节点自身再访问左右子节点；中序遍历指先访问左子节点再访问自身和右子节点；后序遍历指先访问左右子节点再访问自身。

3. 二叉搜索树除了以上内容之外，在本次实验中我们还学习了一种特殊的二叉树——二叉搜索树。

二叉搜索树是一种特殊的二叉树，它的每个节点都满足左子节点小于该节点，右子节点大于该节点的性质。

由于这个性质，二叉搜索树可以被用来进行快速查找、排序等操作。

三、实验过程1. 实现二叉树的遍历方式为了更好地理解和掌握二叉树的遍历方式，我们首先在编程环境中实现了前序遍历、中序遍历和后序遍历。

在代码编写过程中，我们需要考虑如何递归地访问每个节点，并且需要注意访问顺序。

2. 实现二叉搜索树为了更好地理解和掌握二叉搜索树的特性和操作，我们在编程环境中实现了一个简单的二叉搜索树。

在代码编写过程中，我们需要考虑如何插入新节点、删除指定节点以及查找目标节点等操作。

3. 实验结果分析通过对代码运行结果进行分析，我们可以清晰地看到每个遍历方式所得到的结果以及对应的顺序。

同时，在对二叉搜索树进行操作时，我们也可以看到不同操作所产生的不同结果。

四、实验总结通过本次实验，我们进一步加深了对二叉树的理解和掌握，学习了二叉树的遍历方式以及二叉搜索树的特性和操作。

同时，在编程实践中，我们也进一步熟悉了代码编写和调试的过程。

二叉树的基本操作与实现实验报告二叉树是一种重要的数据结构，在计算机科学领域中被广泛应用。

本实验将介绍二叉树的基本操作与实现，并给出相应的实验报告。

一、引言二叉树是一种特殊的树状结构，每个节点至多有两个子节点。

二叉树有许多重要的特性，如平衡二叉树、二叉树等，应用广泛。

在本实验中，我们将介绍二叉树的基本操作和实现。

二、实验目的1.掌握二叉树的基本概念和特性；2.熟悉二叉树的基本操作，包括创建、插入、删除、遍历等；3.学会使用编程语言实现二叉树的基本操作。

三、实验内容本实验主要包括以下内容：1.二叉树的定义和基本概念；2.二叉树的基本操作，包括创建、插入、删除、遍历等；3.使用编程语言实现二叉树的基本操作；4.测试和验证二叉树的基本操作的正确性。

四、实验步骤1.二叉树的定义和基本概念二叉树是一种树状结构，每个节点至多有两个子节点。

二叉树的每个节点包含一个数据项和指向左子树和右子树的指针。

二叉树的特性有很多，如完全二叉树、平衡二叉树、二叉树等。

2.二叉树的基本操作（1）创建二叉树：可以通过手动输入节点数据来创建二叉树，也可以通过读取文件中的数据来创建二叉树。

（2）插入节点：在指定位置插入一个新节点。

（3）删除节点：删除指定位置的节点。

（4）遍历二叉树：有前序遍历、中序遍历和后序遍历三种遍历方式。

3.使用编程语言实现二叉树的基本操作实现二叉树的基本操作可以使用编程语言来完成。

我们可以定义一个二叉树的结构体，包含节点数据和指向左右子树的指针。

然后根据具体的需求，实现相应的操作函数。

4.测试和验证二叉树的基本操作的正确性在完成二叉树的基本操作后，我们可以编写测试代码来验证操作的正确性。

通过创建二叉树，并进行插入、删除和遍历操作，观察输出结果是否符合预期。

五、实验结果与分析在完成二叉树的基本操作后，我们可以进行测试和验证。

通过输出二叉树的遍历结果，比对预期结果来判断操作是否正确。

同时，我们还可以观察二叉树的结构和特性，如是否满足平衡二叉树或二叉树的条件。

数据结构实验报告二叉树二叉树是一种重要的数据结构，广泛应用于计算机科学和算法设计中。

在本次实验中，我们通过实际编程实践，深入理解了二叉树的基本概念、性质和操作。

一、二叉树的定义和基本性质二叉树是一种特殊的树结构，每个节点最多有两个子节点。

它具有以下基本性质：1. 根节点：二叉树的顶部节点称为根节点，它没有父节点。

2. 子节点：每个节点最多有两个子节点，分别称为左子节点和右子节点。

3. 叶节点：没有子节点的节点称为叶节点。

4. 深度：从根节点到某个节点的路径长度称为该节点的深度。

5. 高度：从某个节点到其叶节点的最长路径长度称为该节点的高度。

6. 层次遍历：按照从上到下、从左到右的顺序遍历二叉树的节点。

二、二叉树的实现在本次实验中，我们使用C++语言实现了二叉树的基本操作，包括创建二叉树、插入节点、删除节点、查找节点等。

通过这些操作，我们可以方便地对二叉树进行增删改查。

三、二叉树的遍历二叉树的遍历是指按照某种顺序访问二叉树的所有节点。

常用的遍历方式有三种：前序遍历、中序遍历和后序遍历。

1. 前序遍历：先访问根节点，然后依次递归遍历左子树和右子树。

2. 中序遍历：先递归遍历左子树，然后访问根节点，最后递归遍历右子树。

3. 后序遍历：先递归遍历左子树，然后递归遍历右子树，最后访问根节点。

四、二叉树的应用二叉树在计算机科学和算法设计中有广泛的应用。

以下是一些常见的应用场景：1. 二叉搜索树：二叉搜索树是一种特殊的二叉树，它的左子树的值都小于根节点的值，右子树的值都大于根节点的值。

它可以高效地支持插入、删除和查找操作，常用于有序数据的存储和检索。

2. 堆：堆是一种特殊的二叉树，它的每个节点的值都大于（或小于）其子节点的值。

堆常用于实现优先队列等数据结构。

3. 表达式树：表达式树是一种用二叉树表示数学表达式的方法。

通过对表达式树的遍历，可以实现对数学表达式的计算。

4. 平衡树：平衡树是一种特殊的二叉树，它的左右子树的高度差不超过1。

数据结构设计性实验报告课程名称数据结构实验■题目名称平衡二叉树_____________ 学生学院_ 计算机学院 _______________专业班级_学号_________________学生姓名___________________指导教师______________2015年6月14日目录一、设计任务、要求以及所用环境及工具. (4)实验设计任务. (4)实验要求. (4)编程环境. (4)抽象数据类型及接口简要描述. (5)抽象数据类型. (5)接口简要描述. (7)算法设计 (8)程序测试 (17)测试代码. (17)测试结果. (18)测试分析. (20)思考与小结 (21)设计任务、要求以及所用环境及工具实验设计任务以教材中讨论的各种抽象数据类型为对象，利用C语言的数据类型表示和实现其中某个实验要求实验要求如下：1 •首先了解设计的任务，然后根据自己的基础和能力从中选择一题。

一般来说，选择题目应以在规定的时间内能完成，并能得到应有的锻炼为原则。

若学生对教材以外的相关题目较感兴趣，希望选作实验的题目时，应征得指导教师的认可，并写出明确的抽象数据类型定义及说明。

2. 实验前要作好充分准备，包括：理解实验要求，掌握辅助工具的使用，了解该抽象数据类型的定义及意义，以及其基本操作的算法并设计合理的存储结构。

3. 实验时严肃认真，要严格按照要求独立进行设计，不能随意更改。

注意观察并记录各种错误现象，纠正错误，使程序满足预定的要求，实验记录应作为实验报告的一部分。

4. 实验后要及时总结，写出实验报告，并附所打印的问题解答、程序清单，所输入的数据及相应的运行结果。

编程环境抽象数据类型及接口简要描述本次数据结构实验设计我选择的是二叉平衡树 （AVL ）,使用C++面向对象编程语言实现。

利用C++泛型编程技术完成 AVL 类AVLTree 。

抽象数据类型1. 平衡二叉树结点的 ADT 为： template <type name T> class AVLTreeNode {public :T _key; II 结点关键字int _bf;II 结点平衡因子 AVLTreeNode *_lchild ; II 结点的左孩指针 AVLTreeNode *_rchild ; II 结点的右孩指针II 构造函数AVLTreeNode(T key ‘AVLTreeNode *lchild , AVLTreeNode *rchild :_key(key),_l child(lchild),_rchild(rchild),_bf(bf){};};R L：tzdHET募権怪 4.*___ J □"三耙■耐3E P|C*<底总¥i4 C4 +ATk Viitad C--4CLU和mi*ECiy.i G91D.EiW• La 话亦需 ▼Z ••穷A下完成。

《数据结构〉课程实验报告实验名称树与二叉树实验序号5实验日期姓名院系班级学号指导教师成绩专业教师评语一、实验目得与要求(1)掌握树得相关概念，包括树、结点得度、树得度、分支结点、叶子结点、儿子结点、双亲结点、树得深度、森林等定义。

(2)掌握树得表示，包括树形表示法、文氏图表示法、凹入表示法与括号表示法等。

(3)掌握二叉树得概念，包括二叉树、满二叉树与完全二叉树得定义。

(4)掌握二叉树得性质。

(5)重点掌握二叉树得存储结构，包括二叉树顺序存储结构与链式存储结构。

(6)重点掌握二叉树得基本运算与各种遍历算法得实现。

(7)掌握线索二叉树得概念与相关算法得实现。

(8)掌握哈夫曼树得定义、哈夫曼树得构造过程与哈夫曼编码产生方法。

(9)掌握并查集得相关概念与算法。

(1 0)灵活掌握运用二叉树这种数据结构解决一些综合应用问题。

二、实验项目摘要1编写一程序，实现二叉树得各种基本运算，并在此基础上设计一个主程序完成如下功能：(1)输出二叉树b;(2)输出H结点得左、右孩子结点值；(3)输出二叉树b得深度；(4)输出二叉树b得宽度；(5)输出二叉树b得结点个数；(6)输出二叉树b得叶子结点个数。

2编写一程序，实现二叉树得先序遍历、中序遍历与后序遍历得各种递归与非递归算法，以及层次遍历得算法。

三、实验预习内容二叉树存储结构，二叉树基本运算（创建二叉树、寻找结点、找孩子结点、求高度、输出二叉树）三、实验结果与分析7-1#incl u d e < s tdio、h>#incl u d e<m a1 l o c、h># d e f in e M axS i z e 100typedef cha r E l emT y p e;ty p ed e f struct n o d e｛o ElemTy p e data;。

str u c t n ode * 1 c h i 1 d ;0struct no d e * r chi l d;0}BT N ode;void Cr e a teBTNod e(BTNod e *&b,c h ar *s t r)｛o B TNod e* S t[M a x S ize] , *p=NULL;o i n t t o p=-1,k,j = 0:ch a r ch;b=N U L L;oo0ch= s tr廿］；wh i l e C ch!='\O')叶s wit c h(ch)｛o ca s e'(':to p ++; St[t o p]=p;k=l;b rea k;。

一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）首先构造二叉树的存储结构，用data存储当前节点的值，分别用*lchild，*rchild 表示该节点的左右孩子。

然后应用BiTree Create函数，根据用户的输入构造二叉树，当输入#时表示没有孩子。

采用递归的思想构造Preorder，Inorder，Postorder函数，分别实现二叉树的先序，中序，和后序的遍历。

然后编写了Sumleaf，Depth函数，来求叶子节点的数目和二叉树的深度。

二、【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系）二叉树的存储结构：typedef struct BiTNode{char data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;子程序模块：BiTree Create(BiTree T){char ch;ch=getchar();if(ch=='#')T=NULL;else{if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))printf("Error!");T->data=ch;T->lchild=Create(T->lchild);T->rchild=Create(T->rchild);}return T;}void Preorder(BiTree T){if(T){printf("%c",T->data);Preorder(T->lchild);Preorder(T->rchild);}}int Sumleaf(BiTree T){int sum=0,m,n;if(T){if((!T->lchild)&&(!T->rchild)) sum++;m=Sumleaf(T->lchild);sum+=m;n=Sumleaf(T->rchild);sum+=n;}return sum;}void Inorder(BiTree T) {if(T){Inorder(T->lchild); printf("%c",T->data); Inorder(T->rchild); }}void Postorder(BiTree T) {if(T){Postorder(T->lchild); Postorder(T->rchild); printf("%c",T->data); }}int Depth(BiTree T){int dep=0,depl,depr;if(!T)dep=0;else{depl=Depth(T->lchild);depr=Depth(T->rchild);dep=1+(depl>depr?depl:depr);}return dep;}主程序模块：int main(){BiTree T = 0;int sum,dep;printf("请输入你需要建立的二叉树\n");printf("例如输入序列ABC##DE#G##F###（其中的#表示空）\n并且输入过程中不要加回车\n输入完之后可以按回车退出\n");T=Create(T);printf("先序遍历的结果是：\n");Preorder(T);printf("\n");printf("中序遍历的结果是：\n");Inorder(T);printf("\n");printf("后序遍历的结果是：\n");Postorder(T);printf("\n");printf("统计的叶子数：\n");sum=Sumleaf(T);printf("%d",sum);printf("\n统计树的深度：\n");dep=Depth(T);printf("\n%d\n",dep);}三、【实现描述（Implement）】(30%)（本部分应包括：抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。