树

• 无序树
• 有序树
  • 二叉树

  # 创建树节点
  class Tree(object):
     def __init__(self, elem):
         self.elem = elem
         self.lchild = None
         self.rchild = None
  

深度遍历

• 先序遍历

 def preorder(self, node):
     if node == None:
         return
     print(node.elem)
     self.preorder(node.lchild)
     self.preorder(node.rchild)

• 中序遍历

  def preorder(self, node):
      if node == None:
           return        
       self.preorder(node.lchild)
       print(node.elem)
       self.preorder(node.rchild)

• 后续遍历

  def preorder(self, node):
      if node == None:
          return        
      self.preorder(node.lchild)
      self.preorder(node.rchild)
      print(node.elem)

广度遍历

def breadth_travel(self, root):
    if root == None:
          return
      queue = []
      queue.append(root)
      while queue:
          node = queue.pop(0)
          print node.elem,
          if node.lchild != None:
              queue.append(node.lchild)
          if node.rchild != None:
              queue.append(node.rchild)