第四章：树与二叉树

1.树的基本概念

首先树是一种逻辑结构。树：是n(n≥0)个结点的有限集合,n=0时,称为空树。而任意非空树应满足:

· 1)有且仅有一个特定的称为根的结点

· 2)当n>1时,其余结点可分为m(m>0个互不相交的有限集合,其中每一个集合本身又是一棵树,称为根结点的子树。

特点： 除根结点外每一个结点都有一个一个前驱结点。每一个结点都有零个或多个后继结点。

n个结点的树只有n-1条边。

2.基本术语

2.1树的结点

2.2树的度

度： 树中一个结点的子节点的个数称为该结点的度

树的度： 树中最大度数称为树的度

A的度：4

2.3树的分支结点和叶子结点

度大于0的结点称为 分支结点 （ABCDE）

度为0的结点称为 叶子结点 （FGHIJKL）

2.4结点的层次、高度、深度

层次： 有的第一层也叫第零层

结点的高度：从叶结点开始向上逐层累加的。例如B结点的高度为3，他分别经历了第四层、第三层和第二层。

结点的深度：从根结点自顶向下逐层累加的。

树的高度（深度）是树中结点的最大层数。 高度和深度是相同的。

2.5有序树与无序树

有序树从左到右每一个子树都是有次序的。

无序树从左到右每一个子树都是无次序的。这种树称为无序树,也称为自由树

2.6路径

路径 树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的。

树中的分支是有向的,即从双亲结点指向孩子结点,所以路径一定是自上而下的，也就是说E结点是无法到达F结点的，他们之间不存在路径。例如：A到E的路径为：ABE

路径长度：路径上所经历边的个数。

例如：A到E的路径长度为：2

2.7森林

森林：m(m>=0)棵互不相交的树的集合。

3.树的性质

1)树种结点的个数等于所有结点(不算根结点)的度数加 1

2)度为m的树种第i层上至多有m^(i-1)个结点(i>=1)

3)高度为h的m叉树至多有(m^h-1)/(m-1)个结点

这个就是等比数列求和，最多就是每一个结点的子结点数都为m，这个等比数列的公比为m，首项都是1，根据等比数列1-m为负数，1-q^n也为负数，这里公式就直接调换位置了，结果不变。

4)具有n个结点的m叉树的最小高度为logm(n(m-1)+1) 向下取整。

这个就是第三个性质的推论，首先是高度最小，则就是尽量将结点安排在较小的层上面，也就是每一个结点的子结点数尽量都为m，设(m^h-1)/(m-1)=n，求出m即可，至于结果向下取整，是因为这个结果计算的不一定为整数，因为我们这里的条件是最小高度，则就是每层结点个数，除了最后一层，都达到最大数，那么这个最后一层可能就不满足结点最大数，那么使用这个公式计算的结果就会出现小数，但是最后一层也是有结点的也算一层，所以向下取整。

关于数据结构的知识，持续更新中，欢迎关注公众号理木客