廣度優(yōu)先(層次遍歷)

從樹的root開始，從上到下從左到右遍歷整個(gè)樹的節(jié)點(diǎn)

數(shù)和二叉樹的區(qū)別就是，二叉樹只有左右兩個(gè)節(jié)點(diǎn)

廣度優(yōu)先 順序：A - B - C - D - E - F - G - H - I

代碼實(shí)現(xiàn)

def breadth_travel(self, root):
        """利用隊(duì)列實(shí)現(xiàn)樹的層次遍歷"""
        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)

深度優(yōu)先

深度優(yōu)先有三種算法：前序遍歷，中序遍歷，后序遍歷

image.png

• 先序遍歷 在先序遍歷中，我們先訪問根節(jié)點(diǎn)，然后遞歸使用先序遍歷訪問左子樹，再遞歸使用先序遍歷訪問右子樹
  根節(jié)點(diǎn)->左子樹->右子樹

    #實(shí)現(xiàn) 1
    def preorder(self, root):
          """遞歸實(shí)現(xiàn)先序遍歷"""
          if root == None:
              return
          print root.elem
          self.preorder(root.lchild)
          self.preorder(root.rchild)
         
    #實(shí)現(xiàn) 2  
    def depth_tree(tree_node):
        if tree_node is not None:
            print (tree_node._data)
            if tree_node._left is noe None:
                return depth_tree(tree_node._left)
            if tree_node._right is not None:
                return depth_tree(tree_node._right)
  

• 中序遍歷 在中序遍歷中，我們遞歸使用中序遍歷訪問左子樹，然后訪問根節(jié)點(diǎn)，最后再遞歸使用中序遍歷訪問右子樹
  左子樹->根節(jié)點(diǎn)->右子樹

def inorder(self, root):
      """遞歸實(shí)現(xiàn)中序遍歷"""
      if root == None:
          return
      self.inorder(root.lchild)
      print root.elem
      self.inorder(root.rchild) 

• 后序遍歷 在后序遍歷中，我們先遞歸使用后序遍歷訪問左子樹和右子樹，最后訪問根節(jié)點(diǎn)
  左子樹->右子樹->根節(jié)點(diǎn)

def postorder(self, root):
      """遞歸實(shí)現(xiàn)后續(xù)遍歷"""
      if root == None:
          return
      self.postorder(root.lchild)
      self.postorder(root.rchild)
      print root.elem