树,是一种数据结构。链式 存储方式。由n(n>0)个节点组成。每个节点有零个子节点或多个子节点。没有父节点的成为根节点。
相关术语:
深度:这个树向下的最大层数称为度。
叶节点或终端节点:度为0的节点成为叶节点。
子孙:以某节点为根向下任意的子节点都成为该节点的子孙。
森林:由多个不相交的树的集合成为森林。
分类:
无序树:树中任意节点的子结点之间没有顺序关系,这种树称为无序树,也称为自由树。
有序树:树中任意节点的子结点之间有顺序关系,这种树称为有序树。
二叉树:每个节点最多含有两个子树的树称为二叉树。完全二叉树,满二叉树都是为了方便对二叉树进行操作。
霍夫曼树:带权路径最短的二叉树称为哈夫曼树或最优二叉树;
常见的满二叉树
树的遍历:
树的遍历方式有三种:先序遍历,中序遍历,后序遍历。
先序遍历的规则为:根节点>左节点>右节点
以上图举个栗子:先序结果为1245367
中序遍历的规则为:左节点>根节点>右节点
举个栗子:中序结果为4251637
后序遍历的规则为:左节点>右节点>根节点
举个栗子:后序结果为4526731
在C语言中实现主要思想使用递归,较简单参见CSDN。
根据已知二叉树的三种遍历结果还原二叉树
已知先,中序遍历或者中,后序遍历,是可以画出二叉树的。在已知先,后序,是不可以还原二叉树的。
领取专属 10元无门槛券
私享最新 技术干货