树和二叉树的实验报告

二叉排序树的实验报告二叉排序树的实验报告引言：二叉排序树（Binary Search Tree，简称BST）是一种常用的数据结构，它将数据按照一定的规则组织起来，便于快速的查找、插入和删除操作。

本次实验旨在深入了解二叉排序树的原理和实现，并通过实验验证其性能和效果。

一、实验背景二叉排序树是一种二叉树，其中每个节点的值大于其左子树的所有节点的值，小于其右子树的所有节点的值。

这种特性使得在二叉排序树中进行查找操作时，可以通过比较节点的值来确定查找的方向，从而提高查找效率。

二、实验目的1. 理解二叉排序树的基本原理和性质；2. 掌握二叉排序树的构建、插入和删除操作；3. 验证二叉排序树在查找、插入和删除等操作中的性能和效果。

三、实验过程1. 构建二叉排序树首先，我们需要构建一个空的二叉排序树。

在构建过程中，我们可以选择一个节点作为根节点，并将其他节点插入到树中。

插入节点时，根据节点的值与当前节点的值进行比较，如果小于当前节点的值，则将其插入到当前节点的左子树中；如果大于当前节点的值，则将其插入到当前节点的右子树中。

重复这个过程，直到所有节点都被插入到树中。

2. 插入节点在已有的二叉排序树中插入新的节点时，我们需要遵循一定的规则。

首先，从根节点开始，将新节点的值与当前节点的值进行比较。

如果小于当前节点的值，则将其插入到当前节点的左子树中；如果大于当前节点的值，则将其插入到当前节点的右子树中。

如果新节点的值与当前节点的值相等，则不进行插入操作。

3. 删除节点在二叉排序树中删除节点时，我们需要考虑不同的情况。

如果要删除的节点是叶子节点，即没有左右子树，我们可以直接删除该节点。

如果要删除的节点只有一个子树，我们可以将子树连接到要删除节点的父节点上。

如果要删除的节点有两个子树，我们可以选择将其右子树中的最小节点或左子树中的最大节点替代该节点，并删除相应的替代节点。

四、实验结果通过对二叉排序树的构建、插入和删除操作的实验，我们得到了以下结果：1. 二叉排序树可以高效地进行查找操作。

树和二叉树一、实验目的1.掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。

2.掌握用指针类型描述、访问和处理二叉树的运算。

二、实验要求1.认真阅读和掌握本实验的程序。

2.上机运行本程序。

3.保存和打印出程序的运行结果，并结合程序进行分析。

4.按照二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。

三、实验内容1.输入字符序列，建立二叉链表。

2.按先序、中序和后序遍历二叉树（递归算法）。

3.按某种形式输出整棵二叉树。

4.求二叉树的高度。

5.求二叉树的叶节点个数。

6.交换二叉树的左右子树。

7.借助队列实现二叉树的层次遍历。

8.在主函数中设计一个简单的菜单，分别调试上述算法。

为了实现对二叉树的有关操作，首先要在计算机中建立所需的二叉树。

建立二叉树有各种不同的方法。

一种方法是利用二叉树的性质5来建立二叉树，输入数据时要将节点的序号（按满二叉树编号）和数据同时给出：（序号，数据元素0）。

另一种方法是主教材中介绍的方法，这是一个递归方法，与先序遍历有点相似。

数据的组织是先序的顺序，但是另有特点，当某结点的某孩子为空时以字符“#”来充当，也要输入。

若当前数据不为“#”，则申请一个结点存入当前数据。

递归调用建立函数，建立当前结点的左右子树。

四、解题思路1、先序遍历：○1访问根结点，○2先序遍历左子树，○3先序遍历右子树2、中序遍历：○1中序遍历左子树，○2访问根结点，○3中序遍历右子树3、后序遍历：○1后序遍历左子树，○2后序遍历右子树，○3访问根结点4、层次遍历算法：采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。

因为队列的特点是先进后出，所以能够达到按层次遍历二叉树的目的。

