数据结构：二叉树的操作

二叉树采用二叉链表的数据结构，实现以下操作：

• 二叉树的构建与销毁：
  先构造根结点，再构造左子树，再构建右子树，用‘#’表示空，定义一个索引，构造完根结点，索引往后走，++，再构造左子树，递归调用，完成后索引++，构造右子树

• 二叉树的拷贝
  首先定义一个新的二叉树，按照前序遍历的顺序先拷贝根结点，之后拷贝根结点的左子树，然后拷贝根结点的右子树，利用递归进行每层的拷贝，直到当前根结点为空

• 二叉树的销毁
  按照后序遍历的方式，先销毁右子树，再销毁左子树，最后销毁根结点

• 二叉树的先序、中序、后序遍历
  二叉树的三个遍历采用递归方法，先序表示先遍历根结点，再遍历左子树，然后遍历右子树，中序表示先遍历左子树，再遍历根结点，再遍历右子树，后序表示先遍历左子树，再遍历右子树，再遍历根结点，例如：
  
  此二叉树先序遍历递归过程为到达A，不为空，输出A，调用左子树到达B,不为空，输出B，调用B的左子树到达D,不为空，输出D，调用D的左子树，为空，返回空，到达D,调用D的右子树，为空，返回到D，D返回到B,调用B的左子树，到达E，输出E,调用E的左子树，为空，返回空到E，调用E的右子树到H，输出H，调用H的左子树，为空，返回空，调用H的右子树，为空，返回空到E,E返回到B，B返回到A，接着以此类推调用A的右子树。
  中序遍历与后序遍历也以此类推，不同的是，中序遍历先调用左子树，再打印根结点，后序遍历先调用左子树，再调用右子树，再打印根结点。

• 前序遍历非递归
  创建一个栈，利用栈先进后出的原则，以上图为例，首先，定义一个指针指向根结点A，先打印根结点的值A，将A入栈，之后遍历A的左子树,到B，打印B，将B入栈，遍历B的左子树，打印D，将D入栈，遍历D的左子树，为空，取栈顶元素D，出栈，遍历D的右子树，为空，取栈顶元素B，出栈，遍历B的右子树，到达E,打印E ,E入栈，遍历E的左子树，为空，取栈顶元素E，出栈，遍历E的右子树，到H，打印H的值，H入栈，遍历H的左子树，为空，取栈顶元素H，出栈，遍历H的右子树，为空，取栈顶元素A，出栈，遍历A的右子树到达C，打印C，将C入栈，遍历C的左子树，到达F，打印F，将F入栈，遍历F的左子树，为空，取栈顶元素F，出栈，遍历F的右子树，为空，取栈顶元素C，出栈，遍历C的右子树，到达G，打印G，将G入栈，遍历G的左子树，为空，取栈顶元素G,出栈，遍历G的右子树，为空，栈为空，退出外层循环，结束

• 中序遍历非递归
  与前序遍历类似，创建一个栈，以上图为例，定义一个指针指向根结点A，将A入栈，遍历A的左子树，到达B，将B入栈，遍历B的左子树，到达D，将D入栈，遍历D的左子树，为空，取栈顶元素D，打印D，出栈，遍历D的右子树，为空，取栈顶元素B，打印B，出栈，遍历B的右子树，到达E，将E入栈，遍历E的左子树，为空，取栈顶元素E，打印E，出栈，遍历E的右子树，到达H，将H入栈，遍历H的左子树，为空，取栈顶元素H，打印H，出栈，遍历H的右子树，为空，取栈顶元素A，打印A，遍历A的右子树，到达C，C入栈，遍历C的左子树，到达F，F入栈，遍历F的左子树，为空，取栈顶元素F，打印，出栈，遍历F的右子树，为空，取栈顶元素C，打印，出栈，遍历C的右子树，到达G，G入栈，遍历G的左子树，为空，取栈顶元素G，打印，出栈，遍历 G的右子树，为空，栈为空，结束

