程序猿和他的树

Binary Tree & Binary Search Tree

二叉树和二叉搜索树（BST）

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
    
    def __str__(self):
        return str(self.val)


# 普通二叉树按照root/left/right的顺序进行进行构建树，不对数值大小进行对比。
class BinaryTree():

    # 插入节点（基于队列先进先出来实现）
    # 参考链接：https://www.jianshu.com/p/7ef4d1fd5478
    def Insert(self, root, item):
        node = TreeNode(item)
        # 正常二叉树的建树过程是 根、左、右，整个过程就像是广度优先遍历，所以先判断能不能填到根。
        if root == None:
            root = node
        else:
            queue = []
            queue.append(root)  # queue中保存上一层的节点
            while True:
                pop_node = queue.pop(0)  # 先进先出
                if pop_node.left == None:  # 再判断能不能填到左边
                    pop_node.left = node
                    return
                elif pop_node.right == None:  # 最后判断能不能填到右边
                    pop_node.right = node
                    return
                else:  # 两边都有子树，继续寻找要插入的位置
                    queue.append(pop_node.left)
                    queue.append(pop_node.right)
        return root


    # 创建二叉树 同样的一些数字，以不同的顺序输入，会影响二叉搜索树的创建。 index为要插入的位置。
    # 参考连接：https://blog.csdn.net/seableble/article/details/103172601 / https://blog.csdn.net/dbqb007/article/details/87649557
    def Create(self, items):
        if len(items) == 0:  return TreeNode(0)
        nodeQueue = []  # nodeQueue保存的是这一层所有非空节点，要留着给下一层创建左右子树的时候用。
        root = TreeNode(items[0])  # 创建一个根节点
        nodeQueue.append(root)  # 将根节点加入队列
        cur = None
        lineNodeNum = 2  # 记录下一层需要填充的节点的数量（注意不一定是2的幂，而是上一行中非空节点的数量乘2），第二层的节点数肯定是1*2。
        startIndex = 1  # 记录当前行中数字在数组中的开始位置，第0个位置在根节点，则第第二行第一个位置肯定是items[1]。
        restLength = len(items) - 1  # 记录数组中除去根节点剩余的元素的数量。
        while restLength > 0:  # 只要还有剩，就要继续添加。  
            i = startIndex
            while i < startIndex + lineNodeNum:  # 一次while循环会处理掉一个layer。
                if i == len(items):  return root  # 说明已经将nums中的数字用完，此时应停止遍历，并可以直接返回root
                cur = nodeQueue.pop(0)  # cur是上一行的根节点。
                if items[i] != None:  # 如果是None，就不做处理，保留左节点为None的情况。
                    cur.left = TreeNode(items[i])
                    nodeQueue.append(cur.left)

                if i + 1 == len(items):  return root  # 同上，做一个边界判定。
                if items[i + 1] != None:  # 同上，如果是None，就不做处理，保留右节点为None的情况。
                    cur.right = TreeNode(items[i + 1])
                    nodeQueue.append(cur.right)
                i += 2
            startIndex += lineNodeNum  # 加上这一层已经处理掉的数字，就是下一层要处理的数字的起点。
            restLength -= lineNodeNum  # 减去这一层已经处理掉的数字，就是剩余还未处理的数字的个数。
            lineNodeNum = len(nodeQueue) * 2  # nodeQueue的长度就是这一层的非空节点的个数，乘以2就是下一层需要填充的节点的数量。
        return root


    # 寻找父节点的函数，该方法用于删除某个节点时，寻找其父节点。  
    def FindParent(self, root, item):
        if root.val == item:  # 如果要找的数就是根节点
            return None  # 那么根节点没有父节点，直接return None
        queue = [root]
        while len(queue):
            pop_node = queue.pop(0)
            if pop_node.left and pop_node.left.val == item:  # 如果当前节点存在左子树且当前节点的左子树的val就是item，那么当前节点就是item的父节点。
                return pop_node
            if pop_node.right and pop_node.right.val == item:  # 如果当前节点存在左子树且当前节点的右子树的val就是item，那么当前节点就是item的父节点。
                return pop_node
            # 如果当前节点不是item的父节点，就将当前节点的非空子节点放到队列中，在下次while循环中继续寻找。  
            if pop_node.left != None:
                queue.append(pop_node.left)  # 由于二叉树是root、left、right的顺序创建的，且使用队列保存节点，所以先添加left，后添加right。保证后面先进先出的时候，left先于right出来。
            if pop_node.right != None:
                queue.append(pop_node.right)

        # 如果到这里也没有找到父节点，说明不存在这个数值的父节点。
        return None


    # 删除
    def Delete(self, root, item):
        '''
        从一颗二叉树中删除一个元素的思路：
        先获取 待删除节点 item 的父节点
        如果父节点不为空，
            判断 item 的左右子树
            如果左子树为空且右子树非空，那么判断 item 是父节点的左孩子还是右孩子。如果是左孩子，将父节点的左指针指向 item 的右子树，反之将父节点的右指针指向 item 的右子树
            如果右子树为空且左子树非空，同样判断 item 是父节点的左孩子还是右孩子，如果是左孩子，将父节点的左指针指向 item 的左子树，反之将父节点的右指针指向 item 的左子树
            如果左右子树均不为空，寻找右子树中的最左叶子节点 x ，将 x 替代要删除的节点。
        删除成功，返回 True
        删除失败, 返回 False
        '''
        if root == None:
            return False
        parent = self.FindParent(root, item)
        if parent:  # 存在父节点
            del_node = parent.left if parent.left.val == item else parent.right

            # del_node左右子树都为空 直接删除就行
            if del_node.left == None and del_node.right == None:  
                del del_node
                if parent.left.val == item:
                    parent.left = None
                else:
                    parent.right = None
                return True

            # del_node只有右节点有值，后面就用del_node的右节点补上去。
            elif del_node.left == None and del_node.right != None:
                if parent.left.val == item:  # 要删除的节点是左节点
                    parent.left = del_node.right  # 用del_node的右节点补上去
                else:  # 要删除的节点是右节点
                    parent.right = del_node.right  # 用del_node的右节点补上去、
                del del_node
                return True

            # del_node只有左节点有值，后面就用del_node的左节点补上去。
            elif del_node.left != None and del_node.right == None:
                if parent.left.val == item:  # 要删除的节点是左节点
                    parent.left = del_node.left  # 用del_node的左节点补上去
                else:  # 要删除的节点是右节点
                    parent.right = del_node.left  # 用del_node的左节点补上去
                del del_node
                return True

            else:  # del_node的左右节点都有值（都不为空）
                tmp_pre = del_node
                # 如果del_node的左右子树均不为空，寻找del_node的右子树中的最左叶子节点 x ，将 x 替代要删除的节点。
                tmp_next = del_node.right
                if tmp_next.left == None:  # 如果del_node的右子树的左子树为空，则del_node的右子树的右子树就是del_node的右子树中最左的叶子节点 x 了，将 x 替代要删除的节点。
                    # 开始替换
                    tmp_pre.right = tmp_next.right
                    tmp_next.left = del_node.left
                    tmp_next.right = del_node.right
                else:  # 如果del_node的右子树的左子树非空，就去这里面找最左边的叶子节点 x，将 x 替代要删除的节点。
                    while tmp_next.left:
                        tmp_pre = tmp_next
                        tmp_next = tmp_next.left  # tmp_next = tmp_next.left
                    # 开始替换
                    tmp_pre.left = tmp_next.right
                    tmp_next.left = del_node.left
                    tmp_next.right = del_node.right
                # x 替换 del_node的位置
                if parent.left.val == item:
                    parent.left = tmp_next  # tmp_next就是找到的x
                else:
                    parent.right = tmp_next  # tmp_next就是找到的x
                del del_node
                return True

        else:  # 不存在父节点，直接返回False。
            return False


    # 递归 前序遍历，根结点 ---> 左子树 ---> 右子树。
    def PreOrder(self, root):
        """
        Pre-Order Traversal of binary tree
        :param root: root node of target binary tree
        :return: TreeNode
        """
        # if not root:  return []  # 不处理None模式的一行代码
        if not root:  return [None]  # 不处理None模式的一行代码
        res = [root.val]
        left_tree = self.PreOrder(root.left)
        right_tree = self.PreOrder(root.right)
        return res + left_tree + right_tree   # 如果是递归调用二叉（搜索）树，前/中/后序遍历只用改这里的顺序就行。


    # 循环/栈 前序遍历，根结点 ---> 左子树 ---> 右子树。
    def PreOrder_circulation(self, root):
        """
        Pre-Order Traversal of binary tree based on circulation
        :param root: root node of target binary tree
        :return: TreeNode
        """
        res = []
        stack = []
        if root:
            stack.append(root)
            while len(stack):
                node = stack.pop()
                # 不处理None模式的5行代码
                # if node == None:
                #     continue
                # res.append(node.val)  # 先保存根节点
                # stack.append(node.right)  # 再入栈右子树 下一次循环的时候先入后出
                # stack.append(node.left)  # 再入栈左子树 下一次循环的时候后入先出（实现了根 -> 左 -> 右）
                # 处理None模式的6行代码
                if node == None:
                    res.append(None)
                else:
                    res.append(node.val)  # 先保存根节点
                    stack.append(node.right)  # 再入栈右子树 下一次循环的时候先入后出
                    stack.append(node.left)  # 再入栈左子树 下一次循环的时候后入先出（实现了根 -> 左 -> 右）
        return res


    # 递归 中序遍历，左子树---> 根结点 ---> 右子树。
    def InOder(self, root):
        """
        In-Order Traversal of binary tree
        :param root: root node of target binary tree
        :return: TreeNode
        """
        # if not root:  return []  # 不处理None模式的一行代码
        if not root:  return [None]  # 不处理None模式的一行代码
        res = [root.val]
        left_tree = self.InOder(root.left)
        right_tree = self.InOder(root.right)
        return left_tree + res + right_tree


    # 循环/栈 中序遍历，左子树---> 根结点 ---> 右子树。
    def InOder_circulation(self, root): 
        """
        In-Order Traversal of binary tree based on circulation
        :param root: root node of target binary tree
        :return: TreeNode
        """
        if root == None:  return [None]
        res = []
        stack = [root]
        node = root
        # while node or len(stack) > 0:  #  之前不考虑node==None的条件
        while len(stack) > 0:  # 现在考虑node==None的条件
            if node == None:
                res.append(None)
            else: 
                while node:  # 把当前节点的所有左侧子结点压入栈
                    node = node.left
                    stack.append(node)  # 由于stack是先进后出的，所以这里先把root放进去，再放入left，弹栈的时候才能实现left、root的效果
                if len(stack):  # 访问节点，处理该节点的右子树
                    node = stack.pop()  # 由于之前把左子树先压入了，所以这里先弹出左子树节点
                    if node == None:
                        res.append(None)
                        node = stack.pop()
                    res.append(node.val)  # 开始弹栈，依次访问left、root。
                    node = node.right  #  然后设置新的node为右子树，下一次while循环就会去处理右子树了。这样一来就实现了左 -> 根 -> 右 的顺序。
                    stack.append(node)
        return res


    # 递归 后序遍历，左子树 ---> 右子树 ---> 根结点
    def PostOder(self, root):
        """
        Post-Order Traversal of binary tree
        :param root: root node of target binary tree
        :return: TreeNode
        """
        # if not root:  return []  # 不处理None模式的一行代码
        if not root:  return [None]  # 不处理None模式的一行代码
        res = [root.val]
        left_tree = self.PostOder(root.left)
        right_tree = self.PostOder(root.right)
        return left_tree + right_tree + res


    # 循环/栈 后序遍历，左子树 ---> 右子树 ---> 根结点
    def PostOder_circulation(self, root):
        """
        Post-Order Traversal of binary tree based on circulation
        :param root: root node of target binary tree
        :return: TreeNode
        """
        res = []
        stack = [root]
        pre_Node = None
        # while node or len(stack) > 0:  #  之前不考虑node==None的条件
        while len(stack) > 0:  # 现在考虑node==None的条件
            node = stack.pop()
            if node == None:
                res.append(None)
            else:
                while node:  # 把当前节点的左侧节点全部入栈
                    stack.append(node)
                    node = node.left
                if len(stack) > 0:
                    temp = stack[-1].right  # 获得栈顶元素但是不删除该元素
                    if temp == None or temp == pre_Node:  # 一个根节点被访问的前提是：无右子树或右子树已被访问过
                        node = stack.pop()
                        res.append(node.val)
                        pre_Node = node
                        node = None
                    else:  # 处理右子树，下次while循环时，又会先入栈该右子树的所有左子树
                        node = temp
        return res


    # 深度优先遍历(基于栈/递归)
    def DepthOrder(self, root):
        """
        Depth-first-Order Traversal of binary tree based on recursion
        :param root: root node of target binary tree
        :return: TreeNode
        """
        def _dfs(root):
            # 不处理None模式的4行代码
            # if root != None:
            #     res.append(root.val)  # 先根节点
            #     _dfs(root.left)  # 再左节点
            #     _dfs(root.right)  # 最后右节点
            # 处理None模式的6行代码
            if root == None:
                res.append(None)
            else:
                res.append(root.val)  # 先根节点
                _dfs(root.left)  # 再左节点
                _dfs(root.right)  # 最后右节点
        res = []
        _dfs(root)
        return res


    # 深度优先遍历(基于栈/循环)
    def DepthOrder_circulation(self, root):
        """
        Depth-first-Order Traversal of binary tree based on circulation
        :param root: root node of target binary tree
        :return: TreeNode
        """
        stack = []
        res = []
        # if root.val == None: return res  # 这一句应该不用吧
        # push root 这里push的不是val而是TreeNode
        stack.append(root)
        # 然后就循环取出root，压入root.right节点（先压入后出来），压入root.right节点（后压入先出来），直到栈为空，结束循环。
        while len(stack):
            t = stack.pop()
            # 不处理None模式的5行代码
            # if t == None:
            #     continue
            # stack.append(t.right)
            # stack.append(t.left)
            # res.append(t.val)
            # 处理None模式的6行代码
            if t == None:
                res.append(None)
            else:
                stack.append(t.right)
                stack.append(t.left)
                res.append(t.val)
        return res


    # 广度优先遍历(基于队列/循环)
    def BreadthOrder(self, root):
        """
        Breadth-first-Order Traversal of binary tree based on circulation
        :param root: root node of target binary tree
        :return: TreeNode
        """
        queue = []
        res = []
        queue = []
        # 入队 queue.append(i)
        # 出队 queue[0] queue[1:] 或者 queue.pop()
        # root inQueue 对象入队
        queue.append(root)
        # 然后就循环出队root，root.left节点入队（先入先出），root.right节点再入队（后入后出），直到队列为空，结束循环。
        while len(queue):
            t = queue.pop(0)
            # 不处理None模式的5行代码
            # if t == None:
            #     continue
            # queue.append(t.left)
            # queue.append(t.right)
            # res.append(t.val)
            # 处理None模式的6行代码
            if t == None:
                res.append(None)  # 空节点也放进去
            else:
                queue.append(t.left)
                queue.append(t.right)
                res.append(t.val)
        return res


