二叉树

来源

1. 二叉树 前序、中序、后序、层次遍历及非递归实现 查找、统计个数、比较、求深度的递归实现

2. 二叉树的实现及先序、中序、后序遍历

3. Depth-first search in a tree

4. Graph traversals

二叉树的遍历

遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历，中序遍历，后序遍历。

前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点

例如：求下面树的三种遍历

前序遍历：abdefgc
中序遍历：debgfac
后序遍历：edgfbca

深度优先搜索

如下是一棵树：

深度优先搜索：

unit

** 时间 **
跑遍这个树所需要的时间：

** 递归实现 **

TreeDFS(root):
      // do anything we need to do when first visiting the root
      for each child of root:
        TreeDFS(child)
      // do anything we need to do when last visiting the root