二叉树详解

二叉树

度： 结点拥有子树的个数
叶子节点：没有子节点的节点
树的深度：节点的层数， 根节点默认为第一层。
有序 ：树的左右位置不能改变。

二叉树常被用作二叉查找树和二叉堆

性质１：在非空二叉树的第i层至多有2^{i-1}个结点
性质２：深度为k的二叉树至多有2^k-1个结点
性质３：对任何一棵二叉树Ｔ,如果其中终端节点数为n0,度数为２的节点数为ｎ2，则n0 = n2 + 1（n0表示度数为0的节点总数， n2表示度数为2的节点总数）
性质４：在完全二叉树中，具有n个节点的完全二叉树的深度为[log2n]+1，其中[log2n]+1是向下取整。
性质５：若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：
(1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点;  
(2) 若 2i>n，则该结点无左孩子，  否则，编号为 2i 的结点为其左孩子结点；
(3) 若 2i+1>n，则该结点无右孩子结点，  否则，编号为2i+1 的结点为其右孩子结点。

满二叉树

除了叶结点外每一个结点都有左右子叶且叶结点都处在最底层的二叉树,。   
一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树

完全二叉树

 叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树

完全二叉树是效率很高的数据结构，堆是一种完全二叉树或者近似完全二叉树，所以效率极高，像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化，几乎每次都要考到的二叉排序树的效率也要借助平衡性来提高，而平衡性基于完全二叉树。

叶子结点只可能在最大的两层上出现,对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L 或 L+1。

具有n个结点的完全二叉树的深度为int（log2n）+1

出于简便起见,完全二叉树通常采用数组而不是链表存储:

（1）若i为奇数且i>1，那么tree的左兄弟为tree[i-1]；
（2）若i为偶数且i<n，那么tree的右兄弟为tree[i+1]；
（3）若i>1，tree的父亲节点为tree[i div 2]；
（4）若2*i<=n，那么tree的左孩子为tree[2*i]；若2*i+1<=n，那么tree的右孩子为tree[2*i+1]；
（5）若i>n div 2,那么tree[i]为叶子结点（对应于（3））；
（6）若i<(n-1) div 2.那么tree[i]必有两个孩子（对应于（4））。
（7）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。  

平衡二叉树

• 平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是二叉搜索树，反之则不一定。
• 二叉树的每个节点的左子树减去右子树定义为该节点的平衡因子。二叉平衡树的平衡因子只能是1、0或者-1。
• 平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。
• 二叉搜索树有一个缺点就是，树的结构是无法预料的，随意性很大，它只与节点的值和插入的顺序有关系，往往得到的是一个不平衡的二叉树。在最坏的情况下，可能得到的是一个单支二叉树，其高度和节点数相同，相当于一个单链表，对其正常的时间复杂度有O(lb n)变成了O(n)，从而丧失了二叉排序树的一些应该有的优点。
• 其高度一般都良好地维持在O（log（n）），大大降低了操作的时间复杂度。
• 当插入一个新的节点的时候，在普通的二叉树中不用考虑树的平衡因子，只要将大于根节点的值插入到右子树，小于节点的值插入到左子树，递归即可。而在平衡二叉树则不一样，在插入节点的时候，如果插入节点之后有一个节点的平衡因子要大于2或者小于-2的时候，他需要对其进行调整，现在只考虑插入到节点的左子树部分（右子树与此相同）
• 平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。
• 采用平衡树的优点是：使树的结构较好，从而提高查找运算的速度。缺点是：是插入和删除运算变得复杂化，从而降低了他们的运算速度。

遍历方式

前序遍历

规则是若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树。
应用场景：判断两个二叉树是否相等，只要子树根节点不同，那么就不等

中序遍历

规则是若二叉树为空，则空操作返回，否则从根节点开始（注意并不是先访问根节点），中序遍历根节点左子树，然后访问根节点，最后中序遍历右子树

后序遍历

        规则是若二叉树为空，则空操作返回，否则从左到右先叶子后节点的方式遍历左右子树，最后访问根节点　　
        应用场景：删除二叉树，必须先删除左右子树，然后才能删除根节点

层次遍历

        规则是若二叉树为空，则空操作返回，否则从树的第一层，也就是根节点开始访问，从上到下逐层遍历，在同一层中，按照从左到右的顺序对节点逐个访问

已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树
已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树

线索二叉树

• n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"），这些指针称为线索，加上线索的二叉树称为线索二叉树。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。
• 二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构，使每个结点都有了唯一前驱和后继（第一个结点无前驱，最后一个结点无后继）
• 建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前的左，右指针域是否为空，将它们改为指向前驱结点或后续结点的线索。为实现这一过程，设指针pre始终指向刚刚访问的结点，即若指针p指向当前结点，则pre指向它的前驱，以便设线索。
  另外，在对一颗二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的根结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。
• 在遍历二叉树的同时，使用二叉树中空闲的内存空间记录某些结点的前驱和后继元素的位置（不是全部）。这样在算法后期需要遍历二叉树时，就可以利用保存的结点信息，提高了遍历的效率。使用这种方法构建的二叉树，即为“线索二叉树”
• 线索化的过程即为在遍历的过程中修改空指针的过程。
• LTag 和 RTag 为标志域。实际上就是两个布尔类型的变量：
  LTag 值为 0 时，表示 lchild 指针域指向的是该结点的左孩子；为 1 时，表示指向的是该结点的直接前驱结点；
  RTag 值为 0 时，表示 rchild 指针域指向的是该结点的右孩子；为 1 时，表示指向的是该结点的直接后继结点。