五、程序清单#include<stdio.h>#include<stdlib.h>#define M 100typedef char Etype; //定义二叉树结点值的类型为字符型typedef struct BiTNode //树结点结构{Etype data;struct BiTNode *lch,*rch;}BiTNode,*BiTree;BiTree que[M];int front=0,rear=0;//函数原型声明BiTNode *creat_bt1();BiTNode *creat_bt2();void preorder(BiTNode *p);void inorder(BiTNode *p);void postorder(BiTNode *p);void enqueue(BiTree);BiTree delqueue( );void levorder(BiTree);int treedepth(BiTree);void prtbtree(BiTree,int);void exchange(BiTree);int leafcount(BiTree);void paintleaf(BiTree);BiTNode *t;int count=0;//主函数void main(){char ch;int k;do{printf("\n\n\n");printf("\n===================主菜单===================");printf("\n\n 1.建立二叉树方法1");printf("\n\n 2.建立二叉树方法2");printf("\n\n 3.先序递归遍历二叉树");printf("\n\n 4.中序递归遍历二叉树");printf("\n\n 5.后序递归遍历二叉树");printf("\n\n 6.层次遍历二叉树");printf("\n\n 7.计算二叉树的高度");printf("\n\n 8.计算二叉树中叶结点个数");printf("\n\n 9.交换二叉树的左右子树");printf("\n\n 10.打印二叉树");printf("\n\n 0.结束程序运行");printf("\n============================================");printf("\n 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)");scanf("%d",&k);switch(k){case 1:t=creat_bt1( );break; //调用性质5建立二叉树算法case 2:printf("\n请输入二叉树各结点值:");fflush(stdin);t=creat_bt2();break; //调用递归建立二叉树算法case 3:if(t){printf("先序遍历二叉树:");preorder(t);printf("\n");}else printf("二叉树为空!\n");break;case 4:if(t){printf("中序遍历二叉树:");inorder(t);printf("\n");}else printf("二叉树为空!\n");break;case 5:if(t){printf("后序遍历二叉树:");postorder(t);printf("\n");}else printf("二叉树为空!\n");break;case 6:if(t){printf("层次遍历二叉树：");levorder(t);printf("\n");}else printf("二叉树为空！\n");break;case 7:if(t){printf("二叉树的高度为：%d",treedepth(t));printf("\n");}else printf("二叉树为空！\n");break;case 8:if(t){printf("二叉树的叶子结点数为：%d\n",leafcount(t));printf("二叉树的叶结点为：");paintleaf(t);printf("\n");}else printf("二叉树为空！\n");break;case 9:if(t){printf("交换二叉树的左右子树：\n");exchange(t);prtbtree(t,0);printf("\n");}else printf("二叉树为空！\n");break;case 10:if(t){printf("逆时针旋转90度输出的二叉树：\n");prtbtree(t,0);printf("\n");}else printf("二叉树为空！\n");break;case 0:exit(0);} //switch}while(k>=1&&k<=10);printf("\n再见！按回车键，返回…\n");ch=getchar();} //main//利用二叉树性质5，借助一维数组V建立二叉树BiTNode *creat_bt1(){ BiTNode *t,*p,*v[20];int i,j;Etype e;/*输入结点的序号i、结点的数据e*/printf("\n请输入二叉树各结点的编号和对应的值（如1，a）：");scanf("%d,%c",&i,&e);while(i!=0&&e!='#') //当i为0，e为'#'时，结束循环{p=(BiTNode*)malloc(sizeof(BiTNode));p->data=e;p->lch=NULL;p->rch=NULL;v[i]=p;if(i==1)t=p; //序号为1的结点是根else{j=i/2;if(i%2==0)v[j]->lch=p; //序号为偶数，作为左孩子else v[j]->rch=p; //序号为奇数，作为右孩子}printf("\n请继续输入二叉树各结点的编号和对应的值：");scanf("%d,%c",&i,&e);}return(t);}//creat_bt1;//模仿先序递归遍历方法，建立二叉树BiTNode *creat_bt2(){BiTNode *t;Etype e;scanf("%c",&e);if(e=='#')t=NULL; //对于'#'值，不分配新结点else{t=(BiTNode *)malloc(sizeof(BiTNode));t->data=e;t->lch=creat_bt2(); //左孩子获得新指针值t->rch=creat_bt2(); //右孩子获得新指针值}return(t);} //creat_bt2//先序递归遍历二叉树void preorder(BiTNode *p){if(p){printf("%3c",p->data);preorder(p->lch);preorder(p->rch);}} //preorder//中序递归遍历二叉树void inorder(BiTNode *p){if(p){inorder(p->lch);printf("%3c",p->data);inorder(p->rch);}} //inorder//后序递归遍历二叉树void postorder(BiTNode *p){ if(p){ postorder(p->lch);postorder(p->rch);printf("%3c",p->data);}} //postordervoid enqueue(BiTree T){if(front!=(rear+1)%M){rear=(rear+1)%M;que[rear]=T;}}BiTree delqueue( ){if(front==rear)return NULL;front=(front+1)%M;return(que[front]);}void levorder(BiTree T) //层次遍历二叉树{BiTree p;if(T){enqueue(T);while(front!=rear){p=delqueue( );printf("%3d",p->data);if(p->lch!=NULL)enqueue(p->lch);if(p->rch!=NULL)enqueue(p->rch);}}}int treedepth(BiTree bt) //计算二叉树的高度{int hl,hr,max;if(bt!=NULL){ hl=treedepth(bt->lch);hr=treedepth(bt->rch);max=(hl>hr)?hl:hr;return (max+1);}else return (0);}void prtbtree(BiTree bt,int level) //逆时针旋转90度输出二叉树树形{int j;if(bt){prtbtree(bt->rch,level+1);for(j=0;j<=6*level;j++)printf(" ");printf("%c\n",bt->data);prtbtree(bt->lch,level+1);}}void exchange(BiTree bt) //交换二叉树左右子树{BiTree p;if(bt){p=bt->lch;bt->lch=bt->rch;bt->rch=p;exchange(bt->lch);exchange(bt->rch);}}int leafcount(BiTree bt) //计算叶结点数{if(bt!=NULL){leafcount(bt->lch);leafcount(bt->rch);if((bt->lch==NULL)&&(bt->rch==NULL))count++;}return(count);}void paintleaf(BiTree bt) //输出叶结点{if(bt!=NULL){if(bt->lch==NULL&&bt->rch==NULL)printf("%3c",bt->data);paintleaf(bt->lch);paintleaf(bt->rch);}}图11.2所示二叉树的输入数据顺序应该是：abd#g###ce#h##f##。

