共计 1100 个字符,预计需要花费 3 分钟才能阅读完成。
#include<iostream>
using namespace std;
typedef struct BiNode{
char data;
struct BiNode *lchild,*rchild;
}BiTNode,*BiTree;
// 先序建设二叉链表
void CreateBiTree(BiTree &T){
char ch;
cin >> ch;
if(ch=='#') T=NULL;
else{
T=new BiTNode;
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
// 链栈
typedef struct StackNode{
BiTNode data;
struct StackNode *next;
}StackNode,*LinkStack;
// 结构空栈 S
void InitStack(LinkStack &S){S=NULL;}
bool StackEmpty(LinkStack S){if(!S)
return true;
return false;
}
// 入栈
void Push(LinkStack &S,BiTree e){
StackNode *p=new StackNode;
p->data=*e;
p->next=S;
S=p;
}
// 出栈
void Pop(LinkStack &S,BiTree e){if(S!=NULL){
*e=S->data;
StackNode *p=S;
S=S->next;
delete p;
}
}
// 中序遍历
void In(BiTree T){
LinkStack S;
BiTree p;
BiTree q=new BiTNode;
InitStack(S); p=T;
while(p||!StackEmpty(S)){if(p){Push(S,p);
p=p->lchild;
}
else{Pop(S,q);
cout<<q->data;
p=q->rchild;
}
}
}
// 先序遍历
void Pre(BiTree T){
LinkStack S;
BiTree p;
BiTree q=new BiTNode;
InitStack(S); p=T;
while(p||!StackEmpty(S)){if(p){Push(S,p);
cout<<p->data;
p=p->lchild;
}
else{Pop(S,q);
p=q->rchild;
}
}
}
int main(){
BiTree tree;
cout<<"先序建设二叉链表:";
CreateBiTree(tree);
cout<<"先序遍历的后果为:";
Pre(tree);
cout<<endl;
cout<<"中序遍历的后果为:";
In(tree);
cout<<endl;
}
正文完