二叉樹(shù)相關(guān)算法

任務(wù)：設(shè)計(jì)一個(gè)程序，實(shí)現(xiàn)二叉樹(shù)的前序、中序、后序的遞歸、非遞歸遍歷運(yùn)算。要求：創(chuàng)建二叉樹(shù)；二叉樹(shù)的前序、中序、后序的遞歸遍歷運(yùn)算實(shí)現(xiàn)；二叉樹(shù)的前序、中序、后序的非遞歸遍歷運(yùn)算實(shí)現(xiàn)。#include"stdlib.h”#include"iostream"usingnamespacestd;#defineok1#definenull0typedefchartelemtype;typedefstructbitnode(telemtypedata;structbitnode*lchild,*rchild;}bitnode,*bitree;/*voidvisit(bitnode*p)(printf("%c",p->data);}*/〃先序建樹(shù)bitreecreatebitree(void)(charch;bitnode*t;scanf(〃％c〃,&ch);if(ch=='#')t=null;else(t=(bitnode*)malloc(sizeof(bitnode));t->data=ch;t->lchild=createbitree();t->rchild=createbitree();}returnt;}//中序遞歸遍歷voidinorder(bitreeT)(if(T)(inorder(T->lchild);printf("%c",T->data);inorder(T->rchild);}}//先序遞歸遍歷voidpreorder(bitreeT){if(T)(printf(〃％c〃,T->data);preorder(T->lchild);preorder(T->rchild);}}//后序遞歸遍歷voidPost_order(bitreeT)(if(T)(Post_order(T->lchild);Post_order(T->rchild);printf(〃％c〃,T->data);}}〃先序非遞歸遍歷二叉樹(shù)voidPreTree(bitreeT)(bitreep,node[20];inttop=0;P=T;do(while(p!=NULL)(cout<<p->data<<"";node[top]=p;top++;p=p->lchild;}if(top>0){top--;p=node[top];p=p->rchild;}}while(top>0||p!二NULL);cout<<endl;}〃中序非遞歸遍歷二叉樹(shù)voidInTree(bitreeT)(bitreep,node[20];inttop=0;P=T;do(while(p!二NULL)(node[top]=p;top++;p=p->lchild;}if(top>0){cout<<p->data<<”";top--;p=node[top];p=p->rchild;}}while(top>0||p!二NULL);cout<<endl;}〃后序非遞歸遍歷二叉樹(shù)voidPostTree(bitreeT)(bitreep,node[20];inttop=0;p=T;do(while(p!=NULL)(cout<<p->data<<"";node[top]=p;top++;p=p->lchild;}if(top>0)(top--;p=node[top];p=p->rchild;}}while(top>0||p!=NULL);cout<<endl;}voidleaf(bitreeT,int&count)(if(T)

(if(T->lchild==NULL&&T->rchild==NULL)count++;else(leaf(T->lchild,count);leaf(T->rchild,count);}}}intdeepth(bitreeT)(intleftdep,rightdep;if(!T)return0;else(leftdep二deepth(T->lchild);rightdep二deepth(T->rchild);if(leftdep>rightdep)returnleftdep+1;elsereturnrightdep+1;}}voidlevel_order(bitreeT)(}〃輸出菜單voidprint_menu()cout<<"請(qǐng)選擇你要進(jìn)行的操作：〃<<endl;〃<<〃2.中序遞歸遍歷二叉〃<<〃4.后序遞歸遍歷二叉〃<<〃6.中序非遞歸遍歷二叉〃<<〃2.中序遞歸遍歷二叉〃<<〃4.后序遞歸遍歷二叉〃<<〃6.中序非遞歸遍歷二叉〃<<〃8.求葉子結(jié)點(diǎn)個(gè)〃<<〃10.層序遍歷二叉樹(shù)!〃<<endl;cout<<〃3.先序遞歸遍歷二叉樹(shù)!〃<<〃樹(shù)!〃<<endl;cout<<〃5.先序非遞歸遍歷二叉樹(shù)!〃<<〃樹(shù)!〃<<endl;cout<<〃7.后序非遞歸遍歷二叉樹(shù)!〃<<〃數(shù)!〃<<endl;cout<<〃9.求樹(shù)的深度！ 〃<<〃樹(shù)!"<<endl;cout<<"11.退出!"<<endl;}voidmain()(bitreet;intk,c=0,d;print_menu();cin>>k;while(k!=11)(switch(k)(case1:cout<<"請(qǐng)輸入樹(shù)的先序字符序列，空樹(shù)以#表示〃<<endl;t=createbitree();cout<<"建樹(shù)成功〃<<endl;break;case2:inorder(t);break;case3:preorder(t);break;case4:Post_order(t);break;case5:PreTree(t);break;case6:InTree(t);break;case7:PostTree(t);break;case8:leaf(t,c);cout<<"葉子結(jié)點(diǎn)數(shù)為：〃<<c<<endl;break;case9:d=deepth(t);cout<<"樹(shù)的深度為："<<d<<endl;b