def BinaryTree_main():
    # _list = [1, None, 3, 2]
    _list = [3, 1, None, None, 2]
    # _list = [5, 4, 8, 11, None, 13, 4, 7, 2, None, None, None, 1]
    # _list = [6, 2, 8, 1, 5, 3, 4]

    print("*"*50)
    print("输入list：{}".format(_list))

    print("*"*50)
    print("创建二叉树")
    BTree = BinaryTree()
    root = BTree.Create(_list)

    print("*"*50)
    res = BTree.PreOrder(root)  # 前序遍历
    print("前序遍历结果（递归实现）：{}".format(res))
    res = BTree.PreOrder_circulation(root)  # 前序遍历
    print("前序遍历结果（循环实现）：{}".format(res))

    print("*"*50)
    res = BTree.InOder(root)  # 中序遍历
    print("中序遍历结果（递归实现）：{}".format(res))
    # res = BTree.InOder_circulation(root)  # 中序遍历  # 循环方法实现有None的二叉树不的中序遍历太简洁
    # print("中序遍历结果（循环实现）：{}".format(res))

    print("*"*50)
    res = BTree.PostOder(root)  #  后续遍历
    print("后序遍历结果（递归实现）：{}".format(res))
    # res = BTree.PostOder_circulation(root)  # 循环方法实现有None的二叉树不的后序遍历太简洁
    # print("后序遍历结果（循环实现）：{}".format(res))

    print("*"*50)
    print("层次遍历分为：深度优先遍历和广度优先遍历两种。")

    # 层次遍历：深度优先遍历
    print("*"*50)
    res = BTree.DepthOrder(root)
    print("层次遍历：深度优先遍历（递归实现） {}".format(res))
    res = BTree.DepthOrder_circulation(root)
    print("层次遍历：深度优先遍历（循环实现） {}".format(res))

    # 层次遍历：广度优先遍历(循环实现)
    print("*"*50)
    res = BTree.BreadthOrder(root)
    print("层次遍历：广度优先遍历(循环实现) {}".format(res))

    print("*"*50)
    insert_val = 6
    print("插入{}到二叉树".format(insert_val))
    BTree.Insert(root, insert_val)
    res =  BTree.BreadthOrder(root)
    print("完成插入后的二叉树（广度优先遍历）")
    print(res)

    print("*"*50)
    delete_val = 1
    print("删除节点：{}".format(delete_val))
    result = BTree.Delete(root, delete_val)
    print("{}".format("删除成功" if result else "删除失败"))
    res = BTree.BreadthOrder(root)
    print("完成删除后的二叉树（广度优先遍历）")
    print(res)

