c語言二叉樹建立、遍歷、交換子樹代碼

《c語言二叉樹建立、遍歷、交換子樹代碼》由會員上傳分享，免費在線閱讀，更多相關內容在應用文檔-天天文庫。

1、C語言二叉樹建立,遍歷(遞歸與非遞歸),交換子樹(代碼）//C版二叉樹建立,遍歷(遞歸與非遞歸),交換子樹#include#include#includeusingnamespacestd;//建樹typedefstructNode{?intdata;?Node*lchild,*rchild;}btree;btree*create(inta[],intn,inti){?btree*t;?if(i>n)??t=NULL;?else?{??t=newbtree;??t->data=a[i-1]

2、;??t->lchild=create(a,n,2*i);??t->rchild=create(a,n,2*i+1);?}?returnt;}//前序遍歷(遞歸）voidpreorder(btree*p){?if(p!=NULL)?{????cout<data<lchild);??preorder(p->rchild);?}}//前序遍歷（非遞歸）voidpreorder1(btree*p){?stacks;?while(!s.empty()

3、

4、p!=NULL)?{??wh

5、ile(p!=NULL)??{???cout<data<lchild;??}??p=s.top();??s.pop();??p=p->rchild;?}}//中序遍歷(遞歸）voidinorder(btree*p){?if(p!=NULL)?{??inorder(p->lchild);??cout<data<rchild);?}}//中序遍歷（非遞歸）voidinorder1(btree*p){

6、?stacks;?while(!s.empty()

7、

8、p!=NULL)?{??while(p!=NULL)??{???s.push(p);???p=p->lchild;??}??p=s.top();??cout<data<rchild;?}}//后序遍歷(遞歸）voidpostorder(btree*p){?if(p!=NULL)?{??postorder(p->lchild);??postorder(p->rchild);??cout

9、<data<s;?nodepost;?while(!s.empty()

10、

11、p!=NULL)?{??while(p!=NULL)??{?????post.t=p;?????post.flag=0;?????s.push(post);?????p=p->lchild;??}??if(!s.empty())??{???post=s.top();???s.pop()

12、;???if(post.flag==0)???{????post.flag=1;????s.push(post);????p=(post.t)->rchild;???}???else???{????cout<<(post.t)->data<q;?btree*t;?if(p!=NULL)??q.push(p);?while(!q.empty())?{??t=q

13、.front();??cout<data<lchild!=NULL)?????q.push(t->lchild);??if(t->rchild!=NULL)???q.push(t->rchild);?}}//對二叉樹t中所有結點的左右子樹進行交換voidexchange(btree*p){?btree*t;?if(p!=NULL)?{????t=p->lchild;????p->lchild=p->rchild;????p->rchild=t;????exchange(p->lch

14、ild);????exchange(p->rchild);?}}voidmain(){?btree*root;?inta[5]={1,2,3,4,5};?root=create(a,5,1);?cout<<