二叉树进阶复习1

一：二叉树基本操作思想

二：二叉树习题思想及其感悟

三：个人总结

一：二叉树基本操作思想

 

 

 思想：

1：求第k层的结点个数可求第k-1层的左右子树结点个数相加；（分治思想）；

2：看它的返回值条件：有root = NULL，和 k = 1，这两种情况；

 

 1：用变量接收返回值再进行返回，这样可以避免找到以后回溯上一层还要继续递归右子树寻找；

 2：使用最小数的单元，或者其他限制条件来确定数的返回。将一个大树看作一棵树来进行分治。

3：左边找完右边找完之后便可以进行直接到最外层。

 思想：

1：用变量承接可以防止后序中多次递归。

 

2：分治思想：将一颗复杂的大树化为一颗简单的树进行分治。

思想：

1：先将根结点放入队列中，然后出一个结点（按照先进先出的顺序）就将他的左右子树结点放入队列中； 循环操作直到队列为空。

 思想：

1：将一棵树的所有结点放入队列中。

2：出一个结点，再进它的左子树和右子树结点（无论它的结点为不为空）依次循环，当要出的结点为空时便退出循环。

3：退出循环后，判断后面的循环是否为空，如果都为空则为完全二叉树，有一个不为空，则为不完全二叉树。。

二：叉树习题思想及其感悟

1：二叉树最小深度： 为完全二叉树，公式为logn+1;

   ：二叉树最大深度： 为非完全二叉树，并且每层结点个数为1，深度为n；

2: 一颗完全二叉树： 只有度为2的结点和度为零的结点。

3：度与结点个数的关系，n - 1 =  n0 * 0 + n1 * 1 + n2 * 2 + n3 * 3;

   ： 总结点 n = n0 + n1 + n2 + n3；

常用这两个方程进行运算。

4：已知中序遍历求后序遍历

通过中序遍历来分左右区间；

再通过后序遍历来确定根；（ 后序通过刚开始也要花分左右区间依次定根）。

5：习题：

 

 思想：

1：分治思想：先看成一颗简单的子树，进行比较；

其中比较过程中有三种情况：

  （1）：两个都空

    (2) :   一个空一个不为空

  （3）：两个都在，但是要选能够根据题意快速得到结果的返回值。 

2：走到最后就是分别递归它的左子树和右子树看是否符合条件，（之后的每个子树都符合这个条件）。

 

思想：

1：将问题放入一颗简单的大树当中。

2：思考它的返回条件：

（1）：为空；

（2）： 不为空时，则比较它的的子树。

  (3):  最后放到整体分析，先比较整体的树，整体的树得不到答案时，再通过比较它的左子树和右子树来得出答案；。（一定要根据选择题意能够比较出结果的返回值）。

 

思想:遍历（也可用分治思想；）

1: 根据题意来写返回条件。

2：写出递归所要完成的内容。(有可能比较，判断，生结点）。

3：堪称一颗简单字数后，遍历一般要根据题意最后写返回值；（这是每个字数要做的）；

4:  当主函数要完成的内容过多时，可采用多个函数来完成各个任务。