python完全二叉树

通过实现完全二叉树，学习其相应的递归算法

class Node(object):
    def __init__(self,value=None,left=None,rigth=None):
        self.value =value
        self.left =left
        self.right =rigth

class Complete_binary_tree(object):
    def __init__(self,root=None):
        self.root = root
        self.node_list = []
        self.root_to_leaf_number_list = []
        self.sum_of_left_leaves_value = 0
        self.min_depth = 0
        self.value_status = [False,False]

    #  创建一个完全二叉树(除了最后一层,所有层的节点数达到最大,与此同时最后一层的所有节点都从左侧开始排列)
    def create_binary_tree(self,list):
        assert len(list)>0
        self.root = Node(list[0])
        self.node_list.append(self.root)
        for i in range(1,len(list)):
            cur_node = Node(list[i])
            if i%2==1:
                self.node_list[int(i/2)].left = cur_node
            else:
                self.node_list[int(i/2)-1].right = cur_node
            self.node_list.append(cur_node)

    #  中序遍历
    def sort_show(self):
        assert self.root
        print('中序遍历:',end='')
        self._sort_show(self.root)
        print('None')

    def _sort_show(self,cur_node):
        if cur_node.left:
            self._sort_show(cur_node.left)
        print(str(cur_node.value)+ '->',end='')
        if cur_node.right:
            self._sort_show(cur_node.right)

    #  计算树中节点的总数
    def node_number(self):
        result = self._node_number(self.root)
        print('树中节点的总数:',result)
        return result

    def _node_number(self,node):
        left_dep = right_dep = 0
        tmp1 = tmp2 = node
        while tmp1:
            left_dep+=1
            tmp1 = tmp1.left
        while tmp2:
            right_dep+=1
            tmp2 = tmp2.right
        if left_dep==right_dep:
            return 2**left_dep -1
        else:
            return 1 + self._node_number(node.left) + self._node_number(node.right)

    #  从根节点到叶子节点的每条路径可以表示为一个数,求这些数的列表
    def sum_root_to_leaf_numbers(self):
        self._sum_root_to_leaf_numbers(self.root)
        print('根节点至叶子节点的所有路径:' , self.root_to_leaf_number_list)

    def _sum_root_to_leaf_numbers(self,node,value_string=''):
        if not node:
            return
        if not node.left and not node.right:
            value_string += str(node.value)
            self.root_to_leaf_number_list.append(int(value_string))
            return
        self._sum_root_to_leaf_numbers(node.left,value_string+str(node.value))
        self._sum_root_to_leaf_numbers(node.right,value_string+str(node.value))


    #  给定二叉树和两个节点,寻找这两个节点的最近公共祖先                      
    #  如图所示                                                                                         
    #  5和1最近公共祖先为3                                                                
    #  5和4最近公共祖先为5                                                                    
    #  求一颗二叉树的最低深度
    #              3
    #           5    1
    #         6  2  0  8
    #           7 4
    def lowest_common_ancestor(self,value1,value2):
        assert (isinstance(value1,int) and isinstance(value2,int) and self.node_number()>=2)
        result = self._lowest_common_ancestor(self.root,self.root,value1,value2)
        print('两个节点的最近公共祖先为:',result)

    # node为搜索节点,flag_node为标记节点
    def _lowest_common_ancestor(self,node,flag_node,value1,value2):
        if not node:
            return
        if True not in self.value_status:  #[False,False]
            if node.value == value1:  self.value_status[0] = True
            if node.value == value2:  self.value_status[1] = True
            return self._lowest_common_ancestor(node.left, node, value1, value2) or self._lowest_common_ancestor(
                node.right, node, value1, value2)
        elif True in self.value_status and False in self.value_status and node.value!=value1 and node.value!=value2:
            print(flag_node.value)
            return self._lowest_common_ancestor(node.left, flag_node, value1, value2) or self._lowest_common_ancestor(
                node.right, flag_node, value1, value2)
        else:  #在已有标记点的情况下,发现了另外一个节点   [False,True] or [True,False]
            self.value_status[0] = self.value_status[1] = True
            return flag_node.value

    #  求出一颗二叉树所有左叶子的和(二叉树通用方法)
    def sum_of_left_leaves(self):
        assert (self.root)
        self._sum_of_left_leaves(self.root)
        print('该二叉树所有左叶子的和:',self.sum_of_left_leaves_value)

    def _sum_of_left_leaves(self,node,flag='',sum=0):
        if not node:
            return
        if flag=='left' and not node.left and not node.right:
            self.sum_of_left_leaves_value += node.value
            return
        return self._sum_of_left_leaves(node.left,'left',sum) or self._sum_of_left_leaves(node.right,'right',sum)


    #  从根节点到叶子节点的最小深度(二叉树通用方法)
    def minimum_depth(self):
        assert (self.root)
        self._minimum_depth(self.root)
        print('从根节点到叶子节点的最短路径长度:',self.min_depth)

    def _minimum_depth(self,node,depth=0):
        if not node:
            self.min_depth = depth
            return
        if self.min_depth>depth:
            return self._minimum_depth(node.left, depth + 1) or self._minimum_depth(node.right,depth + 1)
        elif depth==self.min_depth:
            self.min_depth +=1
            return self._minimum_depth(node.left, depth + 1) or self._minimum_depth(node.right, depth + 1)
        else:  #min_depth<depth
            return

tree = Complete_binary_tree()
tree.create_binary_tree([1,2,3,4,5,6,7,8])
tree.sort_show()

#  根节点至叶子节点的所有路径
tree.sum_root_to_leaf_numbers()

#  二叉树所有左叶子的和
tree.sum_of_left_leaves()

#  从根节点到叶子节点的最小深度
tree.minimum_depth()

#  最近公共祖先
tree.lowest_common_ancestor(5,8)

output:
中序遍历:8->4->2->5->1->6->3->7->None
根节点至叶子节点的所有路径: [1248, 125, 136, 137]
该二叉树所有左叶子的和: 14
从根节点到叶子节点的最短路径长度: 3
树中节点的总数: 8
两个节点的最近公共祖先为: 2