数据结构各种树总结

1. 二叉树（Binary Tree）

（1）定义

每个节点最多只有两个子节点，没有子节点的节点称之为叶子节点，第一个节点为根节点。

（2）二叉树的性质

① 我们将节点用数组的形式进行保存，比如是tree, tree[0]就代表根节点。假设父节点是tree[n]，左节点为tree[n*2+1], 右节点为tree[n*2+2]。

② 每一层的节点都是满的树我们称为满二叉树(Full Binary Tree)，比如下面图a。除了最后一层不满之外，其它层都是满的的树称为完全二叉树（Complete Binary Tree），如图b。

③ 在一棵满二叉树中，我们假设根节点是第0层，则每一层的节点个数为2^n，第n层之前所有节点个数为(2^n) - 1。

（3）二叉树的各种基本操作

二叉树的创建，先序遍历，中序遍历，后序遍历

from typing import List

class TreeNode:
    def __init__(self, val: int):
        self.val = val
        self.left = None
        self.right = None

class Tree:
    def __init__(self):
        self.root = None
    # 给你一个数组，去创建一颗二叉树
    def create(self, nums: List[int]) -> None:
        tree_nodes = []
        for num in nums:
            if num:
                temp_node = TreeNode(num)
                tree_nodes.append(temp_node)
            else:
                tree_nodes.append(None)
        for i, node in enumerate(tree_nodes):
            if node:
                if i * 2 + 1 < len(nums):
                    node.left = tree_nodes[i * 2 + 1]
                if i * 2 + 2 < len(nums):
                    node.right = tree_nodes[i * 2 + 2]
        self.root = tree_nodes[0]
        return self.root

    # 树的先序遍历，也就是先访问父节点，再访问左节点，再访问右节点
    def pre_order(self, node: TreeNode) -> None:
        if not node:
            return
        print(node.val)
        self.pre_order(node.left)
        self.pre_order(node.right)

    # 树的中序遍历，先访问左节点，再访问父节点，再访问右节点
    def in_order(self, node: TreeNode) -> None:
        if not node:
            return
        self.in_order(node.left)
        print(node.val)
        self.in_order(node.right)

    # 树的后序遍历，先访问右节点，再访问父节点，再访问左节点
    def post_order(self, node: TreeNode) -> None:
        if not node:
            return
        self.post_order(node.right)
        print(node.val)
        self.post_order(node.left)


if __name__ == '__main__':
    test = Tree()
    root = test.create([5,1,4,None,None,3,6])
    test.pre_order(root)
    test.in_order(root)
    test.post_order(root)

2. 二叉搜索树 （Binary Search Tree）

（1）定义

一颗二叉树满足如下性质，则就是一颗二叉搜索树

① 若左子树不为空，则所有的左子树的值都小于父节点的值

② 若右子树不为空，则所有的右子树的值都大于父节点的值。

③ 左右子树也都是二叉搜索树

④ 没有相同值的节点

（2）性质

① 对二叉搜索树进行中序遍历（先遍历左节点，再遍历父节点，再遍历右节点）则得到有序数列。

（3）二叉搜索树的各种操作

① 插入操作

若当前的树为空，则插入的元素为根节点。

若插入的节点小于根节点，则插入到左子树（递归）。

如果插入的节点大于等于根节点，则插入到右子树（递归）。

所有新插入的节点成为叶子节点。

# 插入一个新的节点
    def insert(self, root, val):
        if not root:
            self.root = TreeNode(val)
            return
        if val == root.val:
            return
        if val < root.val:
            if not root.left:
                root.left = TreeNode(val)
            else:
                self.insert(root.left, val)
        else:
            if not root.right:
                root.right = TreeNode(val)
            else:
                self.insert(root.right, val)

② 查询操作

# 查找一个节点是否在这课树中，如果不在则返回False，在的话则返回True
    def search(self, root, val):
        if not root:
            return False
        if val < root.val:
            return self.search(root.left, val)
        elif val > root.val:
            return self.search(root.right, val)
        else:
            return True

