用二叉树实现先序.中序.后序.层次遍历的算法
用先序遍历建立一个二叉树，实现先序遍历、中序遍历、后序遍历，且用队列实现层次遍历： #include
using namespace std;
#define N 10
typedef struct node{
char data;
struct node*lchild,*rchild;
}*BiTree,BTNode;
typedef struct{
BiTree data[N];
int front,rear;
}SqQueue;
BiTree CrtBt()
{ char ch;
BiTree bt;
ch=getchar();
if(ch=='_') return NULL;
bt=new BTNode;
bt->data=ch;
bt->lchild=CrtBt();
bt->rchild=CrtBt();
return bt;
}
void preorder(BiTree bt)
{ if(bt==NULL) return;
putchar(bt->data);
preorder(bt->lchild);
preorder(bt->rchild);
}
void midorder(BiTree bt)
{ if(bt==NULL) return;
midorder(bt->lchild);
putchar(bt->data);
midorder(bt->rchild);
}
void lassorder(BiTree bt)
{ if(bt==NULL) return;
lassorder(bt->lchild);
lassorder(bt->rchild);
putchar(bt->data);
}
void DelTree(BTNode *bt)
{ if(bt==NULL) return;
DelTree(bt->lchild);
DelTree(bt->rchild);
delete(bt);
}
void init_Queue(SqQueue &Q)
{ Q.front=-1;
Q.rear=-1;
}
int enterQueue(SqQueue &Q,BiTree bt) {
if((Q.rear+1)%N==Q.front) return 0;
Q.rear=(Q.rear+1)%N;
Q.data[Q.rear]=bt;
return 1;
}
int empty(SqQueue &Q)
{ if(Q.front==Q.rear) return 1;
else
return 0;
}
BiTree delQueue(SqQueue &Q)
{ BiTree p;
Q.front=(Q.front+1)%N;
p=Q.data[Q.front];
return p;
}
void layertravel(BiTree bt)
{ BiTree p;
SqQueue Q;
init_Queue(Q);
if(bt==NULL) return;
enterQueue(Q,bt);
while(!empty(Q))
{ p=delQueue(Q);
putchar(p->data);
if(p->lchild) enterQueue(Q,p->lchild); if(p->rchild) enterQueue(Q,p->rchild); }
}
int main()
{ BiTree bt;
cout
bt=CrtBt();
cout
preorder(bt);
cout
cout
cout
cout
运行结果：