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

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

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

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

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

4、前序遍历函数。

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

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

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

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

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

3. 判断两棵树是相等 最好能用递归算！！ 非二叉树！！！！

因为现实世界中存在这“树”这种结构——族谱、等级制度、目录分类等等，而为了研究这类问题，必须能够将树储存，而如何储存将取决于所需要的操作。这里有个问题，是否允许存在空树。有些书认为树都是非空的，因为树表示的是一种现实结构，而0不是自然数；我用过的教科书都是说可以有空树，当然是为了和二叉树统一。这个没有什么原则上的差别，反正就是一种习惯。

二叉树
二叉树可以说是人们假想的一个模型，因此，允许有空的二叉树是无争议的。二叉树是有序的，左边有一个孩子和右边有一个的二叉树是不同的两棵树。做这个规定，是因为人们赋予了左孩子和右孩子不同的意义，在二叉树的各种应用中，你将会清楚的看到。下面只讲解链式结构。看各种讲数据结构的书，你会发现一个有趣的现象：在二叉树这里，基本操作有计算树高、各种遍历，就是没有插入、删除——那树是怎么建立起来的？其实这很好理解，对于非线性的树结构，插入删除操作不在一定的法则规定下，是毫无意义的。因此，只有在具体的应用中，才会有插入删除操作。

节点结构
数据域、左指针、右指针肯定是必须的。除非很少用到节点的双亲，或者是资源紧张，建议附加一个双亲指针，这将会给很多算法带来方便，尤其是在这个“空间换时间”的时代。

template class T>

struct BTNode

{

    BTNode(T data = T(), BTNodeT>* left = NULL, BTNodeT>* right = NULL, BTNodeT>* parent = NULL)

        : data(data), left(left), right(right), parent(parent) {}

    BTNodeT> *left, *right, *parent;

    T data;

};

基本的二叉树类
template class T>

class BTree

{

public:

    BTree(BTNodeT> *root = NULL) : root(root) {}

    ~BTree() { MakeEmpty(); }

    void MakeEmpty() { destroy(root); root = NULL; }

protected:

    BTNodeT> *root；

private:

    void destroy(BTNodeT>* p)

    {

        if (p)

        {

            destroy(p->left);

            destroy(p->right);

            delete p;

        }

    }

}

二叉树的遍历
基本上有4种遍历方法，先、中、后根，逐层。当初我对这个很迷惑，搞这么多干什么？到了后面才明白，这是不同的应用需要的。例如，判断两个二叉树是否相等，只要子树根节点不同，那么就不等，显然这时要用先序遍历；而删除二叉树，必须先删除左右子树，然后才能删除根节点，这时就要用后序遍历。

实际上，搞这么多遍历方法，根本原因是在内存中储存的树是非线性结构。对于用数组储存的二叉树，这些名目繁多的方法都是没有必要的。利用C++的封装和重载特性，这些遍历方法能很清晰的表达。

1.         前序遍历......

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

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

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

先序非递归算法
【思路】
假设：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;
    }
}

6. 什么是二叉树的递归？

树的后序遍历是指先依次后序遍历每棵子树，然后访问根结点。当树用二叉树表示法(也叫孩子兄弟表示法)存储时，可以找到唯一的一棵二叉树与之对应，我们称这棵二叉树为该树对应的二叉树。那么根据这个法则可知，树的后序遍历序列等同于该树对应的二叉树的中序遍历。
从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上。
⑴访问结点本身（N），
⑵遍历该结点的左子树（L），
⑶遍历该结点的右子树（R）。
以上三种操作有六种执行次序：
NLR、LNR、LRN、NRL、RNL、RLN。
注意：
前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。
从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上。

扩展资料：

二叉树前序访问如下：
从根结点出发，则第一次到达结点A，故输出A;
继续向左访问，第一次访问结点B，故输出B；
按照同样规则，输出D，输出H；
当到达叶子结点H，返回到D，此时已经是第二次到达D，故不在输出D，进而向D右子树访问，D右子树不为空，则访问至I，第一次到达I，则输出I；
I为叶子结点，则返回到D，D左右子树已经访问完毕，则返回到B，进而到B右子树，第一次到达E，故输出E；
向E左子树，故输出J；
按照同样的访问规则，继续输出C、F、G。
二叉树中序访问如下：
从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出B；继续到达D，H；
到达H，H左子树为空，则返回到H，此时第二次访问H，故输出H；
H右子树为空，则返回至D，此时第二次到达D，故输出D；
由D返回至B，第二次到达B，故输出B；
按照同样规则继续访问，输出J、E、A、F、C、G。
参考资料来源：百度百科-二叉树
参考资料来源：百度百科-二叉树遍历

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

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

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