• 热门专题

Python排序搜索基本算法之二叉树的深度和宽度

作者:  发布日期:2014-04-15 20:45:15
Tag标签:宽度  算法  深度  
  • 接着上一个二叉树的主题,用python写一下求二叉树深度和宽度的代码,求深度用递归;求宽度用队列,然后把每层的宽度求出来,找出最大的就是二叉树的宽度,如下:

     

    import queue
    
    class Node:
    	def __init__(self,value=None,left=None,right=None):
    		self.value=value
    		self.left=left
    		self.right=right
    
    def treeDepth(tree):
    	if tree==None:
    		return 0
    	leftDepth=treeDepth(tree.left)
    	rightDepth=treeDepth(tree.right)
    	if leftDepth>rightDepth:
    		return leftDepth+1
    	if rightDepth>=leftDepth:
    		return rightDepth+1
    
    def treeWidth(tree):
    	curwidth=1
    	maxwidth=0
    	q=queue.Queue()
    	q.put(tree)
    	while not q.empty():
    		n=curwidth
    		for i in range(n):
    			tmp=q.get()
    			curwidth-=1
    			if tmp.left:
    				q.put(tmp.left)
    				curwidth+=1
    			if tmp.right:
    				q.put(tmp.right)
    				curwidth+=1
    		if curwidth>maxwidth:
    			maxwidth=curwidth
    	return maxwidth
    
    if __name__=='__main__':
    	root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))
    	depth=treeDepth(root)
    	width=treeWidth(root)
    	print('depth:',depth)
    	print('width:',width)

    输出为:

     

     

    depth: 4
    width: 3
    

    转自http://blog.csdn.net/littlethunder/article/details/23736491
About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规