⼆叉树详解
1.这⾥就不介绍⼆叉树的相关概念，如，树⾼度，节点层数，节点度数，路径，叶节点，分⽀节点，根节点，⽗节点，左节点，右节点，兄弟节点，祖先节点，⼦孙节点，左⼦树，右⼦树等基本概念
2.⼆叉树的分类
(1).斜树
斜树：所有的结点都只有左⼦树的⼆叉树叫左斜树。所有结点都是只有右⼦树的⼆叉树叫右斜树。这两者统称为斜树。
左斜树:
右斜树:
(2).满⼆叉树
国际标准定义是除了叶结点外每⼀个结点都有左右⼦结点的⼆叉树。
国际定义满⼆叉树:
注意：这⾥的定义与国内某些教材的定义不同，国内的定义是：除了叶结点外每⼀个结点都有左右⼦叶且叶⼦结点都处在最底层的⼆叉树。很显然，按照这个定义，上⾯的图⽰⼆叉树就不是满⼆叉下图是国内定义满⼆叉树:
满⼆叉树的特点有：
1）叶⼦只能出现在最下⼀层。出现在其它层就不可能达成平衡。
2）⾮叶⼦结点的度⼀定是2。
3）在同样深度的⼆叉树中，满⼆叉树的结点个数最多，叶⼦数最多。
(3).完全⼆叉树
完全⼆叉树：对⼀颗具有n个结点的⼆叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满⼆叉树中编号为i的结点在⼆叉树中位置完全相同，则这棵⼆叉树称为完全⼆叉树。
特点：
1）叶⼦结点只能出现在最下层和次下层。
2）最下层的叶⼦结点集中在树的左部。
3）倒数第⼆层若存在叶⼦结点，⼀定在右部连续位置。
4）如果结点度为1，则该结点只有左孩⼦，即没有右⼦树。
5）同样结点数⽬的⼆叉树，完全⼆叉树深度最⼩。
注：满⼆叉树⼀定是完全⼆叉树，但反过来不⼀定成⽴。
(4).平衡⼆叉树
是⼀棵空树或它的任意节点的左右两个⼦树的⾼度差的绝对值不超过1，这就是它的定义，并没有说关于排序的问题，所以平衡⼆叉树不⼀定是⼆叉pai xu sh
将⼆叉树节点的左⼦树的深度减去它的右⼦树的深度称为平衡因⼦BF，则平衡⼆叉树上所有节点的平衡因⼦只可能是-1、0和1。如果出现其他的平衡因⼦说明他不是⼀颗平衡⼆叉树
(5).⼆叉查树⼜称⼆叉搜索树也叫⼆叉排序树
在⼆叉查树中：
(01) 若任意节点的左⼦树不空，则左⼦树上所有结点的值均⼩于它的根结点的值；
(02) 任意节点的右⼦树不空，则右⼦树上所有结点的值均⼤于它的根结点的值；
(03) 任意节点的左、右⼦树也分别为⼆叉查树。
(04) 没有键值相等的节点（no duplicate nodes）。
平衡⼆叉树和⼆叉排序树没有直接关系，平衡⼆叉树做到了每⼀个节点的左、右⼦树深度尽量相等，⼆叉排序树是⼀颗有排序关系的树，当⼆叉排序树出现极端情况⽐如斜树，它的查速度会⽐较慢趋向于O(n)，如果⼆叉排序树和平衡⼆叉树结合起来保证有排序关系的情况下做到左右⼦树平衡，这样查的速度会较快趋向于O(log2N log以2为底n的对数，因为以⼏为底不影响数量级所以⼤家都写成logN log以10为底N的对数简写)，⼆者结合起来就是平衡⼆叉排序树AVL树。
(6).AVL树
AVL树是根据它的发明者G.M. A delson-V elsky和E.M. L andis命名的。它是最先发明的⾃平衡⼆叉查树，也被称为⾼度平衡树。
上⾯的两张图⽚，左边的是AVL树，它的任何节点的两个⼦树的⾼度差别都<=1；⽽右边的不是AVL树，因为7的两颗⼦树的⾼度相差为
2(以2为根节点的树的⾼度是3，⽽以8为根节点的树的⾼度是1)。
AVL树的查、插⼊和删除在平均和最坏情况下都是O(logn)。
如果在AVL树中插⼊或删除节点后，使得⾼度之差⼤于1。此时，AVL树的平衡状态就被破坏，它就不再是⼀棵⼆叉树；为了让它重新维持在⼀个平衡状态，就需要对其进⾏旋转处理。学AVL树，重点的地⽅也就是它的旋转算法；
在所有的不平衡情况中，都是按照先 寻最⼩不平衡树，然后 寻所属的不平衡类别，再 根据 4 种类
别进⾏固定化程序的操作。
AVL树应⽤:
由于维护这种⾼度平衡所付出的代价⽐从中获得的效率收益还⼤，故⽽实际的应⽤不多，更多的地⽅是⽤追求局部⽽不是⾮常严格整体平衡的红⿊树.当然，如果应⽤场景中对插⼊删除不频繁，只是对查要求较⾼，那么AVL还是较优于红⿊树.
Windows NT内核中⼴泛存在.
AVL树详解:
(7).红⿊树
R-B Tree，全称是Red-Black Tree，⼜称为“红⿊树”，它⼀种特殊的⼆叉查树。红⿊树的每个节点上都有存储位表⽰节点的颜⾊，可以是红(Red)或⿊(Black)。
红⿊树的特性:
（1）每个节点或者是⿊⾊，或者是红⾊。
（2）根节点是⿊⾊。
（3）每个叶⼦节点（NIL）是⿊⾊。 [注意：这⾥叶⼦节点，是指为空(NIL或NULL)的叶⼦节点！]
（4）如果⼀个节点是红⾊的，则它的⼦节点必须是⿊⾊的。 [注意：可以出现⽗节点和⼦节点都是⿊⾊]
（5）从⼀个节点到该节点的⼦孙节点的所有路径上包含相同数⽬的⿊节点。
注意：
(01) 特性(3)中的叶⼦节点，是只为空(NIL或null)的节点。
(02) 特性(5)，确保没有⼀条路径会⽐其他路径长出俩倍。因⽽，红⿊树是相对是接近平衡的⼆叉树。
红⿊树的应⽤:
红⿊树的应⽤⽐较⼴泛，主要是⽤它来存储有序的数据，它的时间复杂度是O(lgn)，效率⾮常之⾼。
⼴泛⽤于C++的STL中,map和set都是⽤红⿊树实现的.
著名的linux进程调度,⽤红⿊树管理进程控制块，进程的虚拟内存区域都存储在⼀颗红⿊树上，每个虚拟
地址区域都对应红⿊树的⼀个节点，左指针指向相邻的地址虚拟存储区域，右指针指向相邻的⾼地址虚拟地址空间.
IO多路复⽤epoll的实现采⽤红⿊树组织管理sockfd，以⽀持快速的增删改查.
ngnix中,⽤红⿊树管理timer，因为红⿊树是有序的，可以很快的得到距离当前最⼩的定时器.
Java集合中的和和hashMap树化为红⿊树，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红⿊树去实现的。
红⿊树详解:
3.⼆叉树的遍历
分为：深度优先遍历和⼴度优先遍历
深度优先遍历分为：
1).先序遍历
递归实现:
public void preOrder(TreeNode<T> k1){
if (k1 != null){
System.out.printf(k1.key + " ");
preOrder(k1.left);
preOrder(k1.right);
}
}
循环实现:
public void PreOrder(TreeNode<T> Node) {
二叉树定义if (Node == null) {
System.out.println("null");
return;
}
Stack<AVLTreeNode<T>> stack = new Stack<>();
while (Node != null || !stack.isEmpty()) {
if (Node != null) {
System.out.print(Node.key+" ");
stack.push(Node);
Node = Node.left;
} else {
Node = stack.pop();
Node = Node.right;
}
}
}
2).中序遍历 ⼆叉排序树的中序遍历就是排序
递归实现:
public void midOrder(TreeNode<T> k1){
if (k1 != null){
mOrder(k1.left);
System.out.printf(k1.key + " ");
mOrder(k1.right);
}
}
循环实现:
和先序遍历本质是⼀样的，都是先从根结点把左边遍历到头并且保存下来为了回溯⽤，注意下⾯的处理：拿到栈顶的元素，并且栈顶元素出栈，打印栈顶元素的数值，然后看栈顶元素有没有右孩⼦，如果有的话就重复上⾯的步骤（这个右孩⼦相当于⼀个新的根节点），如果没有就继续出栈
我们⼀步⼀步分析：
1.先把左边遍历到头并且保存下来回溯⽤，⽆论先、中、后序，⼀定是先左，所以先把左边遍历到头，要保存下来是因为左边的元素既是⽗亲节点的左，⼜是右孩⼦的中，我们遍历右孩⼦的时候需要⽤到这些左边节点
2.遍历到头之后，就直接打印这个最左边的元素，因为中序遍历是左、中、右，这个最左边的元素
最多有⼀个右孩⼦，它既是⽗亲节点的左，⼜是右孩⼦节点的中，所以直接打印
3.栈顶元素出栈，并把当前节点赋值为栈顶元素的右孩⼦：因为栈顶元素已经打印完毕，它的作⽤除了打印，就是到它的右孩⼦，我们是靠栈来回溯节点的，如果打印完了不出栈，回溯的时候就会重复。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。