• 后序遍历非递归
  创建一个栈，定义一个指针指向根结点A，定义一个last指针用来保存上一个左右子树已经遍历过的结点，A入栈，遍历A的左子树到达D，不为空，入栈，遍历D的左子树，为空，取栈顶元素D，D的右孩子为空，D出栈，打印D，last指向D，取栈顶元素B，B的右孩子为E，不为空，也不为last所指向的结点D，遍历B的右子树，到达E，E入栈，遍历E的左子树，为空，取栈顶元素E，E的右孩子为H，不为空也不为last所指的结点，遍历E的右子树，到达H，H入栈，遍历H的左子树，为空，取栈顶元素H，H的右孩子为空，H出栈，打印H，last指向H，取栈顶元素E，E的右孩子为last指向的结点H，E出栈，打印E，last指向E，取栈顶元素B，B的右孩子为last指向的E，B出栈，打印B，last指向B，取栈顶元素A，A的右孩子不为空，也不为last指向的结点，遍历A的右孩子，到达C，C入栈，遍历C的左孩子，到达F，F入栈，遍历F的左孩子，为空，取栈顶元素F，F的右孩子为空，F出栈，打印F，last指向F，取栈顶元素C，C的右孩子不为空，也不为last指向的结点，遍历C的右孩子，到G，G入栈，遍历G的左孩子，为空，取栈顶元素G，G的右孩子为空，G出栈，打印G，last指向G，取出栈顶元素C，C的右孩子为last指向的G，C出栈，打印C，last指向C，取出栈顶元素A，A的右孩子为last指向的C，A出栈，打印A，last指向A，栈此时为空，结束

• 二叉树的层序遍历
  二叉树的层序遍历要用到队列，从队头出，从队尾进，先让二叉树的第一个根结点进入队列，取队头元素，输出队头元素，如果队头元素的左孩子不为空，入队列，如果该节点的右孩子不为空，入队列，实现此循环，直到队列为空，例如上图，先让A入队，取出队头节点，打印A，A的左孩子不为空，即让B入队，A的右孩子不为空，即让C入队，取出队头节点B，打印，B的左孩子不为空，即让D入队，B的右孩子不为空，即让E入队，取出队头元素C，打印，C的左孩子不为空，即让F入队，C的右孩子不为空，即让G入队，取出队头元素D，打印，D的左右孩子为空，不用操作，取出队头元素E，打印，E的右孩子不为空，即让H入队，取出队头元素F，打印，F的左右孩子为空，不操作，取出队头元素G，打印，G的左右孩子为空，不操作，取出队头元素H，打印，H的左右孩子为空，不操作，此时队列为空，结束。

• 求二叉树的高度
  再以上图为例，求二叉树的高度是求出根结点左右子树的高度，比较得到最大的再加根结点所占的一层的高度，递归过程为先到达根结点，不为空，调用A的左子树，到达B,调用B的左子树到达D，调用D的左子树，为空，返回0到D,调用D的右子树，为空，返回0到D，D已经调用完，返回1到B，调用B的右子树，到E，调用E的左子树，为空，返回0到E，调用E的右子树到H，调用H的左子树，为空，返回0到H，调用H的右子树，为空，返回0到H，H已经调用完，返回1到E，E已经调用完，比较E的左右子树高度，加上E所占层高度1，返回2到B，B已经调用完，比较B左右子树的高度，右子树高，加上B所占层的高度1，返回4到A，A的右子树以此类推，最后得到二叉树高度为4.

• 求二叉树的结点个数
  求二叉树的结点个数，采用递归方法，采用上图，有两种方法，第一种方法是分别求出根结点左子树的结点个数和右子树的结点个数，再加上根结点的个数；第二种方法是当遇到当前二叉树的根结点时，count++，即是采用先序、中序、后序任意一种遍历。

