二叉树
1.二叉树特点
由二叉树定义以及图示分析得出二叉树有以下特点：
1）每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
2）左子树和右子树是有顺序的，次序不能任意颠倒。
3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。
4）无子树的节点也称为叶子
2.二叉树性质
1）在二叉树的第i层上最多有2i-1 个节点 。（i>=1）
2）二叉树中如果深度为k,那么最多有2k-1个节点。(k>=1）
3）n0=n2+1 n0表示度数为0的节点数，n2表示度数为2的节点数。
4）在完全二叉树中，具有n个节点的完全二叉树的深度为[log2n]+1，其中[log2n]是向下取整。
5）若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点有如
(1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点;
(2) 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；
(3) 若 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。
3.斜树
往一边倾斜的数，就叫斜树，例如：所有的节点都是只有左子女节点的树就叫左斜树；反过来只有右子女节点的树就叫右斜树。
4.满二叉树
满二叉树：在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
特点：
1）叶子只能出现在最下一层。出现在其它层就不可能达成平衡。
2）非叶子结点的度一定是2。
3）在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。
5.完全二叉树
完全二叉树：对一颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。
特点：
1）叶子结点只能出现在最下层和次下层。
2）最下层的叶子结点集中在树的左部。
3）倒数第二层若存在叶子结点，一定在右部连续位置。
4）如果结点度为1，则该结点只有左孩子，即没有右子树。
5）同样结点数目的二叉树，完全二叉树深度最小。
满二叉树一定是完全二叉树，但反过来不一定成立。
6.二叉树遍历
遍历方式：
1）前序遍历
2）中序遍历
3）后序遍历
4）层序遍历
图1.png
前序遍历：进入当前节点，马上执行当前节点的主要逻辑
进入A，执行A的逻辑，然后到B，执行B的逻辑，到D，执行D的逻辑，到H执行H的逻辑，因为H没有子节点，所以返回到D，然后进入D的右节点I，执行I的逻辑，而I也没有子节点，返回到D，因为D的逻辑和左右节点也执行完了，所以这时候回到B，执行B节点的右节点E，执行E的逻辑，然后进入J，执行J的逻辑，J没有节点返回到节点E，然后进入K节点，执行K的逻辑，至此A节点的左子树的逻辑已经跑完，后面到A节点的右子树，规律也一样。
最终输出的结果是：
A -> B -> D -> H -> I -> E -> J -> K -> C -> F -> L -> G
// 前序遍历: 根->左->右
fun preTraverse(root: TreeNode?) {
if (root != null) {
println("preTraverse:${root.value}")
preTraverse(root.left,stringBuffer)
preTraverse(root.right,stringBuffer)
}
}
中序遍历：第一次进入当前节点不执行当前节点的主要逻辑，当第二次进入这个节点的时候才执行当前节点主要逻辑。
进A节点，先不执行A节点的逻辑，直接进入B节点，先不执行B节点的逻辑，直接进入D节点，先不执行D节点的逻辑，直接进入H节点，由于H节点没有子节点，则执行H节点的逻辑，执行完H节点的逻辑后返回D节点，开始执行D节点的逻辑，执行完D节点的逻辑后进入I节点，由于I节点没有子节点，则直接执行I节点的逻辑，执行完I节点后返回D节点，此时的D节点已经执行完，所以直接返回到B节点，开始执行B节点的逻辑，执行完B节点的逻辑后进入E节点，先不执行E节点的逻辑，直接进入J节点，由于J节点没有子节点，直接执行J节点的逻辑，执行完J节点的逻辑后返回E节点，开始执行E节点的逻辑，执行完E节点的逻辑后进入K节点，由于K节点没有子节点，直接执行K节点的逻辑，执行完K节点逻辑后返回E节点，此时的E节点已完成所有逻辑，所以直接返回B节点，而B节点也已经完成所有逻辑，所以也直接返回到A节点，开始执行A节点的逻辑，至此A节点的左子树已经完成了，而后面到A节点的右子树，规律也一样。
最终输出的结果是：
H -> D -> I -> B -> J -> E -> K -> A -> L -> F -> C -> G
// 中序遍历: 左->根->右
fun inTraverse(root: TreeNode?) {
if (root != null) {
inTraverse(root.left,stringBuffer)
println("preTraverse:${root.value}")
inTraverse(root.right,stringBuffer)
}
}
后续遍历：第一次进入当前节点的时候不执行当前节点的主要逻辑，当第二次进入这个节点的时候还是不执行主要逻辑，只有第三次进入当前节点的时候才执行当前的逻辑。
进A节点，先不执行A节点的逻辑，直接进入B节点，先不执行B节点的逻辑，直接进入D节点，先不执行D节点的逻辑，直接进入H节点，由于H节点没有子节点，则执行H节点的逻辑，执行完H节点的逻辑后返回D节点，还是不执行D节点的逻辑，直接进入I节点，由于I节点没有子节点，则执行I节点的逻辑，执行完I节点后再次回到D节点，此时开始执行D节点的逻辑，执行完D节点逻辑后返回到B节点，先不执行B节点的逻辑直接进入E节点，先不执行E节点的逻辑，直接进入J节点，由于J节点没有子节点，则执行J节点的逻辑，执行完J节点的逻辑后返回E节点，还是不执行E节点的逻辑，直接进入K节点，由于K节点没有子节点，则执行K节点的逻辑，执行完K节点后再次回到E节点，此时开始执行E节点的逻辑，执行完E节点的逻辑后返回到B节点，此时开始执行B节点的逻辑，执行完B节点的逻辑后，返回到A节点，此时A节点的左子树已经执行完毕，但是与前序、后序不同的是此时还没有执行A节点的逻辑，而右子树的执行规律和左子树一样。
最终输出的结果是：
H -> I -> D -> J -> K -> E -> B -> L -> F -> G -> C -> A
// 后序遍历: 左->右->根
fun postTraverse(root: TreeNode?) {
if (root != null) {
postTraverse(root.left,stringBuffer)
postTraverse(root.right,stringBuffer)
println("preTraverse:${root.value}")
}
}
层序遍历：顾名思义就是从上到下，从左往右，一层一层的执行。
先执行第一层A节点的逻辑；然后到第二层B节点的逻辑，C节点的逻辑；再到第三层D节点的逻辑，E节点的逻辑，F节点的逻辑，G节点的逻辑；最后到第四层H节点的逻辑，I节点的逻辑，J节点的逻辑，K节点的逻辑，L节点的逻辑。
最终输出的结果是：
A -> B -> C -> D -> E -> F -> G -> H -> I -> J -> K -> L
// 层次遍历(BFS)
fun levelOrder(root: TreeNode?): MutableList<MutableList<Int>> {
val result = mutableListOf<MutableList<Int>>()
if (root == null) {
return result
}
val queue = LinkedList<TreeNode>()
queue.offer(root)
while (!queue.isEmpty()) {
val level = mutableListOf<Int>()
val size = queue.size
for (i in 0 until size) {
val head = queue.poll()
level.add(head.value)
if (head.left != null) {
queue.offer(head.left)
}
if (head.right != null) {
queue.offer(head.right)
}
}
result.add(level)
}
return result
}
7.线索二叉树
线索二叉树：二叉树末端的节点由于没有子节点，那么实际是浪费了空间，为了利用好这些空间，利用某种遍历将末端节点的子节进行线索化，所谓的线索化就是将空的左子节点指向它的前驱节点，空的右子节点指向后继节点。所谓的前驱节点就是当前节点的前一个输出节点，而后继节点就是指当前节点的后一个输出节点。
例如：图2的中序遍历的E节点，它的前驱节点就是B节点，而后继节点就是A节点。
图2.png
二叉树线索化带来的好处是，不管给到哪个节点都能快速找到该节点前驱和后继节点。
/**---------------------中序遍历线索化------------------------------*/
private var preTreeNode: TreeNode? = null
fun inTraverseThreading(current: TreeNode?) {
if (current != null) {
inTraverseThreading(current.left)
println("current:${current.value},preTreeNode:${preTreeNode?.value}")
if (current.left == null) {
current.leftTag = TreeNodeTag.Thread
current.left = preTreeNode
}
if (preTreeNode?.right == null) {
preTreeNode?.rightTag = TreeNodeTag.Thread
preTreeNode?.right = current
}
preTreeNode = current
inTraverseThreading(current.right)
}
}
8.二叉排序树
二叉排序树的特点：
1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
3）左、右子树也分别为二叉排序树；
二叉排序树的创建：
取一个数据和根节点对比，如果比根节点小放在左边，否则放在右边，如果根节点已经有子节点，则和子节点再做对比。
例如现在有数据：55,10,15,88,60,50,100,80,52,46,35,20,45,87,76,58
1）取第一个数据55作为根节点；
2）取数据10和根节点55做对比，因为比根节点55小，所以放在根节点55的左边，此时的根节点55的左子节点为空，所以直接插在根节点55的左子节点位置；
3）取第三个数据15和根节点55对比，因为比根节点55小，所以放在根节点55的左边，此时的根节点55的左子节点不为空，所以还需要和左子节点10作对比，因为比左子节点10大，所以放在左子节点10的右子节点上；
4)）以此内推，将数据插入，最终输出结果如图3。
图3.png
data class TreeNode(
val value: Int,
var left: TreeNode? = null,
var right: TreeNode? = null
)
/**
* 查找
* @param target 目标
* @param current 当前的节点
*/
fun searchBST(target: TreeNode, current: TreeNode): TreeNode {
if (target.value == current.value) {
return current
}
return if (target.value > current.value) {
if (current.right != null) {
searchBST(target, current.right!!)
} else {
current
}
} else {
if (current.left != null) {
searchBST(target, current.left!!)
} else {
current
}
}
}