③ 创建二叉搜索树

    def create(self, nums):
        for num in nums:
            new_node = TreeNode(num)
            self.insert(self.root, new_node)
        return self.root

④ 中序遍历，可以得到从小到大的list

    def in_order(self, node, rlt):
        if not node:
            return rlt
        self.in_order(node.left, rlt)
        rlt.append(node.val)
        self.in_order(node.right, rlt)

⑤ 删除操作

如果要删除的节点是叶子节点，就直接删除，修改叶子节点的left或者right为None

如果要删除的节点a只有一个子节点b，a节点的父节点是c，那么将c的对应子节点指向b，同时删掉a节点

如果要删除的节点既有左节点又有右节点，那么选择该节点的右子树中最小的那个点的值赋值到该节点，并且删除最小值的那个节点。

如果不理解的话，可以参考这篇博客，里面有详细的图解。

    def delete(self, parent, curr, val):
        # 如果是一颗空树
        if not curr:
            return None
        if val < curr.val:
            self.delete(curr, curr.left, val)
        elif val > curr.val:
            self.delete(curr, curr.right, val)
        else:
            if not curr.left:
                if parent.left == curr:
                    parent.left = curr.right
                else:
                    parent.right = curr.right
                del curr
            elif not curr.right:
                if parent.left == curr:
                    parent.left = curr.left
                else:
                    parent.right = curr.left
                del curr
            else:
                pre_node = curr.right
                if not pre_node.left:
                    curr.val = pre_node.val
                    curr.right = pre_node.right
                    del pre_node
                else:
                    temp_node = curr.right
                    while temp_node.left:
                        pre_node = temp_node
                        temp_node = temp_node.left
                    curr.val = temp_node.val
                    pre_node.left = None
                    del temp_node

 

最后的整体代码：

class TreeNode:
    def __init__(self, val: int):
        self.val = val
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    # 查找一个节点是否在这课树中，如果不在则返回False，在的话则返回True
    def search(self, root, val):
        if not root:
            return False
        if val < root.val:
            return self.search(root.left, val)
        elif val > root.val:
            return self.search(root.right, val)
        else:
            return True

    # 插入一个新的节点
    def insert(self, root, val):
        if not root:
            self.root = TreeNode(val)
            return
        if val == root.val:
            return
        if val < root.val:
            if not root.left:
                root.left = TreeNode(val)
            else:
                self.insert(root.left, val)
        else:
            if not root.right:
                root.right = TreeNode(val)
            else:
                self.insert(root.right, val)

    def create(self, nums):
        for num in nums:
            self.insert(self.root, num)
        return self.root

    def in_order(self, node, rlt):
        if not node:
            return rlt
        self.in_order(node.left, rlt)
        rlt.append(node.val)
        self.in_order(node.right, rlt)

    def delete(self, parent, curr, val):
        # 如果是一颗空树
        if not curr:
            return None
        if val < curr.val:
            self.delete(curr, curr.left, val)
        elif val > curr.val:
            self.delete(curr, curr.right, val)
        else:
            if not curr.left:
                if parent.left == curr:
                    parent.left = curr.right
                else:
                    parent.right = curr.right
                del curr
            elif not curr.right:
                if parent.left == curr:
                    parent.left = curr.left
                else:
                    parent.right = curr.left
                del curr
            else:
                pre_node = curr.right
                if not pre_node.left:
                    curr.val = pre_node.val
                    curr.right = pre_node.right
                    del pre_node
                else:
                    temp_node = curr.right
                    while temp_node.left:
                        pre_node = temp_node
                        temp_node = temp_node.left
                    curr.val = temp_node.val
                    pre_node.left = None
                    del temp_node


if __name__ == '__main__':
    test = BST()
    root = test.create([5,3,2,1,4])
    test.delete(root, root, 3)
    rlt = []
    test.in_order(root, rlt)
    print(rlt)