二叉树的遍历（C语言实现）

#include<iostream> #include<malloc.h> using namespace std; #define maxsize 100 typedef struct node { char data; struct node *left,*right; node(void) { left=NULL; right=NULL; } }btree; void creatree(btree* &b,char str[])//b要用引用 或者传b的地址进来，否则在函数体内更改形参不会对实参产生作用 { btree *stack[maxsize],*p; int top=-1,k,j=0; char ch; b=NULL; ch=str[j]; while(ch!='\0') { switch(ch) { case '(':top++;stack[top]=p;k=1;break; case ')':top--;break; case ',':k=2;break; default://p=(btree *)malloc(sizeof(btree)); p=new btree();//用构造函数构造，可以自动赋初值 p->data=ch;//p->left=p->right=NULL;//这一步可以在构造函数里完成 if(b==NULL) b=p; else { //stack[top]=(btree *)malloc(sizeof(btree));//这里不应该分配新空间，因为它所保存的是上步得到的节点，若果重新分配空间，则上步得到的节点地址无法找到 switch(k) { case 1:stack[top]->left=p;break; case 2:stack[top]->right=p;break; } } } j++; ch=str[j]; } } void porder(btree *b)//这个函数是对的 { btree *stack[maxsize],*p; int top; if(b!=NULL) { top=1; stack[top]=b; while(top>0) { p=stack[top]; top--; cout << p->data << " "; if(p->right!=NULL) { top++; stack[top]=p->right; } if(p->left!=NULL) { top++; stack[top]=p->left; } } } } void iorder(btree *b)//这里有些问题 ，我改了某些地方 { btree *stack[maxsize],*p=b; int top=-1; do { while(p!=NULL) { top++; stack[top]=p; p=p->left; } if(top>=0) { p=stack[top]; top--; cout<<p->data<<" "; p=p->right; if(NULL!=p)//这里必须在这里将右子树放进堆栈，否则到根节点的时候，由于堆栈空了，top的值为-1，会退出循环，导致右子树无法访问 { stack[++top]=p; p=p->left; } } }while(top>=0);//若堆栈空，说明没有要访问的节点了，退出循环 } void psorder(btree *t)//这个函数是对的 { btree *stack[maxsize],*p; int flag,top=-1; do { while(t) { top++; stack[top]=t; t=t->left; } p=NULL; flag=1; while(top!=-1 && flag) { t=stack[top]; if(t->right==p || t->right==NULL) { cout<<t->data<<" "; top--; p=t; } else { t=t->right; flag=0; } } }while(top!=-1); } /***************************** 由于树是递归定义的，因此 有关树的大多数程序都比较适合用递归的方式来写，下面我用递归的 方式写了二叉树的前序、中序和后序遍历，你可以参考下 *******************************/ void Inorder(btree* root)//中序 { if(NULL==root)return; Inorder(root->left);//访问左子树 cout<<root->data<<' ';//访问根 Inorder(root->right);//访问右子树 } void Preorder(btree* root)//前序 { if(NULL==root)return; cout<<root->data<<' ';///访问根 Preorder(root->left);//访问左子树 Preorder(root->right);//访问右子树 } void Psorder(btree* root)//后序 { if(NULL==root)return; Psorder(root->left);//访问左子树 Psorder(root->right);//访问右子树 cout<<root->data<<' ';//访问根 } void main() { btree *b; creatree(b,"a(b(c),d(e(,f),g))"); cout<<"非递归函数执行的结果\n"; cout<<"先序遍历："; porder(b); cout<<endl; cout<<"中序遍历："; iorder(b); cout<<endl; cout<<"后序遍历："; psorder(b); cout<<endl; cout<<"递归函数执行的结果：\n"; cout<<"先序遍历："; Preorder(b); cout<<endl; cout<<"中序遍历："; Inorder(b); cout<<endl; cout<<"后序遍历："; Psorder(b); cout<<endl; } /* a b d c e g f */