一、构建与遍历二叉树
- class Node(object):
- def __init__(self,item):
- self.key=item
- self.left=None
- self.right=None
- class BinaryTree(object):
- def __init__(self):
- self.root=None
- def addNode(self,item):
- new_node = Node(item)
- if self.root is None:
- self.root=new_node
- else:
- stack=[]
- stack.append(self.root)
- while True:
- node=stack.pop(0)
- if node.left is None:
- node.left=new_node
- return
- elif node.right is None:
- node.right=new_node
- return
- else:
- stack.append(node.left)
- stack.append(node.right)
- def traverse(self): #层次遍历
- if self.root is None:
- return None
- else:
- s=[]
- s.append(self.root)
- while len(s) > 0:
- node = s.pop(0)
- print(node.key)
- if node.left is not None:
- s.append(node.left)
- if node.right is not None:
- s.append(node.right)
- def preOrder(self,root):
- if root is None:
- return None
- print(root.key)
- self.preOrder(root.left)
- self.preOrder(root.right)
- def inOrder(self,root):
- if root is None:
- return None
- self.inOrder(root.left)
- print(root.key)
- self.inOrder(root.right)
- def postOrder(self,root):
- if root is None:
- return None
- self.postOrder(root.left)
- self.postOrder(root.right)
- print(root.key)