实验报告课程：数据结构（c语言）实验名称：二叉树的构建、基本操作和遍历系别：数字媒体技术实验日期：专业班级：媒体161 组别：无：学号：实验报告容验证性实验一、预习准备：实验目的：1、熟练掌握二叉树的结构特性，熟悉二叉树的各种存储结构的特点及适用围；2、熟练掌握二叉树的遍历方法及遍历算法；3、掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。

实验环境：Widows操作系统、VC6.0实验原理：1.定义：树：树(tree)是n(n>0)个结点的有限集T，其中，有且仅有一个特定的结点，称为树的根(root)。

当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)二叉树：二叉树是n(n>=0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。

哈夫曼树: 最优二叉树——赫夫曼树设有n个权值{w1,w2,……wn}，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的二叉树叫Huffman树。

2. 特点：树：树中至少有一个结点——根树中各子树是互不相交的集合二叉树：每个结点至多有二棵子树(即不存在度大于2的结点)二叉树的子树有左、右之分，且其次序不能任意颠倒哈夫曼树：一棵有n个叶子结点的Huffman树有2n-1个结点采用顺序存储结构——动态分配数组存储3. 表示：遍历二叉树：先序遍历：先访问根结点,然后分别先序遍历左子树、右子树中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树后序遍历：先后序遍历左、右子树，然后访问根结点 按层次遍历：从上到下、从左到右访问各结点 构造Huffman 树的方法——Huffman 算法（1) 根据给定的n 个权值{w1,w2,……wn}，构造n 棵只有根 结点的二叉树，令起权值为wj ；(2) 在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和；(3) 在森林中删除这两棵树，同时将新得到的二叉树加入森林中重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。

实习报告实习内容：二叉树遍历实习时间：2023实习单位：某高校计算机实验室一、实习目的本次实习的主要目的是通过实现二叉树的遍历，加深对二叉树数据结构的理解，掌握二叉树的常见操作，提高编程能力。

二、实习内容1. 理解二叉树的基本概念和性质，包括节点之间的关系、树的深度、高度等。

2. 掌握二叉树的存储结构，包括顺序存储和链式存储。

3. 实现二叉树的前序遍历、中序遍历和后序遍历。

4. 通过实际编程，验证二叉树遍历的正确性。

三、实习过程1. 二叉树的基本概念和性质：二叉树是一种非线性的数据结构，每个节点最多有两个子节点。

节点之间的关系包括父子关系、兄弟关系等。

