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

第1页共7页实验三二叉树的操作及应用一、实验目的1、掌握二叉树的特点，以及二叉链表的结构2、熟练掌握二叉树的各种操作，如建立、遍历、查找和输出3、利用己经掌握的进行实际应用二、实验要求1、编写程序实现二叉树的各种运算，并在此基础上设计主函数，使其完成如下功能：（1）按先序建立二叉树，如“ABC□□DE□G□□F□□□”，（□表示空格）。（2）建立二叉树后，判断二叉树空否，同时输出二叉树的深度。（3）建立二叉树后，判断二叉树空否，同时输出二叉树的结点数。（4）建立二叉树后，判断二叉树空否，同时输出二叉树的叶子点数。2、编写一个子函数，用非递归算法中序遍历二叉树。三、程序运算结果截图第2页共7页四、程序源代码1.#includestdio.h#includestdlib.hstructBinTreeNode;typedefstructBinTreeNode*PBinTreeNode;structBinTreeNode{charinfo;PBinTreeNodellink;PBinTreeNoderlink;};typedefstructBinTreeNode*BinTree;BinTreeCreateBiTree(){charch;BinTreet;scanf(%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){第3页共7页l=GetDepth(t-llink);r=GetDepth(t-rlink);c=(lr?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;elsereturnLeaf(t-llink)+Leaf(t-rlink);}elsereturn0;}main(){BinTreet;printf(pleaseinput:\n);t=CreateBiTree();if(IsEmptyTree==0)printf(二叉树为空);elseprintf(二叉树不为空\n);printf(二叉树的深度是:\n);printf(%d:\n,GetDepth(t));printf(二叉树的结点数是:\n);printf(%d:\n,Node(t));printf(二叉树的叶子点数是:\n);printf(%d:\n,Leaf(t));}第4页共7页2.#includestdio.h#includestdlib.hstructBinTreeNode;typedefstructBinTreeNode*PBinTreeNode;structBinTreeNode{charinfo;PBinTreeNodellink;PBinTreeNoderlink;};structBinTreeNodeBinTreeNode;typedefstructBinTreeNode*BinTree;#includestdio.h#includemalloc.h#includestdlib.htypedefintDataType;structSeqStack{intMAXNUM;intt;DataType*s;};typedefstructSeqStack*PSeqStack;PSeqStackcreateEmptyStack_seq(intm)//创建空栈{PSeqStackpastack=(PSeqStack)malloc(sizeof(structSeqStack));if(pastack!=NULL){pastack-s=(DataType*)malloc(sizeof(DataType)*m);if(pastack-s){pastack-MAXNUM=m;pastack-t=-1;returnpastack;}elsefree(pastack);}printf(Outofspace!\n);returnNULL;}intIsEmpty(PSeqStackpalist)//判断空栈{if(palist-t==-1)第5页共7页return0;elsereturn1;}voidpush_seq(PSeqStackpastack,charx)//在栈中插入元素x{if(pastack-t=pastack-MAXNUM-1)printf(Overflow!\n);else{pastack-t=pastack-t+1;pastack-s[pastack-t]=x;}}DataTypetop_seq(PSeqStackpastack)//取栈顶元素{if(pastack-t==-1)printf(It'isempty!\n);elsereturn(pastack-s[pastack-t]);}voidpop_seq(PSeqStackpastack)//出栈{if(pastack-t==-1)printf(Underflow!\n);elsepastack-t=pastack-t-1;}BinTreeCreateBiTree()//创建二叉树{charch;BinTreet;scanf(%c,&ch);if(ch=='')t=NULL;else{t=(BinTree)malloc(sizeof(structBinTreeNode));t-info=ch;t-llink=CreateBiTree();t-rlink=CreateBiTree();}第6页共7页returnt;}intIsEmptyTree(BinTreet)//判断二叉树是否为空{if(t==NULL)return0;elsereturn1;}BinTreeroot(BinTreet)//返回根结点{returnt;}BinTreeleftChild(BinTreet)//返回左子树{if(t)returnt-llink;returnNULL;}BinTreerightChild(BinTreet)//返回右子树{if(t)returnt-rlink;returnNULL;}voidInOrderTravel(BinTreet)//二叉树中序遍历非递归算法法{BinTreec=t;PSeqStacks=createEmptyStack_seq(20);if(t==NULL)return;while(c!=NULL||!IsEmpty(s)){while(c!=NULL){push_seq(s,c-info);c=leftChild(c);}c=top_seq(s);printf(%c,c);printf(%c,top_seq(s));pop_seq(s);第7页共7页c=rightChild(c);}printf(\n);}voidInorder(BinTreet)//二叉树中序遍历递归算法{if(t==NULL)return;Inorder(leftChild(t));printf(%c,t-info);Inorder(rightChild(t));}main(){BinTreet;printf(pleaseinput:\n);t=CreateBiTree();if(IsEmptyTree==0)printf(二叉树为空);elseprintf(二叉树不为空\n);printf(二叉树递归遍历:\n);Inorder(t);printf(\n);printf(二叉树递归遍历:\n);Inorder(t);}