Python完全二叉树的构建，包含广度优先插入节点、广度遍历、先序、中序、后序遍历等函数。
class Node(object):
"""节点"""
def __init__(self, item):
self.elem = item
self.lchild = None
self.rchild = None
class Tree(object):
"""二叉树"""
def __init__(self):
self.root = None
self.preorder_list = []
self.inorder_list = []
self.postorder_list = []
def add(self, item):
"""
插入树节点
广度优先
"""
node = Node(item)
if self.root == None:
self.root = node
return
queue = [self.root]
while queue:
cur_node = queue.pop(0)
if cur_node.lchild == None:
cur_node.lchild = node
return
else:
queue.append(cur_node.lchild)
if cur_node.rchild == None:
cur_node.rchild = node
return
else:
queue.append(cur_node.rchild)
def breadth_travel(self):
"""
广度遍历
"""
if self.root == None:
return []
queue = [self.root]
ls = [self.root.elem]
while queue:
cur_node = queue.pop(0)
if cur_node.lchild == None:
return ls
else:
ls.append(cur_node.lchild.elem)
queue.append(cur_node.lchild)
if cur_node.rchild == None:
return ls
else:
ls.append(cur_node.rchild.elem)
queue.append(cur_node.rchild)
def is_empty(self):
"""
判断树是否为空
"""
if self.root == None:
print(True)
else:
print(False)
def list_add(self, add_list):
"""
输入列表快速添加树节点
"""
for i in add_list:
self.add(i)
def pre(self, node):
"""
先序遍历
根 左 右
"""
if node == None:
return
self.preorder_list.append(node.elem)
self.pre(node.lchild)
self.pre(node.rchild)
def preorder(self):
self.pre(self.root)
return self.preorder_list
def mid(self, node):
"""
中序遍历
左 根 右
"""
if node == None:
return
self.mid(node.lchild)
self.inorder_list.append(node.elem)
self.mid(node.rchild)
def inorder(self):
self.mid(self.root)
return self.inorder_list
def pos(self, node):
"""
后序遍历
左 右 根
"""
if node == None:
return
self.pos(node.lchild)
self.pos(node.rchild)
self.postorder_list.append(node.elem)
def postorder(self):
self.pos(self.root)
return self.postorder_list
if __name__ == "__main__":
tree = Tree()
tree.list_add([0,1,2,3,4,5,6,7,8,9])
tree.add(10)
ls=tree.breadth_travel()
print(ls)
ls = tree.preorder()
print(ls)
ls=tree.inorder()
print(ls)
ls=tree.postorder()
print(ls)