# 二叉树的特点是
# 一般来说，树的根节点及其子树之间是不存在大小关系的，这种树叫做无序树。
# 反之，如果根节点和左子树、右子树之间存在大小关系，则这种树叫做有序树。
# 二叉搜索树（二叉查找树）是一种有序树，其特点是左孩子比父节点小，右孩子比父节点大，”中序遍历“二叉搜索树的结果是有序的。
class BinarySearchTree:

    # 插入节点
    def Insert(self, root, x):
        """
        Insert TreeNode in binary tree
        :param root: root node of target binary tree
                  x: TreeNode which wait for to be inserted
        :return: TreeNode
        """
        if root == None:
            root = TreeNode(x)  # 每个节点都是TreeNode的结构
        else:
            if x < root.val:  # 小于当前节点的放到左子树中
                root.left = self.Insert(root.left, x)
            else:  # 大于当前节点的放到右子树中
                root.right = self.Insert(root.right, x)
        return root


    # 创建二叉树 同样的一些数字，以不同的顺序输入，会影响二叉搜索树的创建。
    def CreateBT(self, items):
        """
        Create a binary tree based on a list
        :param items: list made of items
        :return: TreeNode
        """
        root = None
        for item in items:
            root = self.Insert(root, item)
        return root


    # 寻找最小节点
    def FindMin(self, root):
        """
        Find minimum element in binary tree
        :param root: root node of target binary tree
        :return: TreeNode
        """
        if root:
            while root.left:
                root = root.left
        return root


    # 删除节点
    def Delete(self, root, x):
        """
        Delete TreeNode in binary tree
        :param root: root node of target binary tree
        :return: TreeNode
        """
        if root:
            if x < root.val:
                root.left = self.Delete(root.left, x)
            elif x > root.val:
                root.right = self.Delete(root.right, x)
            elif root.left and root.right:  # 要删除的节点是根节点（x == root.val） 且 左右子节点都存在
                tmp = self.FindMin(root.right)  # 从右子树中寻找最小的节点作为新的根节点
                min_val = tmp.val  # 设置根节点为右子树中的最小值
                root.right = self.Delete(root.right, min_val)  # 从右子树中删除最小节点。
            else:  # 要删除的节点是根节点（x == root.val） 且 左右子节点不同时存在
                # 如果左子树不存在且要删除的节点就是根节点，直接将右子树作为新的新的二叉树即可，右子树不存在则同理。
                root = root.right if root.left is None else root.left
        return root


    # 递归 前序遍历，根结点 ---> 左子树 ---> 右子树。
    def PreOrder(self, root):
        """
        Pre-Order Traversal of binary tree
        :param root: root node of target binary tree
        :return: TreeNode
        """
        if not root:  return []  # 空节点
        res = [root.val]
        left_tree = self.PreOrder(root.left)
        right_tree = self.PreOrder(root.right)
        return res + left_tree + right_tree   # 如果是递归调用二叉（搜索）树，前/中/后序遍历只用改这里的顺序就行。


    # 循环/栈 前序遍历，根结点 ---> 左子树 ---> 右子树。
    def PreOrder_circulation(self, root):
        """
        Pre-Order Traversal of binary tree based on circulation
        :param root: root node of target binary tree
        :return: TreeNode
        """
        res = []
        stack = []
        if root:
            stack.append(root)
            while len(stack):
                node = stack.pop()
                if node == None:
                    continue
                res.append(node.val)  # 先保存根节点
                stack.append(node.right)  # 再入栈右子树 下一次循环的时候先入后出
                stack.append(node.left)  # 再入栈左子树 下一次循环的时候后入先出（实现了根 -> 左 -> 右）
        return res


    # 递归 中序遍历，左子树---> 根结点 ---> 右子树。
    def InOder(self, root):
        """
        In-Order Traversal of binary tree
        :param root: root node of target binary tree
        :return: TreeNode
        """
        if not root:  return []  # 空节点
        res = [root.val]
        left_tree = self.InOder(root.left)
        right_tree = self.InOder(root.right)
        return left_tree + res + right_tree


    # 循环/栈 中序遍历，左子树---> 根结点 ---> 右子树。
    def InOder_circulation(self, root): 
        """
        In-Order Traversal of binary tree based on circulation
        :param root: root node of target binary tree
        :return: TreeNode
        """
        res = []
        stack = []
        node = root
        while node or len(stack) > 0:
            while node:  # 把当前节点的所有左侧子结点压入栈
                stack.append(node)  # 由于stack是先进后出的，所以这里先把root放进去，再放入left，弹栈的时候才能实现left、root的效果
                node = node.left
            if len(stack):  # 访问节点，处理该节点的右子
                node = stack.pop()  # 由于之前把左子树先压入了，所以这里先弹出左子树节点
                res.append(node.val)  # 开始弹栈，依次访问left、root。
                node = node.right  #  然后设置新的node为右子树，下一次while循环就会去处理右子树了。这样一来就实现了左 -> 根 -> 右 的顺序。
        return res


    # 递归 后序遍历，左子树 ---> 右子树 ---> 根结点
    def PostOder(self, root):
        """
        Post-Order Traversal of binary tree
        :param root: root node of target binary tree
        :return: TreeNode
        """
        if not root:  return []  # 空节点
        res = [root.val]
        left_tree = self.PostOder(root.left)
        right_tree = self.PostOder(root.right)
        return left_tree + right_tree + res


    # 循环/栈 后序遍历，左子树 ---> 右子树 ---> 根结点
    def PostOder_circulation(self, root):
        """
        Post-Order Traversal of binary tree based on circulation
        :param root: root node of target binary tree
        :return: TreeNode
        """
        res = []
        stack = []
        node = root
        pre_Node = None
        while node or len(stack) > 0:
            while node:  # 把当前节点的左侧节点全部入栈
                stack.append(node)
                node = node.left
            if len(stack) > 0:
                temp = stack[-1].right  # 获得栈顶元素但是不删除该元素
                if temp == None or temp == pre_Node:  # 一个根节点被访问的前提是：无右子树或右子树已被访问过
                    node = stack.pop()
                    res.append(node.val)
                    pre_Node = node
                    node = None
                else:  # 处理右子树，下次while循环时，又会先入栈该右子树的所有左子树
                    node = temp
        return res


    # 深度优先遍历(基于栈/递归)
    def DepthOrder(self, root):
        """
        Depth-first-Order Traversal of binary tree based on recursion
        :param root: root node of target binary tree
        :return: TreeNode
        """
        def _dfs(root):
            if root != None:
                res.append(root.val)  # 先根节点
                _dfs(root.left)  # 再左节点
                _dfs(root.right)  # 最后右节点
        res = []
        _dfs(root)
        return res


    # 深度优先遍历(基于栈/循环)
    def DepthOrder_circulation(self, root):
        """
        Depth-first-Order Traversal of binary tree based on circulation
        :param root: root node of target binary tree
        :return: TreeNode
        """
        stack = []
        res = []
        if root.val == None:  return res
        # push root 这里push的不是val而是TreeNode
        stack.append(root)
        # 然后就循环取出root，压入root.right节点（先压入后出来），压入root.right节点（后压入先出来），直到栈为空，结束循环。
        while len(stack):
            t = stack.pop()
            if t == None:
                continue
            stack.append(t.right)
            stack.append(t.left)
            res.append(t.val)
        return res


    # 广度优先遍历(基于队列/循环)
    def BreadthOrder(self, root):
        """
        Breadth-first-Order Traversal of binary tree based on circulation
        :param root: root node of target binary tree
        :return: TreeNode
        """
        queue = []
        res = []
        queue = []
        # 入队 queue.append(i)
        # 出队 queue[0] queue[1:]
        # root inQueue 对象入队
        queue.append(root)
        # 然后就循环出队root，root.left节点入队（先入先出），root.right节点再入队（后入后出），直到队列为空，结束循环。
        while len(queue):
            t = queue.pop(0)
            if t == None:
                continue
            queue.append(t.left)
            queue.append(t.right)
            res.append(t.val)
        return res