树的深度是指从根节点到最远叶子节点的最长路径上的边数，高度是指从根节点到最远叶子节点的最长路径上的边数加1。

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

顺序存储结构使用数组来实现，每个节点存储在数组的一个位置中，节点之间的父子关系通过数组下标来表示。

链式存储结构使用链表来实现，每个节点包含数据域和两个指针域，分别指向左子节点和右子节点。

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

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

前序遍历是指先访问根节点，然后递归遍历左子树，最后递归遍历右子树。

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

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

4. 编程实现：根据二叉树的存储结构和遍历方法，编写C语言程序实现二叉树的前序遍历、中序遍历和后序遍历。

程序中使用递归函数来实现遍历操作，通过建立链式存储结构，验证遍历的正确性。

四、实习心得通过本次实习，我对二叉树的数据结构有了更深入的了解，掌握了二叉树的存储方式和常见操作。

在实现二叉树遍历的过程中，我学会了如何使用递归函数解决问题，提高了编程能力。

同时，通过实际编程验证了二叉树遍历的正确性，增强了对算法理解的信心。

西安交通大学实验报告课程数据结构（C语言描述）实验报告名称树与二叉树上机实验系别专业班级姓名学号一．实验目的掌握二叉树的建立方法；理解二叉树的结构和前序遍历、中序遍历、后序遍历及按层次遍历的方法；学会用二叉树解决问题。

二．实验内容（－）实验题目一：设树中结点的定义为：struct BTreeNode {ElemType data;struct BTreeNode* left;struct BTreeNode* right;};下面是根据二叉树的前序序列来建立二叉树的子程序：void CreatBiTree(struct BTreeNode** T){char ch;scanf("\n%c",&ch);if(ch=='#') *T=NULL; /* “#” 代表空子树*/else {(*T)=malloc(sizeof(struct BTreeNode));(*T)->data=ch;CreatBiTree(&((*T)->left));CreatBiTree(&((*T)->right));}}设输入该二叉树的前序序列为：ABC##DE#G##F##HI##J#K##（#代表空子树）请编程完成下列任务：⑴请根据此输入来建立该二叉树，并输出该二叉树的前序、中序和后序序列，⑵按层次遍历的方法来输出该二叉树按层次遍历的序列；⑶求该二叉树的高度；⑷交换该二叉树的左右子树,并输出交换后新的二叉树中序遍历的结果；1.要点分析理解并正确运用二叉树的结构和遍历方法。

前序序列：ABC##DE#G##F##HI##J#K## 表示的二叉树为：所以根据二叉树的结构可知：其前序序列为：ABCDEGFHIJK中序序列为：CBEGDFAIHJK后序序列为：CGEFDBIKJHA按层次遍历的结果为：ABHCDIJEFKG交换左右子树后中序遍历的结果为：KJHIAFDGEBC深度为5。

实验报告一：预习要求预习树和二叉树的存储结构、以递归为基本思想的相应遍历操作。

二：实验目的1、通过实验，掌握二叉树的建立与存储方法。

2、掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。

3、掌握用指针类型描述、访问和处理二叉树的运算。

4、理解huffman编解码的算法三：实验内容以括号表示法输入一棵二叉树，编写算法建立二叉树的二叉链表结构；编写先序、中序、后序、层次遍历二叉树的算法；编写算法计算二叉树的结点数，叶子结点数，以及二叉树的深度。

