python 实现树结构的七种遍历

发布时间：2019-09-23 17:09:48编辑：auto阅读（2012）

class BTree(object):
    def __init__(self, value=None, left=None, right=None):
        self.val = value
        self.left = left
        self.right = right
        self.dot = Digraph(comment='Binary Tree')


def create_BTree_By_List(array):
    i = 1
    # 将原数组拆成层次遍历的数组，每一项都储存这一层所有的节点的数据
    level_order = []
    sum = 1
    while sum < len(array):
        level_order.append(array[i - 1:2 * i - 1])
        i *= 2
        sum += i
    level_order.append(array[i - 1:])

    # BTree_list: 这一层所有的节点组成的列表
    # forword_level: 上一层节点的数据组成的列表
    def Create_BTree_One_Step_Up(BTree_list, forword_level):
        new_BTree_list = []
        i = 0
        for elem in forword_level:
            root = BTree(elem)
            if 2 * i < len(BTree_list):
                root.left = BTree_list[2 * i]
            if 2 * i + 1 < len(BTree_list):
                root.right = BTree_list[2 * i + 1]
            new_BTree_list.append(root)
            i += 1
        return new_BTree_list

    # 如果只有一个节点
    if len(level_order) == 1:
        return BTree(level_order[0][0])
    else:
        BTree_list = [BTree(elem) for elem in level_order[-1]]  # 创建最后一层的节点列表
        # 从下往上，逐层创建二叉树
        for i in range(len(level_order) - 2, -1, -1):
            BTree_list = Create_BTree_One_Step_Up(BTree_list, level_order[i])
        return BTree_list[0]


class TreeTraversal():
    @classmethod
    def preorderTraversal_re(cls, root):
        if not root: return []
        return [root.val] + cls.preorderTraversal_re(root.left) + cls.preorderTraversal_re(root.right)

    @classmethod
    def preorderTraversal(cls, root):
        if not root: return []
        res, stack = [], [root]
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.right: stack.append(node.right)
            if node.left: stack.append(node.left)
        return res

    @classmethod
    def inorderTraversal_re(cls, root):
        if not root: return []
        return cls.inorderTraversal_re(root.left) + [root.val] + cls.inorderTraversal_re(root.right)

    @classmethod
    def inorderTraversal(cls, root):
        if not root: return []
        res, stack = [], []
        while True:
            while root:
                stack.append(root)
                root = root.left
            if not stack: return res
            node = stack.pop()
            res.append(node.val)
            if node.right: root = node.right

    @classmethod
    def postorderTraversal_re(cls, root):
        if not root: return []
        return cls.postorderTraversal_re(root.left) + cls.postorderTraversal_re(root.right) + [root.val]

    @classmethod
    def postorderTraversal(cls, root):
        if not root: return []
        res, stack = [], [root]
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.left: stack.append(node.left)
            if node.right: stack.append(node.right)
        return res[::-1]



    @classmethod
    def levelOrder(cls, root):
        if not root: return []
        res, q = [], [root]
        while q:
            length = len(q)
            for _ in range(length):
                node = q.pop(0)
                res.append(node.val)
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
        return res


if __name__ == '__main__':
    array = [8, 6, 10, 5, 7, 9, 11]
    my_tree = create_BTree_By_List(array)
    my_tree.preorder()
    print(TreeTraversal.preorderTraversal_re(my_tree))
    print(TreeTraversal.preorderTraversal(my_tree))
    print(TreeTraversal.inorderTraversal_re(my_tree))
    print(TreeTraversal.inorderTraversal(my_tree))
    print(TreeTraversal.postorderTraversal_re(my_tree))
    print(TreeTraversal.postorderTraversal(my_tree))
    print(TreeTraversal.levelOrder(my_tree))

关键字：