数据结构二叉树的遍历

1、首先，来认识树的相关概念。结点的度是该结点有多少个孩子结点就是该结点的度（简单来说，一个结点向下有几根出去的线，度就是几）。如图所示，A的度是4，B和C的度是2，其它的度都是0。度为0又称作叶结点（终端结点），不为0的度就是分支结点（或非终端节点）。

2、孩子结点（或者是后继结点），如图所示，A的度是四，A的四个孩子结点分别是B、C、D、E。B的孩子结点分别是F和G。

3、双亲结点（或者称直接前驱结点），例如上一步说到的B、C、D、E是A的孩子结点，那么A就是B、C、D、E的双亲结点点，也就是直接前驱结点。B、C分别是F和G，H和I的双亲结点。

4、兄弟结点，例如B、C、D和E是兄弟结点，F和G是兄弟结点，H和I是兄弟结点。

5、区分树的度和结点的度。很好理解，结点的度中最大值就是树的度！例如图中的树的度是4，因为结点度中最大值是A的度是4。

6、结点的层次，根节点的层次为0，从根节点开奘疚豫枭始，后面的孩子结点都是其双亲结点的层次+1。如A的层次为0，B、C、D、E的层次是1，F、G是B的层次+1（即2），H、I是C的层次+1（即2）。树的深度，是结点层次的最大值，这颗树的深度是2。

7、二叉树由一个根结点和两个左子树和右子树构成，子树也是二叉树。5种形态：空结点， 无左右子树结点，只有左子树结点，只有右子树结点和左右子树拎枋辏话都存在的结点。满二叉树：二叉树种，所有分支结点都存在左右子树，切所有叶子结点都在一层上。完全二叉树：有n个结点与满二叉树的结构相同。

8、再看看二叉树的遍历，分别是前序遍历、中序遍历和后序遍历。（根在中间、左边孩子），根节点（根），左子树（左）、右子树（右）。（遍历时，左边遍历完才能到右边）如图，例子的前序遍历是：ABDHIMEJNCFKG。（简记口诀：根左右）

9、它的中序遍历是：HDMIBJNEAFKCG。（简记口诀：左根右）

10、它的后序遍历是：HMIDNJEBKFGC。（简记口诀：左右根）

11、做一下下面才、这题检验下学习成果。

12、答案：前序遍历：abdhinejcfkglomp 中序遍历：hdnibjeafkcolgmp 后续遍历：hnidjebkfolpmgca。可以试想一下给出两个顺序的遍历，如何推算出二叉树图和写出第三个遍历。