用二叉树实现先序、中序、后序、层次遍历的算法

用二叉树实现先序、中序、后序、层次遍历的算法

用先序遍历建立一个二叉树，实现先序遍历、中序遍历、后序遍历，且用队列实现层次遍历： #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(!emp用二叉树实现先序、中序、后序、层次遍历的算法ty(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

运行结果：

【用二叉树实现先序、中序、后序、层次遍历的算法】相关文章：

序04-27

序04-28

霓裳中序第一赏析11-20

实Hilbert空间H中的一个新半序-φ半序04-29

层序的成因及层序地层格架05-02

莺啼序 用梦窗韵原文02-28

《序卦》卦序中的阴阳平衡互补与变通配四时思想04-30

《莺啼序》原文12-19

莺啼序原文02-28

莺啼序的原文03-01