def BinarySearchTree_main():
    BSTree = BinarySearchTree()
    root = None
    _list = [6, 2, 8, 1, 5, 3, 4]
    # _list = [2, 1, 3]
    # _list = [1, 2, 3]

    print("*"*50)
    print("输入列表：{}".format(_list))
    root = BSTree.CreateBT(_list)  # 创建二叉搜索树

    print("*"*50)
    print("所谓前序、中序、后序，是指根节点的位置在输出序列的前面、中间、后面，而左节点永远在右节点的前面。")

    print("*"*50)
    res = BSTree.PreOrder(root)  # 前序遍历
    print("前序遍历结果（递归实现）：{}".format(res))
    res = BSTree.PreOrder_circulation(root)  # 前序遍历
    print("前序遍历结果（循环实现）：{}".format(res))

    print("*"*50)
    res = BSTree.InOder(root)  # 中序遍历
    print("中序遍历结果（递归实现）：{}".format(res))
    res = BSTree.InOder_circulation(root)  # 中序遍历
    print("中序遍历结果（循环实现）：{}".format(res))

    print("*"*50)
    res = BSTree.PostOder(root)  #  后续遍历
    print("后序遍历结果（递归实现）：{}".format(res))
    res = BSTree.PostOder_circulation(root)
    print("后序遍历结果（循环实现）：{}".format(res))

    print("*"*50)
    print("层次遍历分为：深度优先遍历和广度优先遍历两种。")

    # 层次遍历：深度优先遍历
    print("*"*50)
    res = BSTree.DepthOrder(root)
    print("层次遍历：深度优先遍历（递归实现） {}".format(res))
    res = BSTree.DepthOrder_circulation(root)
    print("层次遍历：深度优先遍历（循环实现） {}".format(res))

    # 层次遍历：广度优先遍历(循环实现)
    print("*"*50)
    res = BSTree.BreadthOrder(root)
    print("层次遍历：广度优先遍历(循环实现) {}".format(res))

    # 寻找最小节点
    print("*"*50)
    mini_node = BSTree.FindMin(root)
    print("寻找最小节点：{}".format(mini_node.val))

    # 删除节点
    print("*"*50)
    delet_node = 1
    res = BSTree.InOder(root)
    print("删除节点{}前的中序遍历，{}".format(delet_node, res))
    BSTree.Delete(root, delet_node)
    res = BSTree.InOder(root)
    print("删除节点{}后的中序遍历，{}".format(delet_node, res))



