数据结构学习笔记(十八)——树的基本概念(2)

1 树的性质

（1）树中的节点数等于所以节点的度数加1。

（2）度为m的树中第i层上至多有m∧i-1个节点（i≥1）。

推广：当一棵m次树的第i层有m∧i-1个节点（i≥1）时，称该层是满的，若一棵m次树的所有叶子节点在同一层，除该层外其余每一层都是满的，称该树为满m次树。

（3）高度为h的m次树至多有(m∧h - 1)/(m - 1)个节点。

（4）具有n个节点的m次树的最小高度为log m (n(m-1)+1)(取最小整数)

2 树的基本运算（主要分为三大类）

（1）寻找满足某种特定关系的节点，如寻找当前节点的双亲节点等。

（2）插入或删除某个节点，如在树的当前节点上插入一个新节点或删除当前节点的第i个孩子节点等。

（3）遍历树中每个节点。树的遍历是指按某种方式访问树中的每一个节点且每个节点只被访问一次。主要有先根遍历、后根遍历和层次遍历3种。

先根遍历的过程：（1）访问根节点；（2）按照从左到右的次序先根遍历根节点的每一棵树。图一采用该方式遍历得到的节点序列为：ABDECF。

后根遍历的过程：（1）按照从左到右的次序后根遍历节点的每一棵子树；（2）访问根节点。图一采用该方式遍历得到的节点序列为：DEBFCA。

层次遍历的过程：从根节点开始，从上到下、从左到右访问树中每一个节点。图一采用该方式遍历得到的节点序列为：ABCDEF。

3 存储结构

（1）双亲存储结构：这是一种顺序存储结构，用一组连续空间存储树的所有节点，同时在每个节点中附设一个伪指针指示双亲节点的位置。其存储结构的类型定义为：

typedef struct{

ElemType data; // 存放节点的值

int parent; // 存放双亲的位置

} PTree[MaxSize];

（2）孩子链存储结构：在该存储结构中，每个节点不仅包含数据值，还包含指向其所有孩子节点的指针，并且按树的度（即树中所有节点度的最大值）设计节点的孩子节点指针域个数。其存储结构的类型定义为：

typedef struct node{

ElemType data; // 存放节点的值

struct node * sons[MaxSons]; // 指向孩子节点

}TSonNode;

（3）孩子兄弟链存储结构：在该存储结构中每个节点有3个域，一个数据元素域，一个指向该节点的第一个孩子 节点的指针域，一个指向该节点的下一个兄弟节点的指针域。其存储结构的类型定义为：

typedef struct tnode{

ElemType data; // 存放节点的值

struct tnode * hp; // 指向兄弟节点

struct tnode *vp; // 指向孩子节点

} TSBNode;