python 数据结构 tree 的插入和遍历
python 数据结构 tree 的插入和遍历
hyhlinux 发表于1年前
python 数据结构 tree 的插入和遍历
• 发表于 1年前
• 阅读 10
• 收藏 0
• 评论 0

# coding:utf-8
class Node(object):
"""docstring for Node"""

def __init__(self, item=-1, lchild=None, rchild=None):
self.item = item
self.lchild = lchild
self.rchild = rchild

class Tree(object):
"""docstring for Tree"""

def __init__(self):
self.root = Node()

'''
添加一个节点
顺序:从上至下，从左至右.
'''
node = Node(item)

if self.root.item == -1:
self.root = node
else:
myqueue = []
tree_node = self.root
myqueue.append(tree_node)

while myqueue:
tree_node = myqueue.pop(0)
if not tree_node.lchild:
# 左孩子空，添加到左孩子.
tree_node.lchild = node
return
elif not tree_node.rchild:
tree_node.rchild = node
return
else:
# 若左右都不为空，加入该节点的左右孩子到列表
myqueue.append(tree_node.lchild)
myqueue.append(tree_node.rchild)

def front(self, root=None):
if not root:
return
print(root.item)
self.front(root.lchild)
self.front(root.rchild)

def middle(self, root=None):
if not root:
return
self.middle(root.lchild)
print(root.item)
self.middle(root.rchild)

def later(self, root=None):
if not root:
return
self.later(root.lchild)
self.later(root.rchild)
print(root.item)

def level_search(self, root):
'''
从上至下，从左至右.
'''
if not root:
return

myQueue = []
node = root
myQueue.append(node)

while myQueue:
tree_node = myQueue.pop(0)
print(tree_node.item)

if tree_node.lchild:
myQueue.append(tree_node.lchild)

if tree_node.rchild:
myQueue.append(tree_node.rchild)

def main():
tree = Tree()
for i in xrange(7):

# tree.front(tree.root)
# 0 1 3 4 2 5 6
# tree.middle(tree.root)
# 3 1 4 0 5 2 6
# tree.later(tree.root)
#3, 4, 1, 5, 6, 2, 0
tree.level_search(tree.root)
# 0 1 2 3 4 5 6

if __name__ == '__main__':
main()

##########################
#             0
#     1       |     2
# 3       4   |  5      6
##########################

×