数据结构-树

树，是一种数据结构。链式 存储方式。由n(n>0)个节点组成。每个节点有零个子节点或多个子节点。没有父节点的成为根节点。

相关术语：

深度：这个树向下的最大层数称为度。

叶节点或终端节点：度为0的节点成为叶节点。

子孙：以某节点为根向下任意的子节点都成为该节点的子孙。

森林：由多个不相交的树的集合成为森林。

分类：

无序树：树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为自由树。

有序树：树中任意节点的子结点之间有顺序关系，这种树称为有序树。

二叉树：每个节点最多含有两个子树的树称为二叉树。完全二叉树，满二叉树都是为了方便对二叉树进行操作。

霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树；

常见的满二叉树

树的遍历：

树的遍历方式有三种：先序遍历，中序遍历，后序遍历。

先序遍历的规则为：根节点>左节点>右节点

以上图举个栗子：先序结果为1245367

中序遍历的规则为：左节点>根节点>右节点

举个栗子:中序结果为4251637

后序遍历的规则为:左节点>右节点>根节点

举个栗子：后序结果为4526731

在C语言中实现主要思想使用递归，较简单参见CSDN。

根据已知二叉树的三种遍历结果还原二叉树

已知先，中序遍历或者中，后序遍历，是可以画出二叉树的。在已知先，后序，是不可以还原二叉树的。