• 求二叉树的叶子结点个数
  叶子结点是没有左右孩子的结点，即它的终止条件是当一个结点没有左右孩子时，返回1，以上图为例，进入二叉树，遇到A,它不为空，有左右孩子，调用左子树，到达B，有左右孩子，调用，到达D，D没有左右孩子，返回1到B，调用B的右子树到达E，E有右孩子，调用右子树到H，H没有左右孩子，返回1到E，E返回1到B，B返回1+1=2到A，调用A的右子树，到C，C有左右孩子，调用C的左子树，到F，F没有左右孩子，返回1到C，调用C的右子树，到G，G没有左右孩子，返回1到C，C返回1+1=2到A,则此二叉树有2+2个叶子结点。

• 判断一棵树是否为平衡二叉树（两种方法性能不同）
  平衡二叉树就是左子树与右子树的高度之差为1、-1、0的二叉树，如果二叉树为空，返回true，如果左右子树不是平衡二叉树，返回false，一种方法是判断平衡二叉树，先计算出当前根节点的左右子树的高度，如果高度之差大于1，小于-1，返回false，否则返回true，一直调用，直到遇到终止条件；而这种方法性能比较差，每一格结点都要求它的高度，最终时间复杂度为O(n^2),而另外一种方法是从下往上看，先验证根结点的左右子树是否平衡，记录下来，如果都平衡并且高度差的绝对值小于2，返回true，否则返回false

• 二叉树查找指定值的结点地址
  当二叉树为空时，返回空，当根结点的值为指定值时，返回根节点，或者调用左子树，否则调用右子树，例如找上图的F，进入二叉树，A不为空，也不为指定值，调用左子树，到达B，不为空，也不为指定值，调用左子树，到达D，不为空，也不为指定值，调用左子树，到达空，返回空到D，调用D的右子树，为空，返回到D，D左右子树已经调用完成，返回空到B，B调用右子树，到E，E不为空，也不为指定值，调用E的左子树，为空，返回空到E，调用E的右子树，到达H，不为空，也不为指定值，调用H的左子树，为空，返回空到H，调用H的右子树，为空，返回空到H，H的左右子树调用完成，返回空到E，E的左右子树调用完成，返回空到B，B的左右子树调用完成，返回空到A，调用A的右子树到C，C不为空，也不为指定值，调用C的左子树到F，为指定值，返回F的地址到C，调用C的右子树，到G，不为空，也不为指定值，调用G的左子树，返回空到G，调用右子树，返回空到G，G的左右子树调用完成，返回空到C，C的左右子树调用完成，返回F的地址到A，A返回F的地址。

• 查找指定结点的双亲节点
  首先利用二叉树查找指定结点函数指定结点，如果两个结点有一个为空，返回false，如果指定结点就是根结点，返回false，如果根结点的任意一个孩子为指定结点，那这个根结点就是指定结点的双亲节点，否则取根结点的左子树递归，如果没有，去右子树递归。

• 求二叉树第k层上的结点个数
  首先k应该大于1，如果k等于1，返回1，否则调用左子树，如上图，查找第3层的结点个数，调用A的左子树到达B，到达B相当于找B的第二层，调用B的左子树到达D，相当于D的第一层，返回1到B，调用B的右子树到E，相当于E的第一层，返回1到B，B左右子树调用完成，返回1+1=2到A，调用A的右子树，到C，相当于C的第二层，调用C的左子树，到F，相当于F的第一层，返回1到C，调用C的右子树，到G，相当于G的第一层返回1到C，C返回1+1=2到A，A返回2+2=4，即第3层的结点个数为4.

• 判断二叉树是否为完全二叉树
  完全二叉树指层序遍历只要碰到空节点，后面的节点一定为空，即进行层序遍历，但是循环结束条件不为队列为空，因为遇到空时，结束，如果有队头元素不为空，即不是完全二叉树。
  注：其他相关操作见二叉树面试题博客
  https://blog.csdn.net/qq_41809901/article/details/96296562

源代码见下（github）：
https://github.com/wangbiy/DS/tree/master/test_2019_7_17_1