二叉树操作输出深度、结点数、叶结点数、递归.doc

《二叉树操作输出深度、结点数、叶结点数、递归.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验三二叉树的操作及应用一、实验目的1、掌握二叉树的特点，以及二叉链表的结构2、熟练掌握二叉树的各种操作，如建立、遍历、查找和输出3、利用己经掌握的进行实际应用二、实验要求1、编写程序实现二叉树的各种运算，并在此基础上设计主函数，使其完成如下功能：（1）按先序建立二叉树，如“ABC□□DE□G□□F□□□”，（□表示空格）。（2）建立二叉树后，判断二叉树空否，同时输出二叉树的深度。（3）建立二叉树后，判断二叉树空否，同时输出二叉树的结点数。（4）建立二叉树后，判断二叉树空否，同时输出二叉树的叶子点数。2、编写一个子函数，用非递

2、归算法中序遍历二叉树。三、程序运算结果截图第7页共7页四、程序源代码1.#include#includestructBinTreeNode;typedefstructBinTreeNode*PBinTreeNode;structBinTreeNode{charinfo;PBinTreeNodellink;PBinTreeNoderlink;};typedefstructBinTreeNode*BinTree;BinTreeCreateBiTree(){charch;BinTreet;sca

3、nf("%c",&ch);if(ch=='')t=NULL;else{t=(BinTree)malloc(sizeof(structBinTreeNode));t->info=ch;t->llink=CreateBiTree();t->rlink=CreateBiTree();}returnt;}intIsEmptyTree(BinTreet)//创建二叉树{if(t==NULL)return0;elsereturn1;}intGetDepth(BinTreet)//返回二叉树的深度{intl,r,c;l=r=c=0;if(t

4、){第7页共7页l=GetDepth(t->llink);r=GetDepth(t->rlink);c=(l>r?l:r);returnc+1;}elsereturn0;}intNode(BinTreet)//返回二叉树的结点数{if(t)returnNode(t->llink)+Node(t->rlink)+1;elsereturn0;}intLeaf(BinTreet)//返回二叉树的叶子点数{if(t){if((t->llink==NULL)&&(t->rlink==NULL))return1;elsereturnLea

5、f(t->llink)+Leaf(t->rlink);}elsereturn0;}main(){BinTreet;printf("pleaseinput:");t=CreateBiTree();if(IsEmptyTree==0)printf("二叉树为空");elseprintf("二叉树不为空");printf("二叉树的深度是:");printf("%d:",GetDepth(t));printf("二叉树的结点数是:");printf("%d:",Node(t));printf("二叉树的叶子点

6、数是:");printf("%d:",Leaf(t));}第7页共7页2.#include#includestructBinTreeNode;typedefstructBinTreeNode*PBinTreeNode;structBinTreeNode{charinfo;PBinTreeNodellink;PBinTreeNoderlink;};structBinTreeNodeBinTreeNode;typedefstructBinTreeNode*BinTree;#includ

7、e#include#includetypedefintDataType;structSeqStack{intMAXNUM;intt;DataType*s;};typedefstructSeqStack*PSeqStack;PSeqStackcreateEmptyStack_seq(intm)//创建空栈{PSeqStackpastack=(PSeqStack)malloc(sizeof(structSeqStack));if(pastack!=NULL){pastack

8、->s=(DataType*)malloc(sizeof(DataType)*m);if(pastack->s){pastack->MAXNUM=m;pastack->t=-1;returnpastack;}elsefree(pastack);}printf("Outofsp