二叉树的基本操作实验

1、实验三 二叉树的基本运算一、实验目的1、使学生熟练掌握二叉树的逻辑结构和存储结构。2、熟练掌握二叉树的各种遍历算法。二、实验内容 问题描述 建立一棵二叉树，试编程实现二叉树的如下基本操作：1. 按先序序列构造一棵二叉链表表示的二叉树T；2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；3. 求二叉树的深度/结点数目/叶结点数目；（选做 ）4. 将二叉树每个结点的左右子树交换位置。（选做） 基本要求 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）， 测试数据 如输入：AB6D印G66F力力力（其中力表示空格字符）则输出结果为先序：ABC

2、DEGF中序：CBEGDFA后序：CGEFDBA层序：ABCDEFG 选作内容 采用非递归算法实现二叉树遍历。三、实验前的准备工作1、掌握树的逻辑结构。2、掌握二叉树的逻辑结构和存储结构。3、掌握二叉树的各种遍历算法的实现。一 实验分析本次试验是关于二叉树的常见操作，主要是二叉树的建立和遍历。二叉树的遍历有多种方法，本次试验我采用递归法，递归法比较简单。二 概要设计功能实现I.int CreatBiTree(BiTree &T)存该二叉树2.int PreTravel(BiTree &T)3. int MidTravel(BiTree &T)4.int PostTravel(BiTree &T

3、)5.int Depth(BiTree &T) /用递归的方法先序建立二叉树，并用链表储前序遍历中序遍历后序遍历计算树的深度6.int howmuch(BiTree T,int h) 采用树节点指针数组，用于存放遍历到的元 素地址，如果有左孩子，存入地址，j加一，否则没操作，通过访问数组输出层次遍历的结果。k计算叶子数，j为总节点7 / 87. int exchang(BiTree &T)交换左右子树，利用递归，当有左右孩子时才交换三详细设计#include#include typedef struct BiTNode char data;struct BiTNode *lchild,*rch

4、ild; BiTNode,*BiTree;int CreatBiTree(BiTree &T)/先序法创建二叉树char ch;if(ch=getchar()= )T=NULL;elseT=(BiTNode*)malloc(sizeof(BiTNode);if(!T)exit(1);T-data=ch;CreatBiTree(T-lchild);CreatBiTree(T-rchild);return 0;int PreTravel(BiTree &T)/前序遍历if(T)printf(%c,T-data);PreTravel(T-lchild);PreTravel(T-rchild);ret

5、urn 0;int MidTravel(BiTree &T)/中序遍历if(T)MidTravel(T-lchild);printf(%c,T-data);MidTravel(T-rchild);return 0;int PostTravel(BiTree &T)/后序遍历if(T)PostTravel(T-lchild);PostTravel(T-rchild);printf(%c,T-data);return 0;int howmuch(BiTree T,int h)BiTNode *Q100;/ 树节点指针数组，用于存放遍历到的元素地址if(T=NULL)printf( 空的二叉树n);

6、Q0=T; / 存入树根int i,k=0;int j=1; /j 为总节点for(i=0;ilchild!=NULL) / 如果有左孩子，存入地址，j 加一 ，否则没操作Qj=Qi-lchild ;j+;if(Qi-rchild!=NULL) / 如果有右孩子，存入地址，j 加一 ，否则没操作Qj=Qi-rchild ;j+;if(Qi-lchild=NULL&Qi-rchild=NULL) k+; /计算叶子数 if(h=0)printf(%d, j);else if(h=1)printf(%d,k);else if(h=2)for(i=0;idata);elseprintf( 参数错误)

7、;return 0;int Depth(BiTree &T)/计算树的深度int lh , rh ;if( NULL = T )return 0 ; else lh = Depth( T-lchild ) ;rh = Depth( T-rchild ) ; return ( lh rh ? lh : rh ) + 1 ;int exchang(BiTree &T)/ 交换左右子树if(T != NULL)if(T-lchild!=NULL&T-rchild!=NULL)/ 当有左右孩子时才交换 char t;t=T-lchild-data;T-lchild-data=T-rchild-data

8、; T-rchild-data=t; / 交换数据exchang(T-lchild);/ 递归调用 exchang(T-rchild);return 0;int choose(BiTree T) / 功能选int a;scanf(%d,&a); if(a=1) printf( 先序遍历:);PreTravel(T);else if(a=2)printf( 中序遍历:);MidTravel(T);else if(a=3)printf( 后序遍历:);PostTravel(T);else if(a=4)printf( 层序遍历:);howmuch(T,2);else if(a=5)printf(

9、总节点数：);howmuch(T,0);else if(a=6)printf( 总叶子数：);howmuch(T,1);else if(a=7)printf( 树的深度：);printf(%d,Depth(T);else if(a=8)printf( 交换前 n);howmuch(T,2);exchang(T);printf( 交换后 n);howmuch(T,2);else if(a=9)exit(1);else printf( 没有这个操作n);printf( 操作完成,请输入下一个操作n);choose(T);return 0;int main() / 主函数printf( 二叉树的基本操作n);printf( 请先建立二叉树，按先序的方式输入如果数据为空输入空格n);BiTree T; / 定义二叉树，初始化CreatBiTree(T);choose(T);return 0;四用户手册根据程序的提示按先序输入二叉树， 如果数据为空输入空格，然后回车，输入你 要进行的操作的序号。1.先序遍历、2中序遍历、3后序遍历、4层次遍历、5总节点数、6总叶子数、7树的深度、8交换左右子树、9结束操作五实验总结通过实验，我熟悉二叉树树的基本操作，掌握二叉树的实