03-树结构

树结构依靠节点、叶子节点、子树将自身的数据扩展为像一棵倒过来的树

树结构

1. 什么是树结构

树结构依托路径、节点、叶子节点将自身的数据结构展现得就行一棵倒过来的树一样，因此称之为树结构。

• 根节点(root): 树的最上层的节点，任何非空的树都有一个节点
• 路径(path): 从起始节点到终止节点经历过的边
• 父亲(parent)：除了根节点，每个节点的上一层边连接的节点就是它的父亲(节点)
• 孩子(children): 每个节点由边指向的下一层节点
• 兄弟(siblings): 同一个父亲并且处在同一层的节点
• 子树(subtree): 每个节点包含它所有的后代组成的子树
• 叶子节点(leaf node): 没有孩子的节点成为叶子节点

2. 二叉树

二叉树属于树的一种分类，是简单且较为常用的一种树结构，它的每个节点最多包含两个孩子。

2.1 满二叉树

每个非叶子节点都有两个孩子称之为满二叉树

2.2 完美二叉树

从根节点到叶子节点，每一层都是满二叉树结构

2.3 完全二叉树

除了叶子节点一层外，剩余的层是完美二叉树

2.4 二叉查找树

应用二叉树的结构，对数据按照左边大（小）右边小（大）的结构进行分布。

2.5 一些概念

节点深度(depth): 节点对应的 level 数字
树的高度(height): 二叉树的高度就是 level 数 + 1，因为 level 从 0开始计算的
树的宽度(width): 二叉树的宽度指的是包含最多节点的层级的节点数
树的 size：二叉树的节点总个数。

2.6 二叉树的表示

可以直接利用数组依照层级关系从上（根节点）到下（叶子节点），每一层按照从左到右的方式进行数组展示。

二叉树的数组表示

3. 代码

3.1 树结构

树结构的实现方式和双链式结构的实现方式类似，在节点上添加左右指向。

node_list = [
    {'data': 'A', 'left': 'B', 'right': 'C', 'is_root': True},
    {'data': 'B', 'left': 'D', 'right': 'E', 'is_root': False},
    {'data': 'D', 'left': None, 'right': None, 'is_root': False},
    {'data': 'E', 'left': 'H', 'right': None, 'is_root': False},
    {'data': 'H', 'left': None, 'right': None, 'is_root': False},
    {'data': 'C', 'left': 'F', 'right': 'G', 'is_root': False},
    {'data': 'F', 'left': None, 'right': None, 'is_root': False},
    {'data': 'G', 'left': 'I', 'right': 'J', 'is_root': False},
    {'data': 'I', 'left': None, 'right': None, 'is_root': False},
    {'data': 'J', 'left': None, 'right': None, 'is_root': False},
]


class Node:
    def __init__(self, data, left=None, right=None):
        self.data, self.right, self.left = data, right, left


class Tree:
    def __init__(self, root=None):
        self.root = root
    
    # 数据解析
    def init_data(self, datas):
        node_dict = {}
        for data in datas:
            node = Node(data['data'], data['left'], data['right'])
            node_dict[data['data']] = node
        for data in datas:
            node = node_dict[data['data']]
            if node.left:
                node.left = node_dict[node.left]
            if node.right:
                node.right = node_dict[node.right]
            if data['is_root']:
                self.root = node

3.2 二叉查找树

node_list = [
    {'data': 60, 'left': 12, 'right': 90, 'is_root': True},
    {'data': 12, 'left': 4, 'right': 41, 'is_root': False},
    {'data': 4, 'left': 1, 'right': None, 'is_root': False},
    {'data': 1, 'left': None, 'right': None, 'is_root': False},
    {'data': 41, 'left': 29, 'right': None, 'is_root': False},
    {'data': 29, 'left': 23, 'right': 37, 'is_root': False},
    {'data': 23, 'left': None, 'right': None, 'is_root': False},
    {'data': 37, 'left': None, 'right': None, 'is_root': False},
    {'data': 90, 'left': 71, 'right': 100, 'is_root': False},
    {'data': 71, 'left': None, 'right': 84, 'is_root': False},
    {'data': 100, 'left': None, 'right': None, 'is_root': False},
    {'data': 84, 'left': None, 'right': None, 'is_root': False},
]


class Node:
    def __init__(self, data, left=None, right=None):
        self.data, self.right, self.left = data, right, left

    def __str__(self):
        return '数据是：{}'.format(self.data)


class Tree:
    def __init__(self, root=None):
        self.root = root

    def init_data(self, datas):
        node_dict = {}
        for data in datas:
            node = Node(data['data'], data['left'], data['right'])
            node_dict[data['data']] = node
        for data in datas:
            node = node_dict[data['data']]
            if node.left:
                node.left = node_dict[node.left]
            if node.right:
                node.right = node_dict[node.right]
            if data['is_root']:
                self.root = node

    # 通过递归查找某个值
    def search(self, subtree, value):
        if subtree is None:
            return None
        elif subtree.data > value:
            return self.search(subtree.left, value)
        elif subtree.data < value:
            return self.search(subtree.right, value)
        else:
            return subtree

    # 获取二叉查找树的最小值
    def get_min(self, subtree):
        if subtree is None:
            return None
        elif subtree.left is None:
            return subtree
        else:
            return self.get_min(subtree.left)

    def insert_data(self, subtree, value):
        if subtree is None:
            subtree = Node(value)
        elif subtree.data > value:
            subtree.left = self.insert_data(subtree.left, value)
        else:
            subtree.right = self.insert_data(subtree.right, value)
        return subtree

    def add(self, value):
        # 查找数据  是否已存在
        node = self.search(self.root, value)
        if node:
            return False
        else:
            self.root = self.insert_data(self.root, value)
            return True
    
    # 利用递归删除节点，并清理关系
    def remove_node(self, subtree, value):
        if subtree is None:
            return None
        elif subtree.data > value:
            subtree.left = self.remove_node(subtree.left, value)
            return subtree
        elif subtree.data < value:
            subtree.right = self.remove_node(subtree.right, value)
        else:
            # 找到数据节点 ： 1，2，3
            if subtree.left is None and subtree.right is None:
                return None
            elif subtree.left is None or subtree.right is None:
                if subtree.left is not None:
                    return subtree.left
                else:
                    return subtree.right
            else:
                node = self.get_min(subtree.right)
                subtree.data = node.data
                subtree.right = self.remove_node(subtree.right, node.data)
                return subtree

    def remove(self, value):
        # 判断树中是否包含要删除的数据
        if self.search(self.root, value):
            self.remove_node(self.root, value)
            return True
        return False