二叉樹
二叉樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”(left subtree)和“右子樹”(right subtree)
class Node(object):
"""二叉樹節點類"""
def __init__(self,item):
self.item = item
self.lchild = None
self.rchild = None
class BinaryTree(object):
"""二叉樹"""
def __init__(self,node = None):
# 初始的時候二叉樹是空的根節點指向None
self.root = node
def add(self,item):
"""
廣度優先周遊方式添加節點
:param item:
:return:
"""
# 如果沒有根節點,添加的節點就是根節點
if self.root is None:
self.root = Node(item)
return
# 建立一個空清單用于當做隊列模式
queue = list()
# 将根節點添加到清單
queue.append(self.root)
while len(queue) > 0:
# 取清單中的第一個節點
node = queue.pop(0)
# 如果這個節點沒有左子節點把添加的節點放在這個節點的左子節點位置,添加完成
if node.lchild is None:
node.lchild = Node(item)
return
else:
# 否則将這個節點的左子節點添加到清單尾部
queue.append(node.lchild)
# 如果這個節點沒有右子節點把添加的節點放在這個節點的右子節點位置,添加完成
if node.rchild is None:
node.rchild = Node(item)
return
else:
# 否則将這個節點添加到清單尾部
queue.append(node.rchild)
def breadh_travel(self):
"""廣度優先周遊"""
# 如果根節點不存在不用周遊了
if not self.root:
return
# 建立一個清單用于用隊列存放節點,在依次取出節點并列印
queue = list()
# 添加根節點
queue.append(self.root)
# 循環周遊直到清單裡面沒有資料
while len(queue) > 0:
# 取出先添加的節點
node = queue.pop(0)
# 列印在前面的節點
print(node.item,end=" ")
# 如果這個節點有左子節點
if node.lchild:
# 将這個左子節點添加到清單尾部
queue.append(node.lchild)
# 如果這個節點有右子節點
if node.rchild:
# 将這個右子節點添加到清單尾部
queue.append(node.rchild)
def preordef_travel(self,root):
"""先序周遊 根 左 右 """
# 如果節點存在的話
if root:
# 列印這個節點的數值
print(root.item,end=" ")
# 将這個節點的左子節點調有這個先序方法繼續周遊
self.preordef_travel(root.lchild)
# 将這個節點的右子節點調有這個先序方法繼續周遊
self.preordef_travel(root.rchild)
def inordef_travel(self,root):
"""中序周遊 左 根 右 """
# 如果節點存在的話
if root:
# 将這個節點的左子節點調有這個中序方法繼續周遊
self.inordef_travel(root.lchild)
# 列印這個節點的數值
print(root.item, end=" ")
# 将這個節點的右子節點調有這個中序方法繼續周遊
self.inordef_travel(root.rchild)
def postordef_travel(self,root):
"""後序周遊 左 右 根 """
# 如果節點存在的話
if root:
# 将這個節點的左子節點調有這個後序方法繼續周遊
self.postordef_travel(root.lchild)
# 将這個節點的右子節點調有這個後序方法繼續周遊
self.postordef_travel(root.rchild)
# 列印這個節點的數值
print(root.item, end=" ")
if __name__ == '__main__':
# node = ErChaShu()
node = BinaryTree()
node.add(0)
node.add(1)
node.add(2)
node.add(3)
node.add(4)
node.add(5)
node.add(6)
node.add(7)
node.add(8)
node.add(9)
node.breadh_travel()
print()
node.preordef_travel(node.root)
print()
node.inordef_travel(node.root)
print()
node.postordef_travel(node.root)