"""
bitree.py 二叉樹的簡單實(shí)踐
思路分析：
1. 使用鏈?zhǔn)酱鎯?chǔ)，一個(gè)Ｎｏｄｅ表示一個(gè)樹的節(jié)點(diǎn)
2. 節(jié)點(diǎn)考慮使用兩個(gè)屬性變量分別表示左連接和右連接
"""
from squeue import *
# 二叉樹節(jié)點(diǎn)
class Node:
def __init__(self,val,left=None,right = None):
self.val = val
self.left = left
self.right = right
# 二叉樹遍歷類
class Bitree:
def __init__(self,root = None):
self.root = root
# 先序遍歷
def preOrder(self,node):
if node is None: # 終止條件
return
print(node.val,end = '')
self.preOrder(node.left)
self.preOrder(node.right)
# 中序遍歷
def inOrder(self, node):
if node is None: # 終止條件
return
self.inOrder(node.left)
print(node.val,end = "")
self.inOrder(node.right)
# 后序遍歷
def postOrder(self, node):
if node is None: # 終止條件
return
self.postOrder(node.left)
self.postOrder(node.right)
print(node.val, end="")
# 層次遍歷
def levelOrder(self,node):
"""
讓初始節(jié)點(diǎn)先入隊(duì)樊破，誰出隊(duì)就遍歷誰，并且讓它的左右孩子分別入隊(duì)娘汞，直到隊(duì)列為空
"""
sq = SQueue()
sq.enqueue(node) # 初始節(jié)點(diǎn)入隊(duì)
while not sq.is_empty():
node = sq.dequeue()
# 打印出隊(duì)元素
print(node.val,end='')
if node.left:
sq.enqueue(node.left)
if node.right:
sq.enqueue(node.right)
if __name__ == "__main__":
# B F G D I H E C A
# 根據(jù)后續(xù)遍歷構(gòu)建二叉樹
b = Node('B')
f = Node('F')
g = Node('G')
d = Node('D',f,g)
i = Node('I')
h = Node('H')
e = Node('E',i,h)
c = Node('C',d,e)
a = Node('A',b,c) #樹根
# 將a作為遍歷的起始位置
bt = Bitree(a)
bt.preOrder(bt.root)
print()
bt.inOrder(bt.root)
print()
bt.postOrder(bt.root)
print()
bt.levelOrder(bt.root)
二叉樹遍歷
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門柴我，熙熙樓的掌柜王于貴愁眉苦臉地迎上來解寝，“玉大人，你說我怎么就攤上這事艘儒×祝” “怎么了？”我有些...
- 文/不壞的土叔 我叫張陵界睁，是天一觀的道長觉增。 經(jīng)常有香客問我，道長晕窑，這世上最難降的妖魔是什么抑片？ 我笑而不...
- 正文 為了忘掉前任卵佛，我火速辦了婚禮杨赤，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘截汪。我一直安慰自己疾牲，他們只是感情好，可當(dāng)我...
- 文/花漫 我一把揭開白布衙解。 她就那樣靜靜地躺著阳柔，像睡著了一般。 火紅的嫁衣襯著肌膚如雪蚓峦。 梳的紋絲不亂的頭發(fā)上舌剂，一...
- 文/蒼蘭香墨 我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼岩喷！你這毒婦竟也來了恕沫？” 一聲冷哼從身側(cè)響起，我...
- 序言：老撾萬榮一對(duì)情侶失蹤纱意，失蹤者是張志新（化名）和其女友劉穎婶溯，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體偷霉，經(jīng)...
- 正文 獨(dú)居荒郊野嶺守林人離奇死亡爬虱，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
- 正文 我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了腾它。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片跑筝。...
- 正文 年R本政府宣布虏两，位于F島的核電站，受9級(jí)特大地震影響世剖，放射性物質(zhì)發(fā)生泄漏定罢。R本人自食惡果不足惜，卻給世界環(huán)境...
- 文/蒙蒙 一旁瘫、第九天 我趴在偏房一處隱蔽的房頂上張望祖凫。 院中可真熱鬧，春花似錦酬凳、人聲如沸惠况。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽稠屠。三九已至，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間权埠，已是汗流浹背榨了。 一陣腳步聲響...
- 正文 我出身青樓，卻偏偏與公主長得像秩彤，于是被迫代替她去往敵國和親叔扼。 傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
推薦閱讀更多精彩內(nèi)容
- 引子：五分鐘玩轉(zhuǎn)面試考點(diǎn)-數(shù)據(jù)結(jié)構(gòu)系列漫雷，不會(huì)像那種嚴(yán)肅瓜富、古板的教科書般的博客文章，而是將晦澀難懂的概念和知識(shí)點(diǎn)盡可...
- 注：本文來自 左程云的書《程序員代碼面試指南》 題目：分別用遞歸和非遞歸方法价捧，實(shí)現(xiàn)二叉樹的先序遍歷(根左右)、中序...
- 前言 二叉樹作為一種非澄写粒基礎(chǔ)但十分重要的數(shù)據(jù)結(jié)構(gòu)结蟋，在排序、搜索渔彰、編碼嵌屎、甚至文件系統(tǒng)管理等方面都有廣泛應(yīng)用。今天恍涂，我...