if __name__ == "__main__":
    # 测试普通二叉树
    print("测试普通二叉树")
    BinaryTree_main()
    
    # 测试二叉搜索树
    print("-"*50)
    print("测试二叉搜索树")
    BinarySearchTree_main()

Balance Tree and Balance Plus Tree

Balance Tree

B Tree

B Tree 是指 Balance Tree，也就是平衡树。平衡树是一颗查找树，并且所有叶子节点位于同一层。但是，有的定义下认为，如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。。平衡树是改进的二叉查找树。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离（即深度），因此当结点的深度普遍较大时，查询的均摊复杂度会上升。为了实现更高效的查询，产生了平衡树。

在这里，平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。

240px-AVLtreef.svg.png

B-树是一种多路平衡查找树，下面来具体介绍一下B-树（Balance Tree），不叫B减树，就读作B树，一个m阶的B树具有如下几个特征：

根结点至少有两个子女。
每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m
每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
所有的叶子结点都位于同一层。
每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

参考连接

https://mp.weixin.qq.com/s/raIWLUM1kdbYvz0lTWPTvw

Blance Plus Tree

B+ Tree

B+树是B树的一种变形，它把数据都存储在叶子节点，内部的非叶子节点只存索引和孩子指针，以叶子节点的最小值作为索引（3，5），简化了内部节点。B+树的遍历高效，将所有叶子节点串联成链表即可从头到尾遍历。

