二叉树

树的定义

树是一种数据结构，由n（n>=1）个有限结点组成的一个具有层次关系的集合。每颗树都有一个根结点，根结点下有若干个子结点，每一个非根结点有且只有一个父结点（根节点没有父结点）。除了根结点外，每个子结点又可以分为多个不相交的子树。

二叉树是一种特殊的树，每个结点最多有两个子树的树结构，即使某结点只有一个子树，也要区分左右子树，左子树和右子树是有顺序的。它有五种基本形态：空二叉树、根和空的左右子树、根和左子树、根和右子树、根和左右子树。

二叉树遍历

二叉树遍历指从树的根节点出发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被访问仅且一次。从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成，因此，在任一给定结点上，可以按某种次序执行三个操作：访问结点本身（N）；遍历该结点的左子树（L）；遍历该结点的右子树（R）。
以上三种操作有六种执行次序：NLR、LNR、LRN、NRL、RNL、RLN。前三种次序与后三种次序是对称的，此处讨论下前三种次序。
1、NLR为前序遍历(Preorder Traversal 亦称先序遍历）访问根结点的操作发生在遍历其左右子树之前。先访问根结点，再先序遍历左子树，最后再先序遍历右子树即根—左—右。
2、LNR为中序遍历(Inorder Traversal)。访问根结点的操作发生在遍历其左右子树之中（间）。先中序遍历左子树，然后再访问根结点，最后再中序遍历右子树即左—根—右。
3、LRN为后序遍历(Postorder Traversal)。访问根结点的操作发生在遍历其左右子树之后。先后序遍历左子树，然后再后序遍历右子树，最后再访问根结点即左—右—根。
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。