树形表示法 文氏图表示法 凹入表示法 括号表示法 A(B(E,F)),C(G(J)),D(H,I(K,L,M)))

结点的度：树中某个结点的子树的个数

树的度：树中各个结点中，最大值就是度，通常我们将度为m的树，称为m次树

举个例子

此为 一颗 3次树

分支结点：度不为零的结点 叶子结点：度为零的结点

举个例子

此处，D,I,J,G,H,F 都为叶子结点

路径：一条路，长度等于通过结点数减1

举个例子 例如，A -J

路径为：A - B - E - J 长度为 3

性质1：树中的结点数等于所有结点的度之和加1 （这里的证明，以相对简单来解释） 证明 举个例子 在此，我在所有结点上都标上了度，你会发现，除了叶子结点，也就是度为零的结点，其他结点加起来，就是结点数，但是你会发现根节点并没有算进去，所以这里我们要加1

性质2：度为m的树中第 i 层上最多有 m i-1 个结点（i >= 1)

证明：数学归纳法 对于第一层，将i = 1代进去，mi-1 = m1-1 = 1,显然结论成立 对于第 i - 1 层，将 i = i - 1代进去，第 i - 1层上最多有mi-2 由树的度定义知，度为最大的结点数，那么对于第 i 层来说，第 i - 1层上，每个结点都有m个结点，那么结点数为第 i - 1 层上的m倍。 对于第 i 层，mi-2 * m = mi-1,故在第i层上，也适用这个公式。

举个例子 我们可以用另一种想法来证明这个性质 假设一个度为3的树 我们假设每个结点都是最大结点数，你会发现， 第一层是30 第二层是31 第三层是32 第四层是33 不难发现其中的规律就是公式 mi-1

推广：如果说当一颗树某一层满足以上的规律，称该层是满的，那么一颗树全部都满足，则称这颗树为满m次树 ，以刚刚这个例子来看，便应为满3次树

性质3：高度为h的m次树最多有 ** m h − 1 m − 1 {m^h-1\over m-1} m−1mh−1​**个结点 证明： 由性质2，可以推出，如果我们要球的最多的结点数，那么每一个层都应该是最大结点数 计算如下：m0 + m1 + m2 +……+mh-1 = m h − 1 m − 1 {m^h-1\over m-1} m−1mh−1​

性质4：具有n个结点的m次树的最小高度为 >= l o g m ( n ( m − 1 ) + 1 ) {log_m(n(m -1)+1)} logm​(n(m−1)+1)整数

证明，设具有n个结点的最小高度为 h，这样的树中前h - 1层都是满的，最后一层的结点数，可能满，可能也不满，但至少有一个结点

（我亲手写了证明）

其实，证明下来，还是用到性质3，相当徐性质3的拓展吧。

树的运算主要分为三类

树的遍历也分为三类

先根遍历 **过程：**先访问根节点，按照从左到右的次序遍历根节点每一颗子树 举个例子

后根遍历：从最左边的最下面的结点开始 举个例子 也就是先把子节点都遍历完再去遍历结点

层次遍历 过程：从第一层开始， 从左到右遍历 举个例子‘

树的存储结构有很多，这里介绍三种

顺序存储结构，除了存储值，还存储其双亲的位置

举个例子

看图我们大概就能明白，就是有一个伪指针存放了双亲结点的位置 代码实现

孩子链存储结构（此不谈）

兄弟链存储结构（简略） 此结构，统共每个结点有三个域，一个数据元素域，一个指向该节点的第一个孩子结点的指针域，一个指向该结点的下一个兄弟节点的指针域，每一个结点有固定的两个指针域

举个例子 从这个图上我们就可以很快懂得这种结构

接下来要学习的便是二叉树，这将在我另一篇文章中呈现