Python打印二叉树的左视图、右视图-白红宇

Python打印二叉树的左视图、右视图

阅读量：4300 次

发布时间：2019-05-27

本文共 3130 字，大约阅读时间需要 10 分钟。

先求出二叉树的最大深度，然后求出每一层的节点列表，求每一层节点列表就相当于求距离根节点指定深度的所有节点，再将每一层的节点列表中的最左或最右节点打印出来，或者添加到新列表中，就是二叉树的左视图、右视图了。。。

class Node():    def __init__(self,value,lchild=None,rchild=None,):        self.value=value        self.lchild=lchild        self.rchild=rchild    def __repr__(self):        return str(self.value)class Tree():    def __init__(self,root=None):        self.root=root        self.node_list=[]    def add_node(self,node):        self.node_list.append(node)        temp_list=[]        temp_list.append(self.root)        if self.root == None:            self.root=node        else:            while temp_list:                cur_node=temp_list.pop(0)                if not cur_node.lchild:                    cur_node.lchild=node                    return                elif not cur_node.rchild:                    cur_node.rchild=node                    return                else:                    temp_list.append(cur_node.lchild)                    temp_list.append(cur_node.rchild)    #Depth First Search 深度优先 三种遍历方式    def preorder(self, root,):        """递归实现先序遍历"""        if root == None:            return        print (root.value)        self.preorder(root.lchild)        self.preorder(root.rchild)    def inorder(self, root):        """递归实现中序遍历"""        if root == None:            return        self.inorder(root.lchild)        print(root.value)        self.inorder(root.rchild)    def postorder(self, root):        """递归实现后序遍历"""        if root == None:            return        self.postorder(root.lchild)        self.postorder(root.rchild)        print(root.value)    #Breadth First Search 广度优先搜索    def bfs(self,root):        temp_list=[]        temp_list.append(root)        while temp_list:            cur_node=temp_list.pop()            print(cur_node.value)            if cur_node.lchild:                temp_list.insert(0,cur_node.lchild)            if cur_node.rchild:                temp_list.insert(0,cur_node.rchild)    #找到距离根节点指定距离的所有节点    def find_target_length(self,root,n,target_list=[]):        if n==0:            target_list.append(root)            # print(self.target_list)            # return target_list        if root.lchild:            self.find_target_length(root.lchild,n-1,target_list)        if root.rchild:            self.find_target_length(root.rchild,n-1,target_list)        return target_list    #二叉树的最大深度    def find_max_deep(self,root):        if (not root.lchild) and (not root.rchild):            return 1        if root.lchild:            lenght1=self.find_max_deep(root.lchild)        else:            lenght1=0        if root.rchild:            lenght2 =self.find_max_deep(root.rchild)        else:            lenght2=0        return 1+max(lenght1,lenght2)    #二叉树的左视图    def find_left_view(self,root):        deep_list=[]        out_put_list=[]        max_deep=self.find_max_deep(root)        print('max_deep:',max_deep)        cur_deep=0        while cur_deep

从代码可看出二叉树的形状如下：