Title

Python实现树

树

树结构是一种包括节点(nodes)和边(edges)的拥有层级关系的一种结构    

二叉树

二叉树是一种简单的树，它的每个节点最多只能包含两个孩子    

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

满二叉树(full binary tree)

如果每个内部节点（非叶节点）都包含两个孩子，就成为满二叉树    

完美二叉树(perfect binary tree)

当所有的叶子节点都在同一层就是完美二叉树，毫无间隙填充了 h 层    

完全二叉树(complete binary tree)

当一个高度为 h 的完美二叉树减少到 h-1，并且最底层的槽被毫无间隙地从左到右填充，我们就叫它完全二叉树    

定义树节点

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

二叉树的遍历

• 先(根)序遍历: 先处理根，之后是左子树，然后是右子树
• 中(根)序遍历: 先处理左子树，之后是根，最后是右子树
• 后(根)序遍历: 先处理左子树，之后是右子树，最后是根

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 BinTreeNode(object):
    def __init__(self, data, left=None, right=None):
        self.data, self.left, self.right = data, left, right

class BinTree(object):
    def __init__(self, root=None):
        self.root = root
    @classmethod
    def build_from(cls, node_list):
        # 通过节点信息构造二叉树
        # 第一次遍历我们构造 node 节点
        # 第二次遍历我们给 root 和 孩子赋值
        # 最后我们用 root 初始化这个类并返回一个对象
        node_dict = {}
        for node_data in node_list:
            data = node_data["data"]
            node_dict[data] = BinTreeNode(data)
        for node_data in node_list:
            data = node_data["data"]
            node = node_dict[data]
            if node_data["is_root"]:
                root = node
            node.left = node_dict.get(node_data["left"])
            node.right = node_dict.get(node_data["right"])
        return cls(root)
    def preorder_trav(self, subtree):
        """
        先(根)序遍历
        :param subtree:
        :return:
        """
        if subtree is not None:
            print(subtree.data)
            self.preorder_trav(subtree.left)
            self.preorder_trav(subtree.right)
     def reverse(self, subtree):
        """
        反转二叉树
        :param subtree: 
        :return: 
        """
        if subtree is not None:
            subtree.left, subtree.right = subtree.right, subtree.left
            self.reverse(subtree.left)
            self.reverse(subtree.right)
           
btree = BinTree.build_from(node_list)
btree.preorder_trav(btree.root)    # 输出 A, B, D, E, H, C, F, G, I, J