C语言二叉树建立、遍历、交换子树代码
C语言二叉树建立,遍历(递归与非递归),交换子树(代码）/C版二叉树建立,遍历(递归与非递归),交换子树#include<iostream>#include<queue>#include<stack>using namespace std;/建树typedef struct Node int data; Node *lchild,*rchild;btree;btree *create(int a,int n,int i) btree *t; if(i>n) t=NULL; else t=new btree; t->data=ai-1; t->lchild=create(a,n,2*i); t->rchild=create(a,n,2*i+1); return t;/前序遍历(递归）void preorder(btree *p) if(p!=NULL) cout<<p->data<<endl; preorder(p->lchild); preorder(p->rchild); /前序遍历（非递归）void preorder1(btree *p) stack<btree *> s; while(!s.empty()|p!=NULL) while(p!=NULL) cout<<p->data<<endl;/该语句在中序遍历中的位置不同 s.push(p); p=p->lchild; p=s.top(); s.pop(); p=p->rchild; /中序遍历(递归）void inorder(btree *p) if(p!=NULL) inorder(p->lchild); cout<<p->data<<endl; inorder(p->rchild); /中序遍历（非递归）void inorder1(btree *p) stack<btree *> s; while(!s.empty()|p!=NULL) while(p!=NULL) s.push(p); p=p->lchild; p=s.top(); cout<<p->data<<endl;/该语句在前序遍历中的位置不同 s.pop(); p=p->rchild; /后序遍历(递归）void postorder(btree *p) if(p!=NULL) postorder(p->lchild); postorder(p->rchild); cout<<p->data<<endl; /后序遍历（非递归）struct node btree *t; int flag;void postorder1(btree *p) stack<node> s; node post; while(!s.empty()|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(); if(post.flag=0) post.flag=1; s.push(post); p=(post.t)->rchild; else cout<<(post.t)->data<<endl; p=NULL; /if /while /层次遍历(非递归）void layerorder(btree *p) queue<btree *> q; btree *t; if(p!=NULL) q.push(p); while(!q.empty() t=q.front(); cout<<t->data<<endl; q.pop(); if(t->lchild!=NULL) q.push(t->lchild); if(t->rchild!=NULL) q.push(t->rchild); /对二叉树 t 中所有结点的左右子树进行交换void exchange(btree *p) btree *t; if(p!=NULL) t=p->lchild; p->lchild=p->rchild; p->rchild=t; exchange(p->lchild); exchange(p->rchild); void main() btree *root; int a5=1,2,3,4,5; root=create(a,5,1); cout<<"preorder:"<<endl; preorder(root); cout<<"preorder1:"<<endl; preorder1(root); cout<<"inorder:"<<endl; inorder(root); cout<<"inorder1:"<<endl; inorder1(root); cout<<"postorder:"<<endl; postorder(root); cout<<"postorder1:"<<endl; postorder1(root); cout<<"layerorder:"<<endl; layerorder(root); exchange(root); cout<<"after exchange(layerorder):"<<endl; layerorder(root);
