手机版
你好,游客 登录 注册
背景:
阅读新闻

二叉树先序中序非递归算法

[日期:2014-06-10] 来源:Linux社区  作者:海子 [字体: ]

一直想要写的 二叉树 中序 先序 后序遍历算法

当年学习DS最虚的就是这个,因为非递归算法复杂,测试数据不好弄,只能一个一个手动插入。感觉明显比图的难,虽然大家都觉得图更难。。。。。

递归的太简单了,就不写了。关键是非递归版本。

二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm

Java中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm

先序:

我自己的版本:

void RootPreTraverse(Node* p)
{
 Stack S;
 while(S not empty)
 {
  p=S.top();
  S.pop();
  Show(p);
  if(p->right!=null)
   S.push(p->right);
  if(p->left!=null)
   S.push(p->left);
 }
}

后来发现和层序遍历有点相似,区别就在于 用了栈而不是队列,而且入的顺序换一换,否则到时出栈就错了。

感觉有点微妙,虽然比较容易写出来,但是还是有点悬乎,队列换栈差异这么大!

这个版本(感觉不好写)  http://www.linuxidc.com/Linux/2014-06/102935p2.htm

void BT_PreOrderNoRec(pTreeT root)
{
    stack<treeT *> s;


    while ((NULL != root) || !s.empty())
    {
        if (NULL != root)
        {
            visit(root);
            s.push(root);
            root = root->left;
        }
        else //该版本代码相比于下面比较清sang,
        {
            root = s.top();
            s.pop();
            root = root->right;
        }
    }
}

下面这个和上面是一个思路 http://www.linuxidc.com/Linux/2014-06/102935p3.htm

void preorder_dev(bintree t){ 
    seqstack s; 
    s.top = -1;    //因为top在这里表示了数组中的位置,所以空为-1 
    if(!t){ 
        printf("the tree is empty\n"); 
    }else{ 
        while(t || s.stop != -1){ 
            while(t){    //只要结点不为空就应该入栈保存,与其左右结点无关     
                  printf("%c ",t->data); 
                push(&s,t); 
                t= t->lchild; 
            }  //令有一个版本 http://www.linuxidc.com/Linux/2014-06/102935p4.htm ,这里加了判断if(S not empty()), 感觉有点画蛇添足。因为此处如果栈为空则说明上面while 一定没执行,t为空,同时S empty()那么上一次外层while已经退出了,遍历结束了。可见,此处栈必不空,上面url楼主加了一个永真判断
            t=pop(&s); 
            t=t->rchild; 
        } 
    } 
}

中序:http://www.linuxidc.com/Linux/2014-06/102935p2.htm

01.void BT_InOrderNoRec(pTreeT root) 
02.{ 
03.    stack<treeT *> s; 
04.    while ((NULL != root) || !s.empty()) 
05.    { 
06.        if (NULL != root) 
07.        { 
08.            s.push(root); 
09.            root = root->left; 
10.        } 
11.        else 
12.        { 
13.            root = s.top(); 
14.            visit(root); 
15.            s.pop(); 
16.            root = root->right; 
17.        } 
18.    } 
19.} 

//和上面preorder_dev 几乎如出一辙,从一个show 的地方就可以看出本质区别,赞博主

void midorder(bintree t){ 
    seqstack s; 
    s.top = -1; 
    if(!t){ 
        printf("the tree is empty!\n"); 
    }else{ 
        while(t ||s.top != -1){ 
            while(t){ 
                push(&s,t); 
                t= t->lchild; 
            } 
            t=pop(&s); 
            printf("%c ",t->data); 
            t=t->rchild; 
        } 
    } 
}

后序由于有点复杂,先搁置,集中力量打击主要部分。

从逻辑上看,两人其实是一样的,如果t不空,执行if,到while 因此次数if 等价于里面执行while,如果t空,则执行else,与另一个代码一致

另外看这里 http://www.linuxidc.com/Linux/2014-06/102934.htm

递归转非递归的模式其实不大general。。所以这个还得暂时没有通用方法。。。

后序

//用一个标志位记录是否 左右孩子是否已经被压过栈,如果压过栈了,如果没压栈,会先压站,然后再把该节点压站,因为后面

还要访问(后序),此外还需要把标志位

void PostOrder(TNode* root)
{
    Stack S;
    if( root != NULL )
    {
        S.push(root);
    }
    while ( !S.empty() )
    {
        TNode* node = S.pop();
        if ( node->bPushed )
        {  // 如果标识位为true,则表示其左右子树都已经入栈,那么现在就需要访问该节点了
            Visit(node);       
        }
        else
        {  // 左右子树尚未入栈,则依次将 右节点,左节点,根节点 入栈
            if ( node->right != NULL )
            {
                node->right->bPushed = false; // 左右子树均设置为false
                S.push(node->right);
            }
            if ( node->left != NULL )
            {
                node->left->bPushed = false;
                S.push(node->left);
            }
            node->bPushed = true;            // 根节点标志位为true
            S.push(node);
        }
    }
}

更多详情见请继续阅读下一页的精彩内容http://www.linuxidc.com/Linux/2014-06/102935p2.htm

linux
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款