二叉树的四种遍历

二叉树的四种遍历

二叉树的遍历：前序遍历，中序遍历，后序遍历，层次遍历。不同的遍历方式有时是解决某些问题的有效工具，比如一个计算表达式以中序存储在二叉树中，用前序遍历可以得到前缀表达式（波兰表达式），后序遍历可以得到后缀表达式（逆波兰表达式）。而最能直观展现树的二维图形的遍历则是层次遍历。下面是自己的实现代码：

//存储的二叉树： /*        1       2       3    4    5    6   7   8 9 10 11            */
#include #includeusing namespace std;typedef struct btnode{    struct btnode *lch,*rch;    int date;}bttree;int len;bttree *bottom=new bttree();bttree* create(int A[],int i){        if(i>=len)return 0;        bttree *q=new bttree();        q->date=A[i];        q->lch=create(A,2*i+1);        q->rch=create(A,2*i+2);        return q;}void preorder(bttree *q){  //前序遍历    if(q){        cout<date<<" ";        if(q->lch)preorder(q->lch);        if(q->rch)preorder(q->rch);        }}void inorder(bttree *q){  //中序遍历    if(q){        if(q->lch)inorder(q->lch);        cout<date<<" ";        if(q->rch)inorder(q->rch);    }}void postorder(bttree *q){   //后序遍历    if(q){        if(q->lch)postorder(q->lch);        if(q->rch)postorder(q->rch);        cout<date<<" ";    }}bttree *nq=new bttree(),queue[100];int top=0,bn=0;  // top point and bottom pointvoid levelorder(bttree &q){ //层次遍历    *nq=q;    queue[++top]=*nq;    while(top>bn){  // is not empty        *nq=queue[++bn];        cout<date<<" ";        if(nq->lch)queue[++top]=*(nq->lch);        if(nq->rch)queue[++top]=*(nq->rch);    }}int main(int argc, char *argv[]) {    freopen("cout.txt","w",stdout);    int A[]={1,2,3,4,5,6,7,8,9,10,11},i=0;    len=11;    bottom=create(A,i);    cout<<"there are 4 orders: "<
输出：
there are 4 orders:  前序：1 2 4 8 9 5 10 11 3 6 7  中序：8 4 9 2 10 5 11 1 6 3 7  后序：8 9 4 10 11 5 2 6 7 3 1  层次：1 2 3 4 5 6 7 8 9 10 11

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。