二叉树的一些操作

1. 二叉搜索树（BSTree）的概念

二叉搜索树又被称为二叉排序树，那么它本身也是一棵二叉树，那么满足以下性质的二叉树就是二叉搜索树，如图：

若左子树不为空，则左子树上所有节点的值都小于根节点的值；
若它的右子树不为空，则它的右子树上所有节点的值都大于根节点的值；
它的左右子树也要分别是二叉搜索树。

2. 二叉搜索树的插入

如果插入值已经存在，则不插，return False
如果not root，则返回TreeNode(val)
根据与root.val的比较，在左右子树中进行递归操作

代码中保证插入的值不存在，也是leetcode第701题中所gurantee的

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def insertIntoBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        if not root:
            return TreeNode(val)
        if val < root.val:
            root.left = self.insertIntoBST(root.left, val)
        if val > root.val:
            root.right = self.insertIntoBST(root.right, val)
        return root

3. 二叉搜索树的搜索

搜索节点

public TreeNode search(int key) {
    TreeNode pNode = root;
    while (pNode != null) {
        if (key == pNode.key) {
            return pNode;
        } else if (key > pNode.key) {
            pNode = pNode.rchild;
        } else if (key < pNode.key) {
            pNode = pNode.lchild;
        }
    }
    return null;// 如果没有搜索到结果那么就只能返回空值了
}

获取最小节点

public TreeNode minElemNode(TreeNode node) throws Exception {
    if (node == null) {
        throw new Exception("此树为空树！");
    }
    TreeNode pNode = node;
    while (pNode.lchild != null) {
        pNode = pNode.lchild;
    }
    return pNode;
}

获取最大节点

public TreeNode maxElemNode(TreeNode node) throws Exception {
    if (node == null) {
        throw new Exception("此树为空树！");
    }
    TreeNode pNode = node;
    while (pNode.rchild != null) {
        pNode = pNode.rchild;
    }
    return pNode;
}

获取给定节点在中序遍历下的后续第一个节点（即找到该节点的右子树中的最左孩子）

public TreeNode successor(TreeNode node) throws Exception {
    if (node == null) {
        throw new Exception("此树为空树！");
    }
    // 分两种情况考虑，此节点是否有右子树
    // 当这个节点有右子树的情况下，那么右子树的最小关键字节点就是这个节点的后续节点
    if (node.rchild != null) {
        return minElemNode(node.rchild);
    }

    // 当这个节点没有右子树的情况下,即 node.rchild == null
    // 如果这个节点是它父节点的左子树的话，那么就说明这个父节点就是后续节点了
    TreeNode parentNode = node.parent;
    while (parentNode != null && parentNode.rchild == node) {
        node = parentNode;
        parentNode = parentNode.parent;
    }
    return parentNode;
}

获取给定节点在中序遍历下的前趋结点

public TreeNode precessor(TreeNode node) throws Exception {
    // 查找前趋节点也是分两种情况考虑
    // 如果这个节点存在左子树，那么这个左子树的最大关键字就是这个节点的前趋节点
    if (node.lchild != null) {
        return maxElemNode(node.lchild);
    }
    // 如果这个节点不存在左子树，那么这个节点的父节点
    TreeNode parentNode = node.parent;
    while (parentNode != null && parentNode.lchild == node) {
        node = parentNode;
        parentNode = parentNode.lchild;
    }
    return parentNode;
}

4. 二叉搜索树的删除

要删除的节点不存在，return False
要删除的节点没有子节点，直接删
要删除的节点只有一个子节点（即只有一个左子节点或者一个右子节点），让被删除节点的父亲节点指向其子节点即可
要删除的节点target有两个子节点（即左右均存在），则首先找到该节点的右子树中的最左孩子（也就是右子树中序遍历的第一个节点，分两种情况），然后将两者互换，再删除target即可

    // 从二叉树当中删除指定的节点
    public void delete(int key) throws Exception {
        TreeNode pNode = search(key);
        if (pNode == null) {
            throw new Exception("此树中不存在要删除的这个节点！");
        }

        delete(pNode);
    }

    private void delete(TreeNode pNode) throws Exception {
        // 第一种情况:删除没有子节点的节点
        if (pNode.lchild == null && pNode.rchild == null) {
            if (pNode == root) {// 如果是根节点，那么就删除整棵树
                root = null;
            } else if (pNode == pNode.parent.lchild) {
                // 如果这个节点是父节点的左节点，则将父节点的左节点设为空
                pNode.parent.lchild = null;
            } else if (pNode == pNode.parent.rchild) {
                // 如果这个节点是父节点的右节点，则将父节点的右节点设为空
                pNode.parent.rchild = null;
            }
        }

        // 第二种情况： （删除有一个子节点的节点）
        // 如果要删除的节点只有右节点
        if (pNode.lchild == null && pNode.rchild != null) {
            if (pNode == root) {
                root = pNode.rchild;
            } else if (pNode == pNode.parent.lchild) {
                pNode.parent.lchild = pNode.rchild;
                pNode.rchild.parent = pNode.parent;
            } else if (pNode == pNode.parent.rchild) {
                pNode.parent.rchild = pNode.rchild;
                pNode.rchild.parent = pNode.parent;
            }
        }
        // 如果要删除的节点只有左节点
        if (pNode.lchild != null && pNode.rchild == null) {
            if (pNode == root) {
                root = pNode.lchild;
            } else if (pNode == pNode.parent.lchild) {
                pNode.parent.lchild = pNode.lchild;
                pNode.lchild.parent = pNode.parent;
            } else if (pNode == pNode.parent.rchild) {
                pNode.parent.rchild = pNode.lchild;
                pNode.lchild.parent = pNode.parent;
            }
        }

        // 第三种情况： （删除有两个子节点的节点，即左右子节点都非空）

        // 方法是用要删除的节点的后续节点代替要删除的节点，并且删除后续节点（删除后续节点的时候需要递归操作）
        // 解析：这里要用到的最多也就会发生两次，即后续节点不会再继续递归的删除下一个后续节点了，
        // 因为，要删除的节点的后续节点肯定是:要删除的那个节点的右子树的最小关键字，而这个最小关键字肯定不会有左节点;
        // 所以，在删除后续节点的时候肯定不会用到（两个节点都非空的判断 ），如有有子节点，肯定就是有一个右节点。
        if (pNode.lchild != null && pNode.rchild != null) {
            // 先找出后续节点
            TreeNode successorNode = successor(pNode);
            if (pNode == root) {
                root.key = successorNode.key;
            } else {
                pNode.key = successorNode.key;// 赋值，将后续节点的值赋给要删除的那个节点
            }
            delete(successorNode);// 递归的删除后续节点
        }
    }

5. 二叉搜索树的遍历

前序遍历：leetcode第144题

中序遍历：leetcode第94题

后序遍历：leetcode第145题

层次遍历：leetcode第102题

References

数据结构与算法之二叉搜索树插入、查询与删除