数据结构二叉树的基础理解以及遍历

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

image.png

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

image.png

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

image.png

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

image.png

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

image.png

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

image.png

二叉树由一个根结点和两个左子树和右子树构成，子树也是二叉树。5种形态：空结点， 无左右子树结点，只有左子树结点，只有右子树结点和左右子树都存在的结点。

满二叉树：二叉树种，所有分支结点都存在左右子树，且所有叶子结点都在一层上。

完全二叉树：有n个结点与满二叉树的结构相同。

image.png
image.png

再看看二叉树的遍历，分别是前序遍历、中序遍历和后序遍历。（根在中间、左边孩子），根节点（根），左子树（左）、右子树（右）。（遍历时，左边遍历完才能到右边）

如图，例子的前序遍历是：ABDHIMEJNCFKG。（简记口诀：根左右）

image.png

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

image.png

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

image.png image.png

答案：
前序遍历：abdhinejcfkglomp
中序遍历：hdnibjeafkcolgmp
后续遍历：hnidjebkfolpmgca。