数据结构实验报告《四、二叉树及其应用》

中南大学物理学院数据结构实验报告- - - - 二叉树及其应用 专业班级：电信0903 时间：2011年11月22日数据结构实验报告- - - - 二叉树及其应用【问题描述】利用二叉树结点的结构和对二叉树的基本操作。实现二叉树每一种遍历操作并且利用递归方法编写对二叉树这种递归数据结构进行处理。【基本要求】1、 三种遍历操作实现遍历二叉树；2、 查找二叉树中的结点。【运用拓展】1、 拷贝二叉树并中序访问；2、 获得二叉排序树的深度；3、 获得二叉排序树的叶子结点数；4、 交换所有结点的左右子树并中序访问；5、仿真友好界面显示【设计思路】、定义二叉树：typedef struct BitNode char data; struct BitNode *lchild,*rchild; *BitNode,*BitTree;、相关函数声明：1、void BinTreeInit(BitTree *T)/初始化二叉树，即把树根指针置空(*T)=(BitTree)malloc(sizeof(BitNode);(*T)-data=NULL;printf(二叉树初始化成功!);2、 按先序次序建立一个二叉树int BinTreeCreat(BitTree &BT)char ch;cinch;if(ch=#) BT=NULL;elseif(!(BT=(BitTree)malloc(sizeof(BitNode)exit(0);BT-data=ch;BinTreeCreat(BT-lchild); BinTreeCreat(BT-rchild);return 0;3、/以二叉链表作为存储结构，试编写求二叉树中叶子数的算法。int num=0;void LeafCount2(BitTree T)if(T)LeafCount2(T-lchild) ; /中序遍历左子树if(!T-lchild & !T-rchild) num+; /访问根结点LeafCount2(T-rchild) ; /中序遍历右子树4、/在二叉树t中查找值为x的结点void locate(BitTree t, int x)BitTree p;p=t;if (t = NULL)printf(0n);else if( t-data = x)printf(%dn,p-data);elsep=t-lchild;if (p)locate(t-lchild, x);elselocate(t-rchild, x);5、/以二叉链表作存储结构，试编写求二叉树深度的算法int BinTreeDetth(BitTree T)int l,r;if(T=NULL)return 0;elsel=BinTreeDetth(T-lchild);r=BinTreeDetth(T-rchild);return(lr?l:r)+1);其他函数不赘述了！【函数调用及主函数设计】主函数初始化二叉树TreeInit(BitTree *BT)按先序次序建立一个二叉树BinTreeCreat(BitTree *BT)先、中、后序遍历二叉树BinTraverse(BitTree *BT)求二叉树的深度BintBinTreeDepth(BitTree BT)求二叉树的节点数、深度及交换左右结点等BinTreeCount(BitTree BT)【 程序调试及运行结果分析】1、 欢迎界面：2建立二叉树：3、 判断是否为空二叉树：4、三种遍历方式：5、判断此时的深度：6、判断叶子结点数：7、拷贝二叉树并中序访问为8、交换所有结点的左右子树并中序访问【附：程序代码】#include #include typedef struct BitNode /定义二叉树char data;struct BitNode *lchild,*rchild;BitNode,*BitTree;void BinTreeInit(BitTree *T)/初始化二叉树，即把树根指针置空(*T)=(BitTree)malloc(sizeof(BitNode);(*T)-data=NULL;printf(二叉树初始化成功!n);void BinTreeEmpty(BitTree *T)/检查二叉树是否为空if(*T)-data=NULL)printf(是空二叉树!n);else printf(不是空二叉树!n);void createBitTree(BitTree *T)/创建二叉树利用先序创建int dat;printf(请按照先序遍历输入二叉树的元素，以“”代替空结点:);scanf(%d,&dat);if(dat=0) (*T) = NULL;else(*T) = (BitTree)malloc(sizeof(BitNode);(*T)-data=dat;createBitTree(&(*T)-lchild);createBitTree(&(*T)-rchild);void PreOrder(BitTree T)/二叉树的先序递归算法if (T != NULL)printf(%dt,T-data);PreOrder(T-lchild);PreOrder(T-rchild);void InOrder(BitTree T)/二叉树的中序递归算法if (T != NULL)InOrder(T-lchild);printf(%dt,T-data);InOrder(T-rchild);void PostOrder(BitTree T)/二叉树的后序周游递归算法if (T != NULL)PostOrder(T-lchild);PostOrder(T-rchild);printf(%dt,T-data);void locate(BitTree t, int x)/在二叉树t中查找值为x的结点BitTree p;p=t;if (t = NULL)printf(0n);else if( t-data = x)printf(%dn,p-data);elsep=t-lchild;if (p)locate(t-lchild, x);elselocate(t-rchild, x);int BinTreeDetth(BitTree T)/以二叉链表作存储结构，试编写求二叉树深度的算法int l,r;if(T=NULL)return 0;elsel=BinTreeDetth(T-lchild);r=BinTreeDetth(T-rchild);return(lr?l:r)+1);int num=0;/以二叉链表作为存储结构，试编写求二叉树中叶子数的算法void LeafCount(BitTree T)if(T)LeafCount(T-lchild) ; /中序遍历左子树if(!T-lchild & !T-rchild) num+; /访问根结点LeafCount(T-rchild) ; /中序遍历右子树BitTree copy(BitTree T)/以二叉链表作为存储结构，设计算法拷贝二叉树BitTree T1;if(T=NULL) T1=NULL;elseT1=(BitTree)malloc(sizeof(BitNode); /申请结点T1-data=T-data;T1-lchild=copy(T-lchild);T1-rchild=copy(T-rchild);return T1;BitTree change(BitTree T)/以二叉链表作为存储结构，设计算法交换二叉树中所有结点的左、右子树BitTree t;if(T!=NULL)change(T-lchild);change(T-rchild);t=T-lchild;T-lchild=T-rchild;T-rchild=t;return T;void main()BitTree T;int n,m,a;printf( *n);/输出菜单printf( * 欢迎使用二叉树的运用程序 *n);printf( * *n);printf( * *n);printf( * 0、初始化二叉树； *n);printf( * 1、建立新的二叉树； *n);printf( * （请按照先序输入二叉树的元素，以“”代替空结点） *n);printf( * *n);printf( * 作者：电信班 *n);printf( * 卢银滨 *n);printf( *n);printf( 请输入你要执行的操作:n);scanf(%d,&a);switch(a)case 0:BinTreeInit(&T);a=1;break;case 1:createBitTree(&T);printf(二叉树已成功建立!nn);break;default:printf(您的输入有误n);while(1)printf(0-检查二叉树是否为空n);printf(1-先序遍历n);printf(2-中序遍历n);printf(3-后序遍历n);printf(4-查找你要的结点n);printf(5-求此二叉排序树的深度n);printf(6-求此二叉排序树的叶子结点数n);printf(7-拷贝二叉树并中序访问n);printf(8-交换所有结点的左右子树并中序访问n);printf(9-结束此次操作n);printf(请输入你要执行的操作:n);scanf(%d,&n);switch(n)case 0:BinTreeEmpty(&T);break;case 1:printf(先序遍历为:n);PreOrder(T);printf(n);break;case 2:printf(中序遍历为:n);InOrder(T);printf(n);break;case 3:printf(后序遍历为:n);PostOrder(T);printf(n);break;case 4:printf(请输入你要查找的结点:n);scanf(%d,&m);printf(你要查找的结点为: n);locate(T,m);break;case 5:printf(树的深度为:n);printf(%dn,BinTreeDetth(T);break;case 6:printf(此树的叶子结点数为:n);LeafCount(T);printf(%dn,num);break;case 7:printf(拷贝二叉树并中序访问为:n);PreOrder(copy(T);printf(n);break;case 8:printf(注意：（进行二次交换以便恢复到原来的状态）交换所有结点的左右子树并中序访问:n);printf(the first change is:n);PreOrder(change(T);printf(n);printf(the second change is:n);PreOrder(change(T);printf(n);break;case 9:return;default:printf(您的输入有误n);【参考文献】1 数据结构（C 语言版） 严蔚敏，吴伟民 清华大学出版社 2 数据结构题集（C 语言版） 严蔚敏，吴伟民，米宁 清华大学出版社 3 C+程序设计 杨长兴，刘卫国 中国铁道出版社