python-数据结构-代码实现二叉树的遍历
程序员文章站
2022-05-20 20:49:03
...
1.二叉树需要创建一个包含左子树和右子树的节点类
class Node:
"""节点类"""
def __init__(self, item):
self.item = item
self.lchild = None
self.rchild = None
2.创建二叉树,以广度优先遍历方式添加节点
class BinaryTree:
"""二叉树"""
def __init__(self, node=None):
self.root = node
def add(self, item):
"""广度优先遍历方式添加节点"""
if self.root is None:
self.root = Node(item)
else:
queue = []
queue.append(self.root)
while True:
node = queue.pop(0)
if not node.lchild:
node.lchild = Node(item)
return
else:
queue.append(node.lchild)
if not node.rchild:
node.rchild = Node(item)
return
else:
queue.append(node.rchild)
3.使用广度优先遍历对二叉树进行遍历
def breadh_travel(self):
"""广度优先遍历"""
if self.root is None:
return
queue = []
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)
4.使用深度优先遍历对二叉树进行遍历
def preorder_trval(self, root):
"""先序 根 左 右"""
if root:
print(root.item, end="")
self.preorder_trval(root.lchild)
self.preorder_trval(root.rchild)
def inorder(self, root):
"""中序 左 根 右"""
if root:
self.inorder(root.lchild)
print(root.item, end="")
self.inorder(root.rchild)
def postorder_trval(self, root):
"""后序 左 右 根"""
if root:
self.postorder_trval(root.lchild)
self.postorder_trval(root.rchild)
print(root.item, end="")
5.对两种遍历进行测试
if __name__ == '__main__':
tree = BinaryTree()
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.breadh_travel()
print("")
tree.preorder_trval(tree.root)
print("")
tree.inorder(tree.root)
print("")
tree.postorder_trval(tree.root)
print("")