简介

一棵以根节点开始，每个节点不超过N个子节点的树，称为 N叉树。

前缀树，又称字典树(Trie)， 就是一个常用的N叉树。

遍历

一棵二叉树可以按照前序、中序、后序或者层序来进行遍历。在这些遍历方法中，前序遍历、后序遍历和层序遍历同样可以运用到N叉树中。

二叉树的遍历

  1. 前序遍历 - 首先访问根节点，然后遍历左子树，最后遍历右子树；
  2. 中序遍历 - 首先遍历左子树，然后访问根节点，最后遍历右子树；
  3. 后序遍历 - 首先遍历左子树，然后遍历右子树，最后访问根节点；
  4. 层序遍历 - 按照从左到右的顺序，逐层遍历各个节点。

N叉树

N叉树的中序遍历没有标准定义，中序遍历只有在二叉树中有明确的定义。尽管我们可以通过几种不同的方法来定义N叉树的中序遍历，但是这些描述都不是特别贴切，并且在实践中也不常用到，所以我们暂且跳过N叉树中序遍历的部分。

把上述关于二叉树遍历转换为N叉树遍历，我们只需把如下表述:

  1. 遍历左子树... 遍历右子树...

变为:

对于每个子节点:
      通过递归地调用遍历函数来遍历以该子节点为根的子树

例

image.png

  1. 前序遍历

A->B->C->E->F->D->G

先访问根节点，然后逐个遍历以其子节点为根的子树。

  1. 后序遍历

B->E->F->C->G->D->A

先逐个遍历以根节点的子节点为根的子树，最后访问根节点。

  1. 层序遍历

A->B->C->D->E->F->G

同二叉树（广度优先搜索）。