BiTree CreateBiTree(void)//按先序次序输入二叉树中结点的值，'#'代表空树 { TElemType e; BiTree tmp = NULL;

if( (e=getchar())!='#' ){ getchar();//接收回车符 tmp=(BiTree)malloc(sizeof(BiTNode)); if(!tmp) return NULL; tmp->data=e; printf("请输入左孩子："); tmp->lchild=CreateBiTree(); printf("请输入右孩子："); tmp->rchild=CreateBiTree(); } else getchar();//接收回车符

return tmp; }

以下是二叉树的生成和各种遍历情况 /*利用队列实现二叉树层次遍历 这个程序通过键盘输入一个二叉树，生成二叉树过程中，用到了一个队列， 用队列的先进先出的性质,可以实现层次遍历二叉树。*/ #include <iostream.h> typedef struct node { int data; struct node* left; struct node* right; }node; //线索化二叉树　2004/2/1 typedef struct threadnode { int data; threadnode* prev; threadnode* next; int ltag; int rtag; }threadnode;

class queue { public: queue() { q=new node*[10]; front=0; rear=0; maxsize=10;

} int IsFull() { if((rear+1)%maxsize==front) return 1; else return 0; } int IsEmpty() { if(front==rear) return 1; else return 0; } void InQueue(node* p) { if(IsFull()) { cout<<"队列满!!进队失败!!"<<endl; return; } else { q[rear]=p; rear=(rear+1)%maxsize; } } node* OutQueue() { if(IsEmpty()) { cout<<"队列空!!出队失败!!"<<endl; return 0; } else { node* t; t=q[front]; front=(front+1)%maxsize; return t; } }

private: node** q; int front; int rear; int maxsize; };

//2004/2/1 线索化二叉树的队列　 class threadqueue { public: threadqueue() { q=new threadnode*[10]; front=0; rear=0; maxsize=10;

} int IsFull() { if((rear+1)%maxsize==front) return 1; else return 0; } int IsEmpty() { if(front==rear) return 1; else return 0; } void InQueue(threadnode* p) { if(IsFull()) { cout<<"队列满!!进队失败!!"<<endl; return; } else { q[rear]=p; rear=(rear+1)%maxsize; } } threadnode* OutQueue() { if(IsEmpty()) { cout<<"队列空!!出队失败!!"<<endl; return 0; } else { threadnode* t; t=q[front]; front=(front+1)%maxsize; return t; } }

private: threadnode** q; int front; int rear; int maxsize; };

// 非递归遍历二叉树　工作栈

class stack { private: node** s; int top; int size;

public: void push(node* x) { if(IsFull()) { cout<<"栈己满!!"<<endl; return; } s[++top]=x; }

node* pop() { if(IsEmpty()) { cout<<"栈己空!!"<<endl; return 0; } return s[top--]; } stack() { top=-1; size=20; s=new node*[20]; } int IsEmpty () { if(top==-1) return 1; else return 0; }

int IsFull() { if(top==size-1) return 1; else return 0; }

};

//线索化二叉树使用的栈　

class threadstack { private: threadnode** s; int top; int size;

public: void push(threadnode* x) { if(IsFull()) { cout<<"栈己满!!"<<endl; return; } s[++top]=x; }

threadnode* pop() { if(IsEmpty()) { cout<<"栈己空!!"<<endl; return 0; } return s[top--]; } threadstack() { top=-1; size=20; s=new threadnode*[20]; } int IsEmpty () { if(top==-1) return 1; else return 0; }

int IsFull() { if(top==size-1) return 1; else return 0; }

}; //全局变量 queue q1; stack s1; threadqueue tq1; threadstack ts1;

//层次生成线索化二叉树原型 threadnode* Createthreadtree() { int data; cout<<"请输入根结点: "; cin>>data; threadnode* root; root=new threadnode; root->ltag =root->rtag =0; root->prev =root->next =0; root->data =data; tq1.InQueue (root); threadnode* p; threadnode* s; while(!tq1.IsEmpty ()) { p=tq1.OutQueue (); cout<<"请输入"<<p->data <<"的左子树: "; cin>>data; if(data) { s=new threadnode; s->ltag =s->rtag =0; s->prev =s->next =0; s->data =data; p->prev =s; p->ltag =1; tq1.InQueue (s); } cout<<"请输入"<<p->data <<"的右子树: "; cin>>data; if(data) { s=new threadnode; s->ltag =s->rtag =0; s->prev =s->next =0; s->data =data; p->next =s; p->rtag =1; tq1.InQueue (s); } } return root; } //层次生成二叉树 node* CreateBtree() { int data; cout<<"请输入根结点: "; cin>>data; node* root; root=new node; root->data =data; root->left =0; root->right =0; q1.InQueue (root); node* p; while(!q1.IsEmpty ()) { p=q1.OutQueue (); cout<<"请输入"<<p->data <<"的左子树: "; cin>>data; node* l; if(data) { l=new node; l->data =data; l->left =0; l->right =0; p->left =l; q1.InQueue (l); } cout<<"请输入"<<p->data <<"的右子树: "; cin>>data; if(data) { l=new node; l->data =data; l->left =0; l->right =0; p->right =l; q1.InQueue (l); } } return root; } //非递归遍历二叉树 void travel(node* root) { node* p=root; for(;;) { s1.push (p); while(p->left ) { p=p->left ; s1.push (p); }

for(;;) { p=s1.pop ();

cout<<p->data <<" "; if(p->right ) { p=p->right ;

break; } else { if(s1.IsEmpty ()) return; } } }

}

//中序线索化二叉树，需要一个线索化二叉树原型? void threadBtree(threadnode* root) { threadnode* p=root; threadnode* q=0; for(;;) { ts1.push (p); while(p->prev ) { p=p->prev ; ts1.push (p); } for(;;) { p=ts1.pop ();

if(q!=0) { if(q->rtag ==0) q->next =p; if(p->ltag ==0) p->prev =q; } q=p; if(p->next ) { p=p->next;

break; } else { if(ts1.IsEmpty ()) return; } } } } void main() {

threadnode* root; root=Createthreadtree(); threadBtree(root); }