用对象的思想创建二叉树并实现四种遍历-python版
2017-08-10 本文已影响104人
HelloSunPing
直接上代码:
#coding:utf-8
class Node(object):
"""二叉树节点"""
def __init__(self, item):
super(Node, self).__init__()
self.item = item
self.lchild = None
self.rchild = None
class Tree(object):
"""二叉树类"""
def __init__(self):
super(Tree, self).__init__()
self.root = None
def add(self, item):
"""添加节点"""
node = Node(item)
# 判断当前树是否为空
if self.root is None:
self.root = node
else:
queue = []
queue.append(self.root)
# 采用队列存放, 先将根节点放入队列中,取出,看是否有左子树和右子树,有就放入并且循环回来看子树的子树,没有则添加
while queue:
temp = queue.pop(0)
# 看做节点是否为空
if temp.lchild is None:
temp.lchild = node
break
# 看右节点是否为空
elif temp.rchild is None:
temp.rchild = node
break
# 都不为空,将左节点和右节点放入队列
else:
queue.append(temp.lchild)
queue.append(temp.rchild)
def wide_travel(self):
"""广度优先遍历(广序遍历):从上到下,从左到右.利用队列"""
if self.root is None:
return
else:
queue = []
queue.append(self.root)
while queue:
temp = queue.pop(0)
print(temp.item, end=" ")
# 如果有左孩子则放入队列
if temp.lchild is not None:
queue.append(temp.lchild)
# 如果有右孩子则放入队列
if temp.rchild is not None:
queue.append(temp.rchild)
print()
# 深度遍历采用了递归
def preorder(self, node):
"""深度遍历-先序遍历(根节点-左子树-右子树)"""
if node is None:
return
print(node.item, end=" ")
self.preorder(node.lchild)
self.preorder(node.rchild)
def inorder(self, node):
"""深度遍历-中序遍历(左子树-根节点-右子树)"""
if node is None:
return
self.inorder(node.lchild)
print(node.item, end=" ")
self.inorder(node.rchild)
def posorder(self, node):
"""深度遍历-后序遍历(左子树-右子树-根节点)"""
if node is None:
return
self.posorder(node.lchild)
self.posorder(node.rchild)
print(node.item, end=" ")
if __name__ == '__main__':
tree = Tree()
for char in "ABCDEFG":
tree.add(char)
print("先序遍历:")
tree.preorder(tree.root)
print("\n中序遍历:")
tree.inorder(tree.root)
print("\n后序遍历:")
tree.posorder(tree.root)
print("\n广度遍历:")
tree.wide_travel()
