树

概述

基本概念

树：从树根生长，逐级分支

• 空树–节点数为0的数
• 非空树：有且仅有一个根节点
• 除了根节点外，任何一个节点都有且仅有一个前驱结点
• 路径：从一个结点抵达另一个结点经过的结点序列，只能从上往下进行，故同一双亲的两个孩子间没有路径
• 路径长度：路径经过边的个数

树的属性

• 结点层次(深度)：从上往下的层数(默认从1开始计算)
• 节点高度：从下往上数
• 树的高度：总层数
• 节点的度：有几个孩子(分支)
• 树的度：取决于个各节点度的最大值

有序树：逻辑上，树中结点的各子树从左至右是有次序的，不能互换

无序树：逻辑上，树中结点的各子树从左至右是无次序的，可以互换

常考性质

1. 结点数=总度数+1，结点的度即结点有多少分支(孩子)
2. 度为m与m叉树的区分

3. 度为m的树第i层最多有m^i-1个结点(i>=1)
4. 高度为h的m叉树最多有$\frac{m^h-1}{m-1}$个结点
5. 高度为h的m叉树至少有h个结点(光棍的样子)
6. 高度为h、度为m的树至少有h+m-1个结点，在光棍的基础上某一层加了m-1个结点
7. 具有n个结点的m叉树的最小高度为$\lceil log_m(n(m-1)+1)\rceil$ （向上取整）
   • 由4推导而来，高度最小情况下每个结点都有m个孩子

树的存储结构

树是一种递归定义的数据结构

双亲表示法

1
2
3
4
5
6
7
8
9

#define Maxsize 100
typedef struct{
    ElemType data;
    int parent;//双亲位置域
}PTNode;
typedef struct{
    PTNode nodes[Maxsize];
    int n;//结点数
}PTree;

• 优点：查找指定节点双亲很方便
• 缺点：查指定结点的孩子只能从头遍历

孩子表示法(顺序+链式)

• 顺序存储各个节点，每个节点保存孩子链表头指针

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

struct CTNode{
    int child;
    struct CTNode *next;
};
typedef struct{
    ElemType data;
    struct CTNode *firstChild;
}CTBox;
typedef struct{
    CTBox nodes[Max];
    int n,r;
}CTree;

孩子兄弟表示法(链式)

1
2
3
4

typedef struct CSNode{
    ElemType data;
    struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;

树与二叉树转换

森林与二叉树的转换：将森林的根节点视作兄弟关系

树的遍历

• 先根遍历：若树非空，先访问根节点，再依次对每棵子树进行先根遍历

• 转化为二叉树进行先序遍历

• 后根遍历与先根遍历类似。后根遍历序列对应二叉树中序序列

• 层序遍历：与二叉树的层序遍历几乎一样

森林的遍历

先序遍历：对森林中各个根节点依次进行先根遍历

也可以转化为二叉树进行先序遍历，效果等同。

中序遍历：对森林中各个根节点依次进行中根遍历

注：森林是没有后根遍历的！