定义
- 树是有n个结点的有限集
n\geq0 - n=0,为空树
- 在任意一颗非空树中：
- 有且仅有一个特定的称为根（Root）的结点
- n>1,其余结点可以分为m（m>0)个互不相交的有限集
T_1，T_2，...，T_m - 其中，每个集合本身又是一棵树，且称为根的子树
结点分类
- 结点拥有的子树个数，称为度（Degree）
- 度为0的结点，是叶子结点或终端结点
- 度不为0的结点，称为分支结点或非终端结点
- 除根结点之外，分支结点也称为内部结点
- 另，树的度，是树内各结点的度的最大值
结点间关系
- 结点的子树的根，称为该结点的孩子
- 该结点，称为孩子的双亲，同一个双亲的孩子之间，就是兄弟结点
高度或深度
- 结点的层次，从根开始定义起，根为第一层，根的孩子为第二层，依次类推
- 然后，把树中结点的最大层次称为树的深度或高度
树的分类
- 如果将树中结点的各子树，看成是从左到右是有次序的，不能互换的，则该树为有序树
- 否则，为无序树
森林
- 是m棵（
m\geq0）互不相交的树的集合
双亲表示法
假设以一组连续的空间存储树的结点，同时，在每个结点中，附设一个指示器指示其双亲结点在数组中的位置
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
//结点结构 #define MAXSIZE 1000 typedef int ElemType; typedef struct PTNode { ElemType data; int parent; }PTNode; typedef struct { PTNode nodes[MAXSIZE]; int r,n; }PTree; |
| 下标 | data | parent | firstchild |
| 0 | A | -1 | 1 |
| 1 | B | 0 | 3 |
| 2 | C | 0 | 4 |
| 3 | D | 1 | 6 |
| 4 | E | 2 | 9 |
| 5 | F | 2 | -1 |
| 6 | G | 3 | -1 |
| 7 | H | 3 | -1 |
| 8 | I | 3 | -1 |
| 9 | J | 4 | -1 |
孩子表示法
- 方法一：
- 每个结点有多个指针域，每个指针指向一棵子树的根结点，这种方法叫做多重链表法
- 方法二：
- 每个结点指针域的个数，等于该结点的度，另专门取一个位置来存储结点指针域的个数
总结：
把每个结点的孩子结点排列起来，以单链表作为存储结构，则n个结点有n个孩子链表，如果是叶子结点，则此单链表为空，然后n个头指针组成一个线性表，采用顺序存储结构，存放在一个数组里面
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
//结构 #define MAXSIZE 1000 typedef struct CTNode//孩子结点 { int child; struct CTNode * next; }*ChildPtr; typedef struct//表头结构 { ElemType data; ChildPtr firstchild; }CTBox; typedef struct//树结构 { CTBox nodes[MAXSIZE]; int r,n;//根的位置和结点数 }CTree; |
孩子兄弟表示法
任意一棵树，它的结点第一孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此我们可以设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟
|
1 2 3 4 5 6 |
//结构 typedef struct CSNode { ElemType data; struct CSNode * firstchild,* rightsib; }CSNode,*CSTree; |
本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
你可能也喜欢
- ♥ Dump分析：空指针访问二，重复释放堆内存二03/30
- ♥ 大话数据结构_图遍历01/27
- ♥ 大话数据结构_图相关02/17
- ♥ 红黑树05/01
- ♥ 大话数据结构_图表示01/14
- ♥ 大话数据结构_赫夫曼树与应用01/11
热评文章
- 大话数据结构_图 0
- 大话数据结构_二叉树_结构&&遍历&&推导 0
- 大话数据结构_图表示 0
- 大话数据结构_二叉树 0
- 大话数据结构_图遍历 0
- 大话数据结构_队列 0