二叉树的后序遍历，非递归

1. 二叉树的后序遍历，非递归

后序遍历的非递归步骤类似于中序遍历，在遍历左子树前将根结点指针送入栈中
但是左子树遍历完成后，无法访问根结点，只有在右子树遍历完后，才能访问根结点

如果不使用标志位区分第几次到达根结点，可以利用如下的后序遍历特征来完成：
当栈顶元素(根)的右子树为空(即：无右孩子)，或者是右子树非空但是已遍历完，即右孩子恰好是刚才访问过的结点，此时应访问栈顶结点，并在访问后退栈
否则，如果栈顶元素的右孩子非空且未遍历，此时直接访问栈顶元素的右孩子而不退栈

算法要点只是需要记住最近访问过的结点即可，也就是每次访问一个结点后，就记住这个结点

2. 二叉树的中序遍历非递归的一道题

请点击输入图片描述
选择答案A

3. 二叉树中的层序遍历?

层次遍历就是按二叉树的每一层的顺序来遍历，也就是先访问根结果，然后访问第一层，接着访问第二层...
38题应选:B。大致是先从层次上看出二叉树的根结点为然后从中序中可以看出DBA为左边的结点，CE为右边的结点。然后结合两个可以发现D、E分别是第二层的左右子结点。而B，A则分别为第三层第四层的右结点，C是第三层上的左结点。

4. 关于二叉树的递归遍历还是不理解 那位高手能不能详细讲一下！！！

主要有三种遍历方法，先序遍历，中序遍历，后序遍历。
先序遍历：就是先访问根节点，再访问其左子树。最后访问右子树。
     A
    /    \
  B      C
 /  \     /  \ 
D    E F  G                 
对于遍历来说无论是哪种遍历，采取的思路是遍历左子树和右子树的时候，把左子树和右子树当成一棵新的完整的二叉树来对待，按照指定的遍历方法进行遍历，就比较容易理解了。
例如：先序遍历
1、首先访问根节点A，然后接下来要去访问它的左子树
2、将它的左子树当成一棵完整的二叉树：
  B      
 /  \  

D  E             
这个你要采用先序来进行遍历的话，还是先遍历根节点，然后左子树，然后右子树。那么这个时候必定要先访问根节点B了。
3、再将B的左子树当成一棵新的二叉树：
D
由于其没有子树了，就只有一个根节点。所以这个时候就访问这个根节点D
4、同样的道理再去访问B的右子树E。
5、到这个地方，对于根节点A的左子树才完整遍历了。
6、同样的道理接着去访问A的右子树，还是将它的右子树当成一个新的二叉树，进行遍历。遍历结果是CFG。
7、最终的遍历结果就是ABDECFG。
/* 我的理解是递归A->B->D,然后就回到A了，怎么到了B就停了 去访问E，就是这点我不理解 ，请你帮我理一下思路，到底是怎么回事啊？？？*/
你的理解只是单纯的理解为访问左子树的时候，只是左边的是它的左子树，其实在访问的时候只要是处在A左边的全部都是它的左子树。。。
希望我的回答对你有所帮助。。。。。

5. 如何不用递归遍历二叉树

非递归的方法是用存储代替计算，就是在建立树时，实现了存储展开，相当于存储了未来需要遍历的路径，所以就快了。递归是送快递，一层层往下递，非递归是先建好区域仓库，由各地仓库储存发货，所以速度更快，但需要仓库储存（内存占用更多）。
二叉树遍历在数据结构中用得多，这种算法是从kb时代的内存来的，主要用于理解概念，提升编程时的思想用。
实际用途中
如果用于商业一般用数据库代替，根本用不到二叉树，是用存储代替计算。速度快，可以用内存数据库，如我用h2 database的Memory Mode 在java下可以实现1秒1百万次插入。用sqlite内存模式代替以前在c++需要手工管理的数据结构。数据量大一个电脑存不下时，用hadoop/spark/redis，对分布式大数据支持比较好。
如果用于计算量大的任务或内核结构，可以用矩阵数组，链表，k/v这种比较直观模式存储。
对于树和图这种在内存中复杂的数据结构，尽量不要在生产环境下使用，容易内存泄露，用简单方式代替。对于图结构，可以使用图数据库，如neo4j。对于树结构，可以在数据库中存储一棵树。实际上数据库的存储多用树，如B树、B-树、B+树、B*树。
当然如果你写加密算法，这种要求极高的程序时，还是需要考虑性能最大化的，否则一般用存储代替遍历计算，因为内存和硬盘，现在很便宜了，而cpu还是一种宝贵的资源。

6. 二叉树非递归后序遍历的思路是什么

前序：根-左-右；
中序：左-根-右；
后序：左-右-根。

遍历的思路有3个重点：
1）利用堆栈实现递归
2）树中结点要有指向父结点的指针    //后序遍历用不上这一条

3）树中结点要有标志记录是否已被访问过

上述3点其实就是自己来完成原来递归实现中系统帮你做的事
还有一点要注意，是“左-右-根”， 压栈就要先右后左


Class B-Tree{
    B-Tree left;
    B-Tree right;
    B-Tree father;
    Boolean visited = false;   //初始值设为false

       value;  //树中存的值，可以是任何类型

}


Stack s;
B-Tree t;   //要遍历的树


s.push(t)
while (!s.empty()){
    Boolean hasChildren = false;  //hasChildren是有子结点需要处理的意思 

    t = s.top();
    if(t.right  null &&  ! t.right.visited) { 
        s.push(t.right);
        hasChildren = true;

    }
    if (t.left null  ! t.left.visited){
        s.push(t.left);
        hasChildren = true;
    }
    if (! hasChildren) { 
        out.print(t.value);   // 输出结点
        t.visited = true;
        s.pop();

    }
}

7. 非递归的二叉树前序遍历算法有什么用途

递归和非递归只是解决问题的方法的不同，本质还是一样的。
2. 递归算法相对于非递归算法来说效率通常都会更低
2.1 递归算法会有更多的资源需要压栈和出栈操作（不仅仅是参数，还有函数地址等）
2.2 由于编译器对附加的一些栈保护机制会导致递归执行的更加低效
3. 使用循环代替递归算法，通常可以获得更好的执行效率和空间效率，在二叉树层次较深的情况下，采用非递归方式遍历能够有效的提升遍历的性能。

8. 先序遍历二叉树的递归算法怎样理解？

二叉树的结点结构是:
1、根结点（存放结点数据）
2、左子树指针
3、右子树指计
对二叉树的遍历就是访问各个结点中根结点里存放的数据。例如：
    如果结点A有左结点B，右结点C，记作A(B,C)，不同结点我用"\"隔开。那么有这样一个(BitTree)二叉树表A(B,C) \B（D,E)\E(F.G)\C(空,H)\H(I.空)， 自己画出来，不然我后面白讲了。
    要想把所有的数据都访问到则必需按照一定的原则，即当前结点的下一个结点是哪个结点。
       无论是先、中还是后序算法都是先将左结点视为下一个结点，当左结点不存在（即为空时）才将右结点视作下一个结点，如果右结点也不存在就返回当前结点的上层结点再向右访问，如此类推。
   于是对二叉树的遍历问题就被抽象成三个基本步骤:
1、访问根结点。
2、访问该点的所有左子树。
3、访问该点的所有右子树。
   先序遍历的策略是按123的步骤执行，中序是按213来，后序则是231,它们之间的不同只是“访问根结点”在这三个步骤中的位置。
   看着你刚画好的那个BitTree跟着我的思路走。在先序遍历算法PriorOrder中,先将BitTree的头结点A传进来，按步骤123的处理。123是抽象实现，记住所表达的思想，下面是具体实现。为了避免混乱用中文数字记录步骤。
一、即是读取结点A的数据内容A（此时A为当前函数处理结点)，将A的右结点C放入栈S中，S中的内容为S（C）[注意这一步是算法的一个辅助，并不是先向右访问,下同]，将左结点B传给PriorOrder处理。此时读取了A
二、读取B的内容B（此时B为当前结点），将B的右结点E放入S中，S中的内容为S(C,E),将B的左结点D传给PriorOrder处理。此时读取了AB
三、D为当前结点，D的右为空没有东西放入S，S中的内容仍为S(C,E)，D的左也为空，没有访问可访问的。此时就从S中取出E(因为栈是先进后出的所以取的就是E，此时S中的内容为S(C),正好是上一层没访问过的右子树)，将E传给PriorOrder处理。此时读取了AB D
四、E为当前结点，对于结点E类似的有S(C,G),读取了ABDE,将F传入PriorOrder
五、F为当前结点，右为空，左也为空，读取了ABDEF,从栈中取出G传给PriorOrder处理,S的内容为S(C);
六、类似的读取了ABDEFG,从S中取出了C，传给PriorOrder处理。此时S（）。
七、当前结点为C，从将C的右结点放入S，S中内容为S(H),C的左为空，从S取出H，将H传给PriorOrder处理。此时S为S().于是就读取了ABDEFGC
八，类似的读取了ABDEFGCH
九，最后ABDEFGCHF
   你再对照的书上的算法想想，画画就应该能明白点。特别要理角的一点是为什么用递归算法时计算机能按这样的方式是因为函数调用是“先调用，后执行完”，或者说“后调用，先执行完”。注意我加一个“完”字