实验四 二叉树的建立与遍历.doc

《实验四 二叉树的建立与遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验四二叉树的建立与遍历【实验目的】l掌握二叉树的定义、性质及存储方式，各种遍历算法。【实验内容】１．采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序遍历的递归操作。２．分别求所有叶子结点及结点总数的操作。提示：设计一颗二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD###CE##F##，建立二叉树，求出先序、中序和后序遍历序列，求所有叶子及结点总数。【程序源代码】#include#includetypedefcharTElemType;typedefintStatus;#defi

2、neOK1#defineERROR0#defineOVERFLOW0typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;StatusCreateBiTree(BiTree&BT);voidCountLeaves(BiTreeBT,int&count);intNodeCount(BiTreeBT);voidPreOrder(BiTreeBT);voidInOrder(BiTreeBT);voidPostOrder(BiTreeBT);intmai

3、n(){BiTreeBT;intchoice,cho;intlogo=1;printf("输入二叉树结点，以'#'为空指针");CreateBiTree(BT);do{printf("t1:遍历二叉树");printf("t2：二叉树总结点数及叶子节点数");printf("t3：退出程序");printf("t输入选项:");scanf("%2d",&choice);switch(choice){case1:printf("1:先序遍历");printf("2:中序遍历");printf("3:后序遍历");sca

4、nf("%2d",&cho);switch(cho){case1:PreOrder(BT);printf("");break;case2:InOrder(BT);printf("");break;case3:PostOrder(BT);printf("");break;default:printf("输入错误!");}break;case2:intcount;printf("总结点数为:%2d",NodeCount(BT));CountLeaves(BT,count);printf("叶子结点数为:%2d",count);bre

5、ak;case3:exit(0);break;default:printf("输入错误!");}}while(logo==1);return0;}StatusCreateBiTree(BiTree&BT){charch;scanf("%c",&ch);if(ch=='#')BT=NULL;else{if(!(BT=(BiTree)malloc(sizeof(BiTNode))))exit(OVERFLOW);BT->data=ch;CreateBiTree(BT->lchild);CreateBiTree(BT->rchild);}returnOK

6、;}voidPreOrder(BiTreeBT){if(BT!=NULL){printf("%c",BT->data);PreOrder(BT->lchild);PreOrder(BT->rchild);}}voidInOrder(BiTreeBT){if(BT!=NULL){PreOrder(BT->lchild);printf("%c",BT->data);PreOrder(BT->rchild);}}voidPostOrder(BiTreeBT){if(BT!=NULL){PreOrder(BT->lchild);PreOrder(BT->rch

7、ild);printf("%c",BT->data);}}voidCountLeaves(BiTreeBT,int&count){if(BT){if(!BT->lchild&&!BT->rchild)count++;CountLeaves(BT->lchild,count);CountLeaves(BT->rchild,count);}}intNodeCount(BiTreeBT)//统计总结点数{if(BT==NULL)return0;elsereturn(NodeCount(BT->lchild)+NodeCount(BT->rchild)+1);

8、}【运行结果分析】【实验收获与心得】在本次实验中，我对递归这个概念有了较为深刻的认识，对二叉树