多叉树的遍历

其实二叉树就是特殊的多叉树，多叉树的每个结点都有任意个结点，如下图所示：

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

森林：

森林是多叉树的集合，一颗多叉树也是一种特殊的森林。 多叉树的遍历与二叉树一样，分为DFS和BFS两种。

1. DFS算法：

    def traverse(root):
        if root is not None:
            return
        # 前序位置
        for child in root.children:
            traverse(child)
        # 后序位置
   

   与二叉树的深度遍历不同的是没有中序位置了，因为一个结点有多个子节点，因此再区分中序没什么意义。

2. BFS算法： 多叉树的层序遍历算法和二叉树的层序遍历一样，都是通过队列实现，区别只是二叉树仅仅添加其左右子节点即可，而多叉树需要添加所有子节点。所以多叉树的BFS算法同样也有三种实现方式：
   1. 第一种写法，无法确定遍历深度：

       from collections import deque
      
       def travese(root):
           if root is None:
               return
           q = deque()
           q.append(root)
           while q:
               current = q.popleft()
               # 操作步骤
               print(current.value)
               for child in current.children:
                   q.append(child)
      

   2. 第二种写法，能够保存遍历深度：

       from collections import deque
      
       def travese(root):
           if root is None:
               return
           q = deque()
           q.append(root)
           depth = 1
                  
           while q:
               sz = len(q)
               for _ in range(sz):
                   current = q.popleft()
                   # 操作步骤
                   print(current.value)
                          
                   for child in current.children:
                       q.append(child)
               depth += 1
      

      • 若没有sz循环，则代码无法区分层级，更无法确定深度，会将所有子节点混淆，设置sz的目的就是一次仅处理一层的结点。
   3. 第三种写法，能够适配不同权重边：

       from collections import deque
      
       class State:
           def __init__(self, node, path):
               self.node = node
               self.path = path
      
       def travese(root):
           if root is None:
               return
           q = deque()
           q.append(State(root, 1))
                  
           while q:
               state = q.popleft()
               current = state.node
               depth = state.path
                      
               # 操作步骤
               print(current.value, depth)
                          
               for child in current.children:
                   q.append(child)