四:实验原理及试验方法ADT BinaryTree{数据对象：D：D是具有相同特征的数据元素的集合数据结构：R：若D= 空集，则R=空集，称BinaryTree为空二叉树；若D不等于空集，则R={H}，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D-{root}不等于空集，则存在D-{root}={D1,Dr},且D1∩Dr=空集；（3）若D1不等于空集，则D1中存在唯一的元素x1，<root,x1>∈H，且存在D1上的关系H1包含于H；若Dr≠空集，则Dr中存在唯一的元素xr,<root,xr>∈H，且存在Dr上的关系Hr包含于H；H={<root,x1>,<root,xr>,H1,Hr};（4） (D1,{H1})是一颗符合本定义的二叉树，称为根的左子树，（Dr,{Hr}）是一颗符合本定义的二叉树，称为根的右子树。

基本操作P：CreateBiTree(&T,definition);初始条件：definition给出二叉树的定义。

操作结果：按definition构造二叉树T。

PreOrderTraverse(T);初始条件：二叉树T存在。

操作结果：先序遍历T 。

InOrderTraverse(T);初始条件：二叉树T存在。

操作结果：中序遍历T。

PostOrderTraverse(T);初始条件：二叉树T存在。

《数据结构》实验报告题目: 树和二叉树一、用二叉树来表示代数表达式（一）需求分析输入一个正确的代数表达式, 包括数字和用字母表示的数, 运算符号+ - * / ^ =及括号。

系统根据输入的表达式建立二叉树, 按照先括号里面的后括号外面的, 先乘后除的原则, 每个节点里放一个数字或一个字母或一个操作符, 括号不放在节点里。

分别先序遍历, 中序遍历, 后序遍历此二叉树, 并输出表达式的前缀式, 中缀式和后缀式。

（二）系统设计1.本程序中用到的所有抽象数据类型的定义；typedef struct BiNode //二叉树的存储类型{char s[20];struct BiNode *lchild,*rchild;}BiTNode,*BiTree;2.主程序的流程以及各程序模块之间的层次调用关系, 函数的调用关系图:3. 列出各个功能模块的主要功能及输入输出参数void push(char cc)初始条件: 输入表达式中的某个符号操作结果: 将输入的字符存入buf数组中去BiTree Create_RTree()初始条件: 给出二叉树的定义表达式操作结果：构造二叉树的右子树, 即存储表达式等号右侧的字符组BiTree Create_RootTree()初始条件: 给出二叉树的定义表达式操作结果：构造存储输入表达式的二叉树, 其中左子树存储‘X’, 根节点存储‘：=’void PreOrderTraverse(BiTree T)初始条件: 二叉树T存在操作结果：先序遍历T, 对每个节点调用函数Visit一次且仅一次void InOrderTraverse(BiTree T)初始条件: 二叉树T存在操作结果：中序遍历T, 对每个节点调用函数Visit一次且仅一次void PostOrderTraverse(BiTree T)初始条件: 二叉树T存在操作结果：后序遍历T, 对每个节点调用函数Visit一次且仅一次int main()主函数, 调用各方法, 操作成功后返回0（三）调试分析调试过程中还是出现了一些拼写错误, 经检查后都能及时修正。

树和二叉树的实验报告树和二叉树的实验报告一、引言树和二叉树是计算机科学中常用的数据结构，它们在各种算法和应用中都有广泛的应用。

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

二、树的构建与遍历1. 树的概念和特性树是一种非线性的数据结构，由节点和边组成。

每个节点可以有零个或多个子节点，其中一个节点没有父节点的称为根节点。

树的特点包括层次结构、唯一根节点和无环等。

2. 树的构建在本实验中，我们使用Python语言构建了一棵树。

通过定义节点类和树类，我们可以方便地创建树的实例，并添加节点和连接节点之间的边。

3. 树的遍历树的遍历是指按照一定顺序访问树中的所有节点。

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

我们在实验中实现了这三种遍历方式，并观察了它们的输出结果。

三、二叉树的实现与应用1. 二叉树的概念和特性二叉树是一种特殊的树，每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树的特点包括唯一根节点、每个节点最多有两个子节点和子节点的顺序等。

2. 二叉树的实现我们使用Python语言实现了二叉树的数据结构。

通过定义节点类和二叉树类，我们可以创建二叉树的实例，并实现插入节点、删除节点和查找节点等操作。

3. 二叉树的应用二叉树在实际应用中有很多用途。

例如，二叉搜索树可以用于实现快速查找和排序算法。

AVL树和红黑树等平衡二叉树可以用于高效地插入和删除操作。

我们在实验中实现了这些应用，并通过实际操作验证了它们的效果。

四、实验结果与讨论通过实验，我们成功构建了树和二叉树的数据结构，并实现了它们的基本操作。

通过观察和分析实验结果，我们发现树和二叉树在各种算法和应用中的重要性和灵活性。

树和二叉树的特性使得它们适用于解决各种问题，例如搜索、排序、图算法等。

同时，我们也发现了一些问题和挑战，例如树的平衡性和节点的插入和删除操作等。

这些问题需要进一步的研究和优化。

五、总结本实验通过实际操作和观察，深入了解了树和二叉树的特性和操作。

实验报告实验：树和二叉树一、实验目的：1.掌握二叉树的存储实现2.掌握二叉树的遍历思想3.掌握二叉树的常见算法的程序实现二、实验内容：1.编写函数,输入字符序列,建立二叉树的二叉链表。

2.编写函数,实现二叉树的中序递归遍历算法。

(最好也能实现前缀和后缀遍历算法)3.编写函数,实现二叉树的中序非递归遍历算法。

4.编写函数,借助队列实现二叉树的层次遍历算法。

5.编写函数,求二叉树的高度。

6.编写函数,求二叉树的结点个数。

7.编写函数,求二叉树的叶子个数。

8.编写函数,交换二叉树每个结点的左子树和右子树。

9.编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法。

三、方法与步骤：详见源代码。

四、小结：1.注意并理解了递归算法的执行步骤，使得编写程序时比较顺利，而且得到同学的帮助，减少了发生错误的次数，才使得报告能够顺利完成。

2.注意字符类型数据在输入时的处理，使输入没有错误。

3.重点理解利用栈结构实现非递归算法。

五、实验结果：实验报告源代码：#include"stdio.h"#include"malloc.h"#include"math.h"#define maxsize 100typedef struct btnode{char data;struct btnode *lc,*rc;}bitree;bitree *creat_bitree(bitree *p){char a;scanf("%c",&a);if(a!='#'){ p=(bitree *)malloc(sizeof(bitree));p->data=a;p->lc=creat_bitree(p->lc);p->rc=creat_bitree(p->rc);}elsep=NULL;return p;}void print1_bitree1(bitree *p){if(p==NULL)return ;printf("%c",p->data);print1_bitree1(p->lc);print1_bitree1(p->rc);}void print1_bitree2(bitree *p){if(p==NULL)return ;print1_bitree2(p->lc);printf("%c",p->data);print1_bitree2(p->rc);}void print1_bitree3(bitree *p) {if(p==NULL)return ;print1_bitree3(p->lc);print1_bitree3(p->rc);printf("%c",p->data);}int print2_bitree(bitree *p){int top=-1;bitree *a[maxsize];if(p==NULL) return 0;while(p!=NULL||top!=-1){while(p!=NULL){a[++top]=p;p=p->lc;}if(top<0)return 0;else{p=a[top--];printf("%c",p->data);p=p->rc;}}return 1;}int print3_bitree(bitree *p){int front=-1,rear=0;bitree *b[maxsize];if(p==NULL)return 0;b[rear]=p;while(front!=rear){p=b[++front];printf("%c",p->data);if(p->lc!=NULL)b[++rear]=p->lc;if(p->rc!=NULL)b[++rear]=p->rc;}return 1;}int jiedian_bitree(bitree *p,int a){if(p==NULL)return a;a++;a=jiedian_bitree(p->lc,a);a=jiedian_bitree(p->rc,a);return a;}int yezi_bitree(bitree *p){if(p==NULL)return 0;if(p->lc==NULL&&p->rc==NULL)return 1;return (yezi_bitree(p->lc)+yezi_bitree(p->rc)); }int depth(bitree *p){if(!p)return 0;else{int m=depth(p->lc);int n=depth(p->rc);return (m>n?m:n)+1;}}void change(bitree *p){bitree *q;if(!p)return;else{q=p->lc;p->lc=p->rc;p->rc=q;change(p->lc);change(p->rc);}}int main(){int x=8,a=0,i,j=0;bitree *p;p=NULL;while(x==8){printf("建立二叉链树，请输入字符\n");if(j==1){getchar();j=0;}p=creat_bitree(p);x=0;while(x!=8){ printf("***************************************************** *************************\n");printf("1.递归遍历\t2.中序非递归遍历\t3.层次遍历\t\t4.二叉树高度\n5.结点个数\t6.叶子个数\t\t7.交换每个结点左右子树\t8.重建二叉链树\n9.退出\n");scanf("%d",&x);switch(x){case 1:printf("1.先序2.中序3.后序");printf("\n");scanf("%d",&x);if(x==1)print1_bitree1(p);if(x==2)print1_bitree2(p);if(x==3)print1_bitree3(p);break;case 2:print2_bitree(p);break;case 3:print3_bitree(p);break;case 4:i=depth(p);printf("%d",i);break;case 5:a=jiedian_bitree(p,a);printf("%d",a);break;case 6:i=yezi_bitree(p);printf("%d",i);break;case 7:change(p);break;case 8:j=1;break;}if(x==9)break;printf("\n\n");}}return 0;}。