B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入，这与二叉树恰好相反。下图是把键1-7连接到值 d1-d7 的B+树。链表指针（红色）用于快速顺序遍历叶子节点，空指针（黄色）为null，有效指针（白色）用于指向子节点或者数据（\(d_1\), \(d_2\), ..., \(d_7\)）。

B+ Tree 是基于 B Tree 和叶子节点顺序访问指针进行实现，它具有 B Tree 的平衡性，并且通过顺序访问指针来提高区间查询的性能。（重点内容）

在 B+ Tree 中，一个节点中的 \(key\)（\(key\) 就是索引）从左到右非递减排列，如果某个指针的左右相邻的 \(key\) 分别是 \(key_i\) (3) 和 \(key_{i+1}\) (5)，且不为 null，则该指针指向节点的所有 \(key\) (3、4) 大于等于 \(key_i\) (3) 且小于等于 \(key_{i+1}\) (5)。

Differences of B Tree and B+ Tree

所有data都存储在叶子节点，非叶子节点不存储真正的data。
为所有叶子节点增加了一个链指针，将所有叶子节点串联成链表即可从头到尾遍历。

Red Black Tree

红黑树（Red Black Tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。红黑树，Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST)，树上的每个节点都遵循下面的规则:

每个节点都有红色或黑色
树的根始终是黑色的 (黑土地孕育黑树根)
没有两个相邻的红色节点（红色节点不能有红色父节点或红色子节点，并没有说不能出现连续的黑色节点）
从节点（包括根）到其任何后代NULL节点(叶子结点下方挂的两个空节点，并且认为他们是黑色的)的每条路径都具有相同数量的黑色节点。

参考连接

红黑树，超强动静图详解，简单易懂

van Emde Boas Tree

泛峨眉大悲寺树

van Emde Boas

Morris Traverse

https://zhuanlan.zhihu.com/p/101321696

算法与数据结构

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

数据结构：栈和队列上一篇

算法：位运算下一篇

数据结构：树