欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

二叉树的遍历算法(详细示例分析)

程序员文章站 2023-12-16 17:51:58
复制代码 代码如下:#include#include#include#includ...

复制代码 代码如下:

#include<iostream>
#include<assert.h>
#include<stack>
#include<queue>
using namespace std;
struct node
{
    int v;
    node *leftchild,*rightchild;
    node():leftchild(null),rightchild(null){}
    node(int vv):leftchild(null),rightchild(null)
    {
        v=vv;
    }
};

void print(int v)
{
    cout<<v<<"   ";
}
void preordertraverse(node *n, void (* visit)(int))
{
    assert(n!=null&&visit!=null);
    (*visit)(n->v);
    if(n->leftchild!=null) preordertraverse(n->leftchild,visit);
    if(n->rightchild!=null) preordertraverse(n->rightchild,visit);
}

void inordertraverse(node *n, void (* visit)(int))
{
    assert(n!=null&&visit!=null);
    if(n->leftchild!=null) inordertraverse(n->leftchild,visit);
    (*visit)(n->v);
    if(n->rightchild!=null) inordertraverse(n->rightchild,visit);
}

void postordertraverse(node *n, void (* visit)(int))
{
    assert(n!=null&&visit!=null);
    if(n->leftchild!=null) postordertraverse(n->leftchild,visit);
    if(n->rightchild!=null) postordertraverse(n->rightchild,visit);
    (*visit)(n->v);
}
//非递归版本,将递归改成非递归一般都要利用一个栈
//每次访问一个结点后,在向左子树遍历下去之前,利用这个栈记录该结点的右子女(如果有的话)结点的地址,
//以便在左子树退回时可以直接从栈顶取得右子树的根结点,继续右子树的遍历
void preorder(node *n, void (* visit)(int))
{
    stack<node*> sta;
    sta.push(n);
    while(!sta.empty())
    {
        node * t=sta.top();
        sta.pop();
        assert(t!=null);
        (*visit)(t->v);
        if(t->rightchild!=null) sta.push(t->rightchild);
        if(t->leftchild!=null) sta.push(t->leftchild);
    }
}

//非递归中序遍历
void inorder(node * n , void (* visit) (int))
{
    stack<node *> sta;
    sta.push(n);
    node * p= n;
    while(!sta.empty()&&p!=null)
    {
        p=sta.top();
        while(p!=null&&!sta.empty())
        {
            sta.push(p->leftchild);
            p=p->leftchild;
        }
        sta.pop();//弹出空指针
        if(!sta.empty())
        {
            p=sta.top();
            sta.pop();
            (*visit)(p->v);
            sta.push(p->rightchild);
        }
    }
}


//非递归后续遍历

struct stknode
{
    node * ptr;
    bool tag;//false=left and true=right
    stknode():ptr(null),tag(false)
    {}
};
void postorder(node * n ,void (*visit) (int))
{
    stack<stknode> sta;
    stknode w;
    node * p = n;
    do {
        while(p!=null)
        {
            w.ptr=p;
            w.tag=false;
            sta.push(w);
            p=p->leftchild;
        }
        bool flag=true;
        while(flag&&!sta.empty())
        {
            w=sta.top();
            sta.pop();
            p=w.ptr;
            if(!w.tag)//left,如果从左子树返回,则开始遍历右子树
            {
                w.tag=true;//标记右子树
                sta.push(w);
                flag=false;
                p=p->rightchild;
            }
            else
            {
                (*visit)(p->v);
            }
        }
    } while(!sta.empty());
}

//层序遍历,利用队列
void levelordertraverse(node * n , void (* visit )(int))
{
    assert(n!=null&&visit!=null);
    queue<node * > que;
    que.push(n);
    while(!que.empty())
    {
        node * t=que.front();
        (*visit)(t->v);
        que.pop();
        if(t->leftchild!=null) que.push(t->leftchild);
        if(t->rightchild!=null) que.push(t->rightchild);
    }
}

int main()
{
    node * head= new node(0);
    node * node1= new node(1);
    node * node2= new node(2);
    node * node3= new node(3);
    node * node4= new node(4);
    node * node5= new node(5);
    node * node6= new node(6);


    head->leftchild=node1;
    head->rightchild=node2;   
    node1->leftchild=node3;
    node1->rightchild=node4;
    node2->rightchild=node5;
    node4->leftchild=node6;

   
/*    levelordertraverse(head,print);
    cout<<endl;
    preordertraverse(head,print);
    cout<<endl;*/
    inorder(head,print);
    cout<<endl;
    inordertraverse(head,print);
    cout<<endl;

    postorder(head,print);
    cout<<endl;
    postordertraverse(head,print);
    cout<<endl;
    return 0;
}

上一篇:

下一篇: