二叉树

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
        }
    }
}

参考链接