九.二叉树

向右看齐 2023-02-17 15:56 1阅读 0赞

原文链接:https://www.cnblogs.com/bobo-zhang/p/10856009.html

#  #

[ 11.二叉树 ][11._]

</h1>
 <div class="clear"></div>
 <div class="postBody">

python实现二叉树的数据结构：

. 二叉树的排序方式：

- 广度遍历（层次遍历）

*　　　　- 深度遍历：  
　　　　　　- 前序（根左右）：把根放到最前面  
　　　　　　- 中序（左根右）：把根放到中间  
　　　　　　- 后序（左右根）：把根放到最后*

![复制代码][Image 1]

class Node():
 def __init__(self,item):
 self.item = item
 self.right = None
 self.left = None
 class Tree():
 def __init__(self):
 self.root = None
 def add(self,item):
 node = Node(item)
 if self.root is None:
 self.root = node
 return
 else:
 queue = [self.root]
 while queue:
 cur = queue.pop(0)
 if cur.left is None:
 cur.left = node
 return
 else:
 queue.append(cur.left)
 if cur.right is None:
 cur.right = node
 return
 else:
 queue.append(cur.right)
 #广度遍历
 def travel(self):
 if self.root is None:
 print('')
 return
 else:
 queue = [self.root]
 while queue:
 cur = queue.pop(0)
 print(cur.item)
 if cur.left is not None:
 queue.append(cur.left)
 if cur.right is not None:
 queue.append(cur.right)
 #深度遍历：前序，中序，后序遍历
 def forwordTravel(self,root):
 if root is None:
 return
 print(root.item,end=' ')
 self.forwordTravel(root.left)
 self.forwordTravel(root.right)
 
 def middleTravel(self,root):
 if root is None:
 return
 self.middleTravel(root.left)
 print(root.item,end=' ')
 self.middleTravel(root.right)
 
 def backTravel(self,root):
 if root is None:
 return
 self.backTravel(root.left)
 self.backTravel(root.right)
 print(root.item,end=' ')

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’)

tree.travel()  
tree.forwordTravel(tree.root)  
print(’\\n’)  
tree.backTravel(tree.root)  
print(’\\n’)  
tree.middleTravel(tree.root)  
print(’\\n’)

![复制代码][Image 1]

python实现排序二叉树：

![复制代码][Image 1]

#排序二叉树
 class Node():
 def __init__(self,item):
 self.item = item
 self.left = None
 self.right = None
 class Tree():
 def __init__(self):
 self.root = None
 def insert(self,item):
 node = Node(item)
 cur = self.root
 if cur is None:
 self.root = node
 return
 while True:
 if item < cur.item:
 if cur.left is None:
 cur.left = node
 return
 else:
 cur = cur.left
 else:
 if cur.right is None:
 cur.right = node
 return
 else:
 cur = cur.right
 def preTravel(self,root):
 if root is None:
 return
 print(root.item,end=' ')
 self.preTravel(root.left)
 self.preTravel(root.right)
 def middleTravel(self,root):
 if root is None:
 return
 self.middleTravel(root.left)
 print(root.item,end=' ')
 self.middleTravel(root.right)
 def backTravel(self,root):
 if root is None:
 return
 self.backTravel(root.left)
 self.backTravel(root.right)
 print(root.item,end=' ')

tree = Tree()  
tree.insert(3)  
tree.insert(8)  
tree.insert(5)  
tree.insert(7)  
tree.insert(6)  
tree.preTravel(tree.root)  
print(’\\n’)  
tree.middleTravel(tree.root)  
print(’\\n’)  
tree.backTravel(tree.root)  
print(’\\n’)

</pre>

![复制代码][Image 1]

分类: [数据结构+算法][Link 1]

好文要顶 关注我 收藏该文 ![icon_weibo_24.png][] ![wechat.png][]

[![20190729093950.png][]][20190729093950.png 1]

[波晓张][20190729093950.png 1]  
[关注 - 2][- 2]  
[粉丝 - 542][- 542]

\+加关注

<div class="clear"></div>
 <div id="post_next_prev">
 
 <a href="https://www.cnblogs.com/bobo-zhang/p/10735140.html" class="p_n_p_prefix">« </a> 上一篇： <a href="https://www.cnblogs.com/bobo-zhang/p/10735140.html" title="发布于 2019-05-11 18:25">高性能异步爬虫</a>
 
 <a href="https://www.cnblogs.com/bobo-zhang/p/10574925.html" class="p_n_p_prefix">» </a> 下一篇： <a href="https://www.cnblogs.com/bobo-zhang/p/10574925.html" title="发布于 2019-05-20 11:18">10.排序</a>

posted @ 2019-05-13 12:46  [波晓张][Link 2]  阅读( 391)  评论( 0)  [编辑][Link 3]  收藏

</div>

刷新评论 刷新页面 返回顶部

注册用户登录后才能发表评论，请 登录 或 注册， [访问][Link 4] 网站首页。

[【推荐】了解你才能更懂你，博客园首发问卷调查，助力社区新升级][Link 5]  
[【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库][50_VC_ _CAD_GIS]  
[【推荐】精品问答：精品问答：Python 技术 1000 问][Python _ 1000]

[11._]: https://www.cnblogs.com/bobo-zhang/p/10856009.html
[Image 1]: 
[Link 1]: https://www.cnblogs.com/bobo-zhang/category/1417180.html
[icon_weibo_24.png]: https://common.cnblogs.com/images/icon_weibo_24.png
[wechat.png]: https://common.cnblogs.com/images/wechat.png
[20190729093950.png]: https://pic.cnblogs.com/face/1489694/20190729093950.png
[20190729093950.png 1]: https://home.cnblogs.com/u/bobo-zhang/
[- 2]: https://home.cnblogs.com/u/bobo-zhang/followees/
[- 542]: https://home.cnblogs.com/u/bobo-zhang/followers/
[Link 2]: https://www.cnblogs.com/bobo-zhang/
[Link 3]: https://i.cnblogs.com/EditPosts.aspx?postid=10856009
[Link 4]: https://www.cnblogs.com/
[Link 5]: https://www.wenjuan.com/s/3uIjeq0/
[50_VC_ _CAD_GIS]: http://www.ucancode.com/index.htm
[Python _ 1000]: https://developer.aliyun.com/ask/257928?utm_content=g_1000088948