/*[基本要求] 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。
[测试数据] ABCффDEфGффFффф（其中ф表示空格字符） 则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA */
#include <iostream> using namespace std; class node{ public: char data; node *left; node *right; };
class Btree{ private: node *root; void firsthelp(node *first); void middlehelp(node *first); void lasthelp(node *first); public: void init(); void creattree(char *a); void firstvisit(){firsthelp(root);} void middlevisit(){middlehelp(root);} void lastvisit(){lasthelp(root);} };
void Btree::init(){root=NULL;} void Btree::creattree(char *a) { node *s[10];//储存根节点的债 int i=0; int top=-1; int k=1;//k=1处理左子树，k=2处理右子树 node *p; while(a[i]) { switch(a[i]) { case '#': if(k==1){k=2;} else { top--; /*这句while循环到底有什么问题！！！！若改成if循环运行对这个2叉树则OK， 但不能用于其他的2叉树(比如AB#D#E#F##C##)*/ while(s[top]->right!=NULL) { top--; }
} break; default: p=new node; p->data=a[i]; p->left=p->right=NULL; s[++top]=p; if(root==NULL){root=p;} else {if(k==1){s[top-1]->left=p;} else{s[top-1]->right=p;k=1;} } } i++; } }
void Btree::firsthelp(node *first) { if(first==NULL) return; else{ cout<<first->data<<" "; firsthelp(first->left); firsthelp(first->right); }
} void Btree::middlehelp(node *first) { if(first==NULL) return; else{ middlehelp(first->left); cout<<first->data<<" "; middlehelp(first->right); }
}
void Btree::lasthelp(node *first) { if(first==NULL) return; else{ lasthelp(first->left); lasthelp(first->right); cout<<first->data<<" "; }
}
int main(){ char b[20]="ABC##DE#G##F###"; Btree a; a.init(); a.creattree(b); cout<<"先序遍历的结果"<<endl; a.firstvisit(); cout<<endl; cout<<"中序遍历的结果"<<endl; a.middlevisit(); cout<<endl; cout<<"后序遍历的结果"<<endl; a.lastvisit(); cout<<endl; return 0; }
