一：代碼實(shí)現(xiàn)
class TreeNode:
"""節(jié)點(diǎn)類"""
def __init__(self, mid, left=None, right=None):
self.mid = mid
self.left = left
self.right = right
# 樹(shù)類
class Tree:
"""樹(shù)類"""
def __init__(self, root=None):
self.root = root
def add(self, item):
# 將要添加的數(shù)據(jù)封裝成一個(gè)node結(jié)點(diǎn)
node = TreeNode(item)
if not self.root:
self.root = node
return
queue = [self.root]
while queue:
cur = queue.pop(0)
if not cur.left:
cur.left = node
return
else:
queue.append(cur.left)
if not cur.right:
cur.right = node
return
else:
queue.append(cur.right)
tree = Tree()
tree.add(0)
tree.add(1)
tree.add(2)
tree.add(3)
tree.add(4)
tree.add(5)
tree.add(6)
二：遍歷
在上述樹(shù)類代碼基礎(chǔ)上加遍歷函數(shù)，基于遞歸實(shí)現(xiàn)。
先序遍歷：
先序遍歷結(jié)果是：0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6
# 先序遍歷
def preorder(self, root, result=[]):
if not root:
return
result.append(root.mid)
self.preorder(root.left, result)
self.preorder(root.right, result)
return result
print("先序遍歷")
print(tree.preorder(tree.root))
"""
先序遍歷
[0, 1, 3, 4, 2, 5, 6]
"""
中序遍歷：
中序遍歷結(jié)果是：3 -> 1 -> 4 -> 0 -> 5 -> 2 -> 6
# 中序遍歷
def inorder(self, root, result=[]):
if not root:
return result
self.inorder(root.left, result)
result.append(root.mid)
self.inorder(root.right, result)
return result
print("中序遍歷")
print(tree.inorder(tree.root))
"""
中序遍歷
3, 1, 4, 0, 5, 2, 6]
"""
后續(xù)遍歷
后序遍歷結(jié)果是：3 -> 4 -> 1 -> 5 -> 6 -> 2 -> 0
# 后序遍歷
def postorder(self, root, result=[]):
if not root:
return result
self.postorder(root.left, result)
self.postorder(root.right, result)
result.append(root.mid)
return result
print("后序遍歷")
print(tree.postorder(tree.root))
"""
后序遍歷
[3, 4, 1, 5, 6, 2, 0]
"""
到此這篇關(guān)于教你如何使用Python實(shí)現(xiàn)二叉樹(shù)結(jié)構(gòu)及三種遍歷的文章就介紹到這了,更多相關(guān)Python實(shí)現(xiàn)二叉樹(shù)結(jié)構(gòu)及三種遍歷內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:- Python數(shù)據(jù)結(jié)構(gòu)與算法之二叉樹(shù)結(jié)構(gòu)定義與遍歷方法詳解
- Python實(shí)現(xiàn)二叉樹(shù)結(jié)構(gòu)與進(jìn)行二叉樹(shù)遍歷的方法詳解
