平衡二叉树代码（python创建平衡二叉树的方法）

1   
    
    
    、生成平衡树的核心是partial_tree方法   
    
    
    。

它以一个序列和数字为参数    
    
    
，通过递归的方式返回一个序列


     


     


     


。其中第一个是结构树    


     


     


    ，第二个是不包含在书中的元素 




 




 




。

2


     


     


     


、实现的整体思路是




 




 




 


，每次传入的序列分为左半部分 




 




 




、顶点和右半部分   

   

   

，直到不能继续拆分     

     

     

   ，然后逐层返回




  




  




  

，最后组合成一棵平衡的二叉树   

   

   

   。

实例

""" list_to_tree方法将有序列表转化为平衡二叉树 一棵二叉树分为树顶点   

   

   

   、左子树

     

     

     

、右子树
  


  


  


，其中左子树的值都比树顶节点小     
     
     
  ，右子树的值都比树顶点大 """ defmake_tree(entry,left,right): #创建树的方法 return(entry,left,right) defentry(tree): #获取树的顶点 returntree[0] defleft_branch(tree): #获取左子树 returntree[1] defright_branch(tree): #获取右子树 returntree[2] deflist_to_tree(elements): returnpartial_tree(elements,len(elements))[0] defpartial_tree(elts,n): ifn==0: return((),elts) else: left_size=(n-1)2 left_result=partial_tree(elts,left_size) left_tree=left_result[0] non_left_elts=left_result[1] right_size=n-(left_size+1) this_entry=non_left_elts[0] right_result=partial_tree(non_left_elts[1:],right_size) right_tree=right_result[0] remaing_elts=right_result[1] #print("entry",this_entry) #print("left_tree",left_tree) #print("right_tree",right_tree) return(make_tree(this_entry,left_tree,right_tree),remaing_elts) if__name__=="__main__": tree=list_to_tree((1,3,5,7,9)) print("生成的平衡二叉树为:",tree) print("树的顶点：",entry(tree)) print("树的左子树：",left_branch(tree)) print("树的右子树：",right_branch(tree))

以上就是python创建平衡二叉树的方法 




   




   




   
，希望对大家有所帮助

     

     

     

。更多Python学习指路：Python基础教程