精华内容
下载资源
问答
  • 非递归遍历二叉树

    千次阅读 2020-03-06 16:05:15
    非递归遍历二叉树

    需求:

    输入一个二叉树,采用非递归的方式,输出先序遍历的结果。

    测试用例:

    用以下层次遍历的序列代表二叉树

    1234567#8####9#####
    1234567########
    73914#####5#6##

    想法:

            众所周知,二叉树的遍历用递归写起来就三行,但是当题目要求非递归的时候就比较难了。手动的模拟一下二叉树的先序遍历,其实可以发现用递归写出来的程序,实际执行的时候是按照回溯法的方式实现的。

            而回溯法最好用栈实现,那么可以立即推非递归方法需要一个辅助栈,那么栈中元素都应该有什么呢?显然(想一想就知道了),栈中的每一个元素,除了树节点本身,还需要记录至少两个信息:当前节点的左子树是否访问完毕了,这里用has_get_left来表示,初始化是false,当左子树访问过以后就置位true;右子树依然。

            基于这个有三个项的栈,非递归的算法就可以比较直观的表达出来(用文字写起来比较麻烦,但是我又不会用电脑画图,建议在纸上简单的把逻辑画一下):在一个循环的过程中,首先入栈,两个标志位都默认flase,当左子树不空且左子树可以访问的时候,把左子树入栈,然后继续下一次循环,否则右子树进行同样的操作,直到最后栈空。

            这里值得一提的是,最开始的时候我是觉得直接用一个数组去模拟栈就好了,要不然还要写多写个pop、push两个函数怪麻烦的,然后实操起来发现用数组的话,在模拟入栈操作的时候还需要多写一部分清空脏数据的操作,实际上还不如最开始直接把最适合这个算法的栈写出来好用。

            由此可见,对于一个具体问题,选择一个最适合的结构是很重要的。模拟的终究是模拟的,下次遇见这种问题我当然还是用一个数组(哈哈哈)。

    源代码

    struct node{
        biTree* data;
        bool left_has_get ;
        bool right_has_get ;
        bool this_has_get;
        node* next;
    };
    void pre_travel_tree_norecursion(biTree* root)
    {
        if(root==NULL)
            return;
        node stack[20] ;
        for(int i = 0; i <20;i++)
        {
            stack[i].left_has_get = false;
            stack[i].right_has_get=false;
            stack[i].this_has_get = false;
        }
        int top = 0;
        stack[top].data = root; //用键值对的方式去思考
        while(top>-1)
        {
            if(!stack[top].this_has_get)
            {
                printf("%d  ",stack[top].data->data);
                stack[top].this_has_get = true;
            }
            // ------------------------------------
            //左子可访问,访问左子
            if(stack[top] .data->leftSon != NULL && (!stack[top].left_has_get ))
            {
                stack[top].left_has_get = true;
                stack[top+1].data = stack[top].data->leftSon;
                stack[top+1].left_has_get=false;
                stack[top+1].right_has_get=false;
                stack[top+1].this_has_get =false;
                top ++ ;

                continue;
            }
            //右子可访问,访问右子
            if(stack[top] .data->rightSon != NULL && (!stack[top].right_has_get ) )
            {
                stack[top].right_has_get = true;
                stack[top+1].data = stack[top].data->rightSon;
                stack[top+1].left_has_get=false;
                stack[top+1].right_has_get=false;
                stack[top+1].this_has_get =false;
                top ++ ;
                continue;
            }
            top -- ;

        }

    }

    展开全文
  • 非递归遍历二叉树(后序遍历) 在二叉树的遍历中,分为递归遍历与非递归遍历。非递归遍历的执行效率较高,时间复杂度小,因此采用非递归遍历有利于提高代码运行效率。 //后序遍历非递归实现 void ...

    非递归遍历二叉树(后序遍历)

    在二叉树的遍历中,分为递归遍历与非递归遍历。非递归遍历的执行效率较高,时间复杂度小,因此采用非递归遍历有利于提高代码运行效率。

    //后序遍历非递归实现 
    void PostOrderTraversal(BinTree BT) {
        BinTree T , PrePop = NULL; //PrePop记录上一个Pop出来的结点
        Stack S = CreatStack(MaxSize);//	创建堆栈 
        T=BT;
        while (T || !IsEmpty(S)) {
            while (T) {        //一直向左将结点压入堆栈
                Push(S, T);
                T = T->Left;
            }
            //将Pop的过程改为循环
            while (!IsEmpty(S)) { //后序遍历有两种情况可以Pop该结点
                T = Pop(S);
                if (T->Right == PrePop || T->Right == NULL) {  //该结点的右结点为空或
         //       者上一次Pop的是该结点的右结点
                   printf("%05d", T->Data);
                    PrePop = T;
                }
                else {  //若不满足以上两种情况 说明该节点右侧节点还未被Pop
                    Push(S, T);  //则将该结点重新压回堆栈
                    T = T->Right;  //然后指向该结点的右节点
                    break; //退出Pop循环
                }
            }
        }
        
    

    后序遍历需要访问左子树->右子树->根 所以要Pop某个根结点的条件是右结点已经被Pop或者右结点为NULL,
    如果不满足条件,则说明右侧结点还未被Pop,继续进行循环(PrePop变量记录上一个Pop的结点,并用于判断是不是当前结点的右结点)


    后序遍历的Pop过程可以是连续的,直到有不满足条件的结点出现才停止Pop过程,所以写成循环。

    展开全文
  • 非递归遍历二叉树 1.前言 ​ 总所周知,二叉树的遍历分为先序遍历、中序遍历和后序遍历。遍历的顺序不同,则结果不同。而遍历方法也分递归和非递归。而二者的复杂度相同:时间复杂度为O(nlgn),空间复杂度为O(n) 。 ...

    非递归遍历二叉树

    1.前言

    ​ 总所周知,二叉树的遍历分为先序遍历、中序遍历和后序遍历。遍历的顺序不同,则结果不同。而遍历方法也分递归和非递归。而二者的复杂度相同:时间复杂度为O(nlgn),空间复杂度为O(n)

    ​ 虽然递归的二叉树逻辑简单,但是通过递归调用可能会浪费多余的栈空间资源,因此非递归遍历也是十分有用的,相比起递归遍历,其会占用更少的栈资源。

    2.非递归遍历的实现

    ​ 非递归遍历二叉树是通过循环来实现的,在逻辑上相比起递归要稍微复杂一些,需要借用到stack(栈)数据结构。因为遍历时必须根节点往子节点循环,因此我们需要某类容器来存储上次循环节点的值,而栈这种类型数据结构恰恰能满足我们所需。

    ​ 那么如何利用栈来实现二叉树的非递归遍历呢?

    ​ 如果一个二叉树只有三个节点:根节点、左子节点、右子节点。那么所谓的先序遍历,就是先输出根节点、再输出左子节点、再输出右子节点;同理中序遍历,是输出左子节点、根节点、右子节点;后序遍历…。那么我们可以将三个节点按照我们想要的顺序依次推入栈中,再弹出,就能对三个节点进行先、中、后序遍历。例如:

    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
     };
    
    //三节点二叉树的先序输出
    stack<TreeNode *> sta;
    //中序和后序,只需要修改入栈的顺序
    sta.push(root->right);
    sta.push(root->left);
    sta.push(root);
    cout<<(sta.top())->val<<endl;
    sta.pop();
    cout<<(sta.top())->val<<endl;
    sta.pop();
    cout<<(sta.top())->val<<endl;
    sta.pop();
    

    ​ 那假设现在给这个二叉树的左子节点赋予左、右子节点,使得二叉树变为5节点的二叉树。那么原来3节点二叉树的先序遍历:根、根左、根右——就变成:根、根左、左左、左右、根右。会发现原来根节点的左子节点扩展成了三个,也就是包含了其左右子节点,而如果只看左子节点和它的子节点会发现,它们三个的顺序也是:根、左、右。

    ​ 我们现在可以得出一个结论,所谓的先序遍历、中序遍历、后序遍历不过是对一个节点以及它的左右子节点的遍历顺序罢了。那么我们把每三个节点:根、左、右当做一个整体,根据弹出栈的顺序,在循环遍历的时候将三个节点入栈,就能得到我们想要的遍历顺序。以下提供一种循环遍历二叉树的方法:

    ​ 该方法需要注意的一点:每个节点会被弹出两次栈,第一次被弹出是为了将左右子节点或者父节点入栈,第二次弹出是真正将其输出。

    //先序非递归遍历
    sta.push(root);//先把根节点入栈
    map<TreeNode*,bool> m;//定义一个键值对,用来判别该节点是否弹出过一次栈
    m.insert(make_pair(root,false));//如果值为false,则未被弹出过栈
    while(!sta.empty())//如果栈空,则说明遍历完成
    {
        p = sta.top();//弹出栈
        if(p == NULL)
            continue;
        sta.pop();
        
        if(m[p] == true)//如果值为true,则之前被弹出过一次栈
        {
            vec.push_back(p->val);
        }
        else
        {
            if(p->right != NULL)//右子节点入栈
            {
                m.insert(make_pair(p->right,false));
                sta.push(p->right);
            }
            if(p->left != NULL)//左子节点入栈
            {
                m.insert(make_pair(p->left,false));
                sta.push(p->left);
            }
            m[p] = true;//第一次弹出栈,将值设为true
            sta.push(p);//再次入栈
        }
    }
    

    ​ 以上是先序非递归遍历,如果需要中序、后序遍历,只需要修改入栈顺序。

    展开全文
  • 遍历二叉树 遍历二叉树的先序、中序和非递归遍历二叉树的六种算法
  • 使用非递归遍历二叉树,可以深刻的理解树的遍历,和递归原理. 以下代码比较多,非递归遍历需要一个栈,一个队列,其中也已经写好,不是用的c++stl. 可以深刻理解.需要学习的同学下载学习把. 代码:...

    使用非递归遍历二叉树,可以深刻的理解树的遍历,和递归原理.

    以下代码比较多,非递归遍历需要一个栈,一个队列,其中也已经写好,不是用的c++stl.

    自己用c语言写的可以深刻理解.需要学习的同学下载学习把.


    因为代码比较多,就没有贴在这边了

    代码:http://download.csdn.net/detail/hes_c/9860416

    展开全文
  • 实际上非递归的遍历方法很有用处,由于每次递归都需要将函数的信息入栈,当递归层数太深很容易就导致栈溢出,所以这个时候就必须用到非递归遍历二叉树了。而且,当看懂非递归遍历后,你会发现,其实非递归也很简单。...
  • 数据结构非递归先序、中序、后序遍历二叉树,数据结构非递归先序、中序、后序遍历二叉树
  • //后序非递归遍历二叉树 int otherstack[max];//辅助栈,用于检测出栈时是否已经遍历右子树 int *othertop,*otherbottom; tree temp; othertop=otherbottom=otherstack; while(LRD||!emptystack()) { ...
  • 原地址 http://www.jianshu.com/p/49c8cfd07410 更简单的非递归遍历二叉树的方法 解决二叉树的很多问题的方案都是基于对二叉树的遍历。遍历二叉树的前序,中序,后序三大方法算是计算机科班学生必写代码了。
  • java语言实现的二叉树的各种操作(包括递归与非递归遍历二叉树,求二叉树的高度,节点总数,叶子节点等)
  • 更简单的非递归遍历二叉树

    千次阅读 2015-04-09 20:26:10
    其递归遍历是人人都能信手拈来,可是在手生时写出非递归遍历恐非易事。正因为并非易事,所以网上出现无数的介绍二叉树非递归遍历方法的文章。可是大家需要的真是那些非递归遍历代码和讲述吗?代码早在学数据结构时就...
  • 非递归遍历二叉树(先序、中序、后序)   采用递归的方法实现三种遍历,不仅代码简洁且容易理解,但其开销也比较大,而若采用非递归方法实现三种遍历,则要用栈来模拟实现(递归也是用栈实现的)。  先序遍历...
  • 其递归遍历是人人都能信手拈来,可是在手生时写出非递归遍历恐非易事。正因为并非易事,所以网上出现无数的介绍二叉树非递归遍历方法的文章。可是大家需要的真是那些非递归遍历代码和讲述吗?代码早在学数据结构时就...
  • 1.借助栈,实现3种遍历的非递归算法。     2.层次遍历是自顶向下、自左至右的遍历二叉树中的元素,可以借助队列实现。 二、具体实现 #include<stdio.h> #include<stdlib.h> #...
  • 递归 和 非递归 遍历二叉树

    千次阅读 2013-08-22 16:29:54
    1 二叉树结点 2 先序遍历二叉树 3 中序遍历二叉树 4 后序遍历二叉树 5 测试样例 1 二叉树结点 struct BinaryTreeNode { int m_nValue;...BinaryTreeNode *m_pLeft;...先序遍历二叉树递归算法定义为: 若二叉树为空

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,407
精华内容 5,362
关键字:

非递归遍历二叉树