二叉木の構造及び各種遍歴
2331 ワード
class Node(object):
''' '''
def __init__(self,elem):
self.data = elem
self.lchild = None
self.rchild = None
class Tree(object):
''' '''
def __init__(self):
self.root = None
def add(self,item):
node = Node(item)
queue = []
if self.root is None:
self.root = node
return
queue.append(self.root)
while queue:
cur_node = queue.pop(0)
if cur_node.lchild is None:
cur_node.lchild = node
return
else:
queue.append(cur_node.lchild)
if cur_node.rchild is None:
cur_node.rchild = node
return
else:
queue.append(cur_node.rchild)
def breath_traval(self):
''' '''
if self.root is None:
return
queue = [self.root]
while queue:
cur_node = queue.pop(0)
print(cur_node.data,end=' ')
if cur_node.lchild is not None:
queue.append(cur_node.lchild)
if cur_node.rchild is not None:
queue.append(cur_node.rchild)
def pre_order(self,node):
''' '''
if node is None:
return
print(node.data,end=' ')
self.pre_order(node.lchild)
self.pre_order(node.rchild)
def mid_order(self,node):
''' '''
if node is None:
return
self.mid_order(node.lchild)
print(node.data, end=' ')
self.mid_order(node.rchild)
def post_order(self,node):
''' '''
if node is None:
return
self.post_order(node.lchild)
self.post_order(node.rchild)
print(node.data, end=' ')
if __name__ == '__main__':
tree = Tree()
tree.add(1)
tree.add(2)
tree.add(3)
tree.add(4)
tree.add(5)
tree.breath_traval()
print('
')
tree.pre_order(tree.root)
print('
')
tree.mid_order(tree.root)
print('
')
tree.post_order(tree.root)