什么是树？二叉树的基本术语是什么？

1。什么是树？

树是一种数据结构。它是一种非线性数据结构。上面我们提到的大部分数据结构都是线性的，也比较简单。数据结构，下面的树和图都是非线性数据结构，也是一个概念很多的范畴。

树是一种由节点或顶点和边（可能是非线性的）组成的数据结构，并且不包含环。没有节点的树称为空（null 或empty）树。非空树由一个主节点和（可能）几个附加节点组成，所有这些节点形成多级层次结构。

树的定义：n个节点的有限集合。 n=0，空树； n>0，1个根节点，m个不相交的有限集，每个子​​集是根的子树。

正如如图所示，照片中有一棵树：

2。基本树术语

l 节点的度：树中节点的子树数量。

l 树的度：树中每个节点的度的最大值。

l 分支节点：度数非零的节点。

l 叶节点：度数为零的节点。

l 路径：i->j；路径长度：路径经过的节点数减1。

l 子节点：某个节点的后继节点；父节点：该节点是其子节点的父节点（父节点）；姐妹节点：同一父节点的子节点；后代节点：某个节点的所有子树中的节点；祖先节点：从树节点到本节点的路径上的节点。

l 节点级别：根节点为第一级别（以此类推）；树高：树中节点的最大层数。

l 有序树：树中节点的子树从左到右排列，顺序不能改变；无序的树：恰恰相反。

l 森林：杂乱树木的集合。

3。树的属性值

l 树的节点树是所有节点的度加1（加上根节点）。

l 度为 m 的树的第 i 层最多有 m^(i-1) 个节点。

l 高度为 h 的第 m 棵树最多有 (m^h-1) )/(m-1) 个节点。

l 具有 n 个节点的 m 树的最小高度为 logm(n(m-1) + 1) 向上舍入。 ？这些术语对于熟悉树的基本概念非常有用。