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

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

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

2. 二叉树的遍历非递归算法中应注意哪些问题

先序非递归算法
【思路】
假设：T是要遍历树的根指针，若T != NULL
对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。
问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取T的右子树的根指针？
方法1：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
方法2：访问T->data后，将T->rchild入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T->rchild，出栈，遍历以该指针为根的子树。
【算法1】
void     PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{     // 基于方法一，流程图如右，当型循环
    InitStack(S);
    while ( T!=NULL || !StackEmpty(S)){
       while ( T != NULL ){
          Visit(T->data) ;      
          Push(S,T);
          T = T->lchild;
       }

       if( !StackEmpty(S) ){
          Pop(S,T);
          T = T->rchild;
       }
    }
}
【算法2】
void     PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{     // 基于方法二，流程图如右，当型循环
    InitStack(S);
   
    while ( T!=NULL || !StackEmpty(S) ){
       while ( T != NULL ){
          Visit(T->data);
          Push(S, T->rchild);
          T = T->lchild;
       }
       if ( !StackEmpty(S) ){
          Pop(S,T);
       }
    }
}
进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。
中序非递归算法
【思路】
T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取T指针？
方法：先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。

【算法】
void     InOrder(BiTree T, Status ( *Visit ) (ElemType e))
{     // 流程图如右，当型循环
    InitStack(S);
   
    while ( T!=NULL || !StackEmpty(S) ){
       while ( T != NULL ){
          Push(S,T);
          T = T->lchild;
       }
       if( !StackEmpty(S) ){
          Pop(S, T);
          Visit(T->data);
          T = T->rchild;
       }
    }
}
进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。
后序非递归算法
【思路】

T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。
可采用标记法，结点入栈时，配一个标志tag一同入栈(0：遍历左子树前的现场保护，1：遍历右子树前的现场保护)。
首先将T和tag(为0)入栈，遍历左子树；返回后，修改栈顶tag为1，遍历右子树；最后访问根结点。
typedef struct stackElement{
Bitree     data;
char         tag;
}stackElemType;
【算法】
void     PostOrder(BiTree T, Status ( *Visit ) (ElemType e))
{     // 流程图如右，当型循环
    InitStack(S);
    while ( T!=NULL || !StackEmpty(S) ){
       while ( T != NULL ){
          Push(S,T,0);
          T = T->lchild;
       }
      
       while ( !StackEmpty(S) && GetTopTag(S)==1){
          Pop(S, T);
          Visit(T->data);
       }
       if ( !StackEmpty(S) ){
          SetTopTag(S, 1);         // 设置栈顶标记
          T = GetTopPointer(S);     // 取栈顶保存的指针
          T = T->rchild;
       }else break;
    }
}

3. 为什么说二叉树遍历用递归的方法不如非递归方法

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

4. 假设二叉树以二叉链表作为存储结构，试设计一个计算二叉树叶子结点树的递归算 法 要求用递归算法啊

1、首先要定义两个类：结点类和二叉树类。

2、二叉树类的组成：建立树的函数、遍历函数、删除函数。求结点数函数。

3、采用递归的思想，遇到标识符表示该结点为空，否则开辟空间创建新结点，同时调用递归开辟左结点和右结点。

4、前序遍历函数。

5、删除函数的思路：如果当前结点不为空，采用递归访问左结点和右结点、回收当前结点的空间。

6、求结点数函数的思路：如果当前结点为空，返回0、如果当前结点的左右孩子都为空，放回1。

7、求树高函数的思路：如果当前结点为空，返回0、递归访问左孩子和右孩子、比较左右孩子的高度，返回 较大值+1。

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

主要有三种遍历方法，先序遍历，中序遍历，后序遍历。
先序遍历：就是先访问根节点，再访问其左子树。最后访问右子树。
     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左边的全部都是它的左子树。。。
希望我的回答对你有所帮助。。。。。

6. 完全二叉树的算法

如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0=n2+1，则n= n0+n1+n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n= 2n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=(n+1)/2或n0=n/2。总结起来，就是 n0=[n/2]，其中[]表示上取整。可根据完全二叉树的结点总数计算出叶子结点数。

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

二叉树的结点结构是:
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
   你再对照的书上的算法想想，画画就应该能明白点。特别要理角的一点是为什么用递归算法时计算机能按这样的方式是因为函数调用是“先调用，后执行完”，或者说“后调用，先执行完”。注意我加一个“完”字

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

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