微信公众号： 点击蓝色字体小白图像与视觉进行关注

有问题或建议，请公众号留言

下面主要讲二叉树

整理知识，学习笔记发布日记，杂文，所见所想

1. 二叉树的遍历

1.1 广度优先遍历 breadth_travel

1.2 深度优先遍历 先序遍历，中序遍历，后序遍历三种

1.3 已知先序中序求后序

广度优先遍历,深度优先一般用递归，广度优先一般用队列。一般情况下能用递归实现的算法大部分也能用堆栈来实现。广度优先遍历,从树的root开始，从上到下从从左到右遍历整个树的节点那么深度遍历有重要的三种方法。这三种方式常被用于访问树的节点，它们之间的不同在于访问每个节点的次序不同。这三种遍历分别叫做先序遍历（preorder），中序遍历（inorder）和后序遍历（postorder）。 #!/usr/bin/env python3.6.5# -*- coding: UTF-8 -*-"""Author: yanyongDate: 2020/10/3 14:44docs:"""#创建单个节点类class Node(object):    def __init__(self, elem, lchild = None, rchild = None):        self.elem = elem        self.plchild = lchild        self.prchild= rchild#创建树的类class Tree(object):    def __init__(self, rootNode = None):        self.root = rootNode    def add(self, elem):        #实现一个只添加一个节点，在主函数中若要添加多个  则需要重复调用        """实现树上面添加节点"""        node = Node(elem)#创建一个节点        if self.root == None:#如果树为空，则对根节点赋值            #print("树为空") #用于测试            self.root = node        # print("树不为空")        else:#树不为空，那么依次加入节点进行层次遍历            queue = [] #用队列实现树            queue.append(self.root)            while queue:                cur_node = queue.pop(0)#始终弹出队列的第一个元素进行判断                if cur_node.plchild is None:                    cur_node.plchild = node                    return                else:#如果左子树都不为空，则把当前节点的左子节点加入队列继续判断                    queue.append(cur_node.plchild)                if cur_node.prchild is None:                    cur_node.prchild = node                    return                else:#如果右子树都不为空，则把当前节点的右子节点加入队列继续判断                    queue.append(cur_node.prchild)    def breadth_travel(self):        """广度优先遍历(层次遍历)"""        if self.root == None:            return        queue = []#用队列实现树遍历        queue.append(self.root)        while queue:            cur_node = queue.pop(0)            print(cur_node.elem, end=' ')            if cur_node.plchild is not None:                queue.append(cur_node.plchild)            if cur_node.prchild is not None:                queue.append(cur_node.prchild)    #深度优先遍历    #先序遍历  根节点->左子树->右子树    def preorder(self, cur_rootNode):        if cur_rootNode == None:            return #return是从当前递归调用的函数中返回        print(cur_rootNode.elem, end=' ')        self.preorder(cur_rootNode.plchild)        self.preorder(cur_rootNode.prchild)    #中序遍历 左子树->根节点->右子树    def inorder(self, cur_rootNode):        if cur_rootNode == None:            return #return是从当前递归调用的函数中返回        self.inorder(cur_rootNode.plchild)        print(cur_rootNode.elem, end=' ')        self.inorder(cur_rootNode.prchild)    #后序遍历 左子树->右子树->根节点    def postorder(self, cur_rootNode):        if cur_rootNode == None:#return是从当前递归调用的函数中返回            return        self.postorder(cur_rootNode.plchild)        self.postorder(cur_rootNode.prchild)        print(cur_rootNode.elem, end=' ')if __name__ == "__main__":    tree = Tree()    tree.add(0)    tree.add(1)    tree.add(2)    tree.add(3)    tree.add(4)    tree.add(5)    tree.add(6)    tree.add(7)    tree.add(8)    tree.add(9)    print("breadth_travel:")    tree.breadth_travel()    print(' ')    #这依赖于前面已经监理了一棵树 然后把数的根结点传进去    print("postorder:")    tree.postorder(tree.root)

输出结果：

breadth_travel:0 1 2 3 4 5 6 7 8 9  postorder:7 8 3 9 4 1 5 6 2 0 

已知先序中序求后序

#!/usr/bin/env python3.6.5# -*- coding: UTF-8 -*-"""Author: yanyongDate: 2020/10/3 17:16docs: """def get_after_deep(pre, mid, a):    """    已知先序和中序递归求后序    :param pre: [1, 2, 4, 5, 8, 9, 11, 3, 6, 7, 10]    :param mid: [4, 2, 8, 5, 11, 9, 1, 6, 3, 10, 7]    :param a:  []    :return: a    """    if len(pre) == 1:        a.append(pre[0])        return    if len(pre) == 0:        return    root = pre[0]    root_index = mid.index(root)    get_after_deep(pre[1:root_index + 1], mid[:root_index], a)    get_after_deep(pre[root_index+1:], mid[root_index+1:], a)    a.append(root)    return ares = get_after_deep([1, 2, 4, 5, 8, 9, 11, 3, 6, 7, 10], [4, 2, 8, 5, 11, 9, 1, 6, 3, 10, 7], [])print(res)

输出结果：

[4, 8, 11, 9, 5, 2, 6, 10, 7, 3, 1]

更多请扫码关注：