C语言二叉树建立、遍历、交换子树代码.doc

C语言二叉树建立,遍历(递归与非递归),交换子树(代码）/C版二叉树建立,遍历(递归与非递归),交换子树#include#include#includeusing namespace std;/建树typedef struct Nodeint data;Node *lchild,*rchild;btree;btree *create(int a,int n,int i)btree *t;if(in)t=NULL;elset=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) coutdatalchild);preorder(p-rchild);/前序遍历（非递归）void preorder1(btree *p)stack s;while(!s.empty()|p!=NULL)while(p!=NULL)coutdatalchild;p=s.top();s.pop();p=p-rchild;/中序遍历(递归）void inorder(btree *p)if(p!=NULL)inorder(p-lchild);coutdatarchild);/中序遍历（非递归）void inorder1(btree *p)stack s;while(!s.empty()|p!=NULL)while(p!=NULL)s.push(p);p=p-lchild;p=s.top();coutdatarchild;/后序遍历(递归）void postorder(btree *p)if(p!=NULL)postorder(p-lchild);postorder(p-rchild);coutdataendl;/后序遍历（非递归）struct nodebtree *t;int flag;void postorder1(btree *p)stack 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;elsecoutdataendl;p=NULL;/if/while/层次遍历(非递归）void layerorder(btree *p)queue q;btree *t;if(p!=NULL)q.push(p);while(!q.empty()t=q.front();coutdatalchild!=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);coutpreorder:endl;preorder(root);coutpreorder1:endl;preorder1(root);coutinorder:endl;inorder(root);coutinorder1:endl;inorder1(root);coutpostorder:endl;postorder(root);coutpostorder1:endl;postorder1(root);coutlayerorder:e