树 && 二叉树

数据结构与算法 / 数据结构
Word count: 4.1k   |   Reading time≈ 16 min

树

树：是n(n>=0)个节点的有限集
n=0，空树
n>0，只有一个跟root，其余节点为根的子树

数的基本术语

树的基本术语.png 根结点：非空树中无前驱结点的结点 **结点的度**：结点拥有的子树数 树的度：数内结点的度的最大值 叶子节点(终端节点)：度为0，没有子树了 非终端节点：度不为0，根结点以外分支结点称为内部结点 上下的关系： 结点的子树根为该结点的**孩子**，该结点称为孩子的**双亲** 结点的**祖先**：从根到该结点所经分支上的所有节点。 节点的**子孙**：以某一节点为根的子树中的任一节点。 水平关系： 兄弟结点：有共同双亲的结点 堂兄弟：双亲在同一层的结点

树的深度：树中结点的最大层次。

森林：是m(m>=0)颗互不相交的数的集合(把根节点删除数就变成了森林)

树：当结点只有一个孩子时，就无须区分它是左还是右的次序(但是二叉树一定区分)

二叉树

二叉树的概念：最多只有“两个”叉的树(结构最简单、规律性最强)
是n(n>=0)个节点的有限集，或是空集(n=0)，或由一个根节点及两颗互不相交的分别称作这个根的左子树和右子树的二叉树组成。

1.二叉树的性质

  1. 在二叉树的第 i 层上至多有 2^(i-1) 个节点

  2. 深度为 n 的二叉树至多有 2ⁿ-1个节点

  3. 对于任意一颗二叉树 T ，如果其子叶树为 n₀，度为 2 的结点数为 n₂ ，则 n₀ = n₂ + 1
    两种特殊形式的二叉树：
    满二叉树：深度为 n 且具有 2ⁿ-1 个结点的二叉树称为满二叉树
    给二叉树编号：从上到下，从左到右
    完全二叉树：深度为 k 的具有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中的编号为 1-n 的结点一一对应时(位置&&编号)，称之为完全二叉树

  4. 具有 n 个节点的完全二叉树的深度为 ⌊㏒₂ n⌋ + 1
    ⌊x⌋称作x的底，表示不大于x的最大整数

  5. 表明了完全二叉树中双亲结点编号与孩子结点编号之间的关系
    总共有 n 个节点，结点编号为 i
    ①i = 1，则节点i是二叉树的根，无双亲；如果 i > 1，则其双亲是 Li /2J。
    ②若2i > n，则结点 i 为叶子结点，无左孩子；
    否则，其左孩子是结点2i
    ③若2i + 1> n，则节点 i 无右孩子；
    否则，其右孩子结点是2i + 1

2.二叉树的存储结构

二叉树的存储结构.png
顺序存储结构：从0开始给树编号
二叉树的顺序存储缺点：
结点间的关系蕴藏在其存储位置中，浪费空间，适于存满二叉树和完全二叉树。
链式存储结构：
二叉链表(找后继方便)

1
2
3
4
5
6
typedef struct BiNode{
	TElemType data;
	struct BiNode *lchild,*rchild; //左右孩子指针
}BiNode,*BiTree;
//BiNode普通的结点类型
//*BiTree指向有三个成员的这种结点类型的指针

在n个结点的二叉链表中，有n + 1个空指针域
空指针数目 = 2n - (n - 1) = n + 1
(总指针域个数 - 孩子结点个数 = 空指针域个数)

三叉链表(找双亲方便)

1
2
3
4
typedef struct TriTNode{
	TElemType data;
	struct TriTNode *lchild,*parent,*rchild;
}TriTNode,*TriTree;

3.遍历二叉树

先左子树 后右子树(前中后区分根结点访问顺序)

  1. 先序遍历：根节点 -> 左子树 -> 右子树(根左右)
  2. 中序遍历：左子树 -> 根节点 -> 右子树(左根右)
  3. 后序遍历：左子树 -> 右子树 -> 根节点(左右根)
  4. 层次遍历：从根节点开始，按从上到下、从左到右的顺序访问每一个节点
    先序遍历的 递归方法
    1
    2
    3
    4
    5
    6
    7
    void PreOrderTraverse(BiTree *T){
    	if(T!=NULL){
    		printf("%d\t",T->data);
    		PreOrderTraverse(T->lchild);//递归遍历左子树
    		PreOrderTraverse(T->rchild);//递归遍历右子树
    	}
    }
    中序遍历的 递归方法
    1
    2
    3
    4
    5
    6
    7
    void InOrderTraverse(BiTree *T){
    	if(T!=NULL){
    		PreOrderTraverse(T->lchild);//递归遍历左子树
    		printf("%d\t",T->data);
    		PreOrderTraverse(T->rchild);//递归遍历右子树
    	}
    }
    后序遍历的 递归方法
    1
    2
    3
    4
    5
    6
    7
    void PostOrderTraverse(BiTree *T){
    	if(T!=NULL){
    		PreOrderTraverse(T->lchild);//递归遍历左子树
    		PreOrderTraverse(T->rchild);//递归遍历右子树
    		printf("%d\t",T->data);
    	}
    }
    从递归的角度看，这三种算法是完全相同的(访问路径是相同的)，只是访问的时机不同
    时间复杂度：O(n)
    中序 非递归算法
    栈
    基本思想：
    建立一个栈
    根结点进栈(先不访问)，遍历左子树
    根结点出栈，输出根结点，遍历右子树 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    Status InOrderTraverse(BiTree T){
    	BiTree p;
    	InitStack(S);
    	p = T; //p最初指向根节点

    	//继续循环的条件：p不为空 or 栈中有元素
    	while( p || !StackEmpty(S) ){ 
    		if(p){ 
    			//当前根节点入栈，栈中暂存未访问的根节点
    			Push(S,p);
    			p = p->lchild;
    		}else{ //p为空，无左子树
    			Pop(S,q); //弹出栈顶根节点，q指向它
    			printf("%c",q->data);
    			p = q->rchild;  //p指向右孩子
    		}
    	}
    	return OK;
    }
    二叉树的层次遍历
    算法设计思路：使用一个队列(顺序循环队列)
    (1)将根节点进队；
    (2)循环的条件：队列不为空
    从队列中出列一个结点(第一个)，访问它
    若它有左右孩子结点，则将结点进队
    (3)出列的顺序即为层次遍历顺序 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    //队列类型定义
    typedef struct{
    	BTNode data[MaxSize]; //存放队中元素的数组
    	int front,rear;  //队头和队尾指针
    }SqQueue; //顺序循环队列类型

    void LevelOrder(BTNode *b){
    	BTNode *p;
    	SqQueue *qu;
    	InitQueue(qu); //初始化队列
    	enQueue(qu,b); //根结点指针进入队列
    	while(!QueueEmpty(qu)){
    		deQueue(qu,p);   //出队结点p(队列的首结点出栈)
    		printf("%c",p->data); //访问结点p
    		if(p->lchild != NULL) enQueue(qu,p->lchild);
    		if(p->rchild != NULL) enQueue(qu,p->rchild);
    	}
    }

1. —— 二叉树的建立

补全二叉树.png
对上图所示二叉树，按照下列顺序读入字符：
ABC##DE#G##F### 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Status CreateBiTree(BiTree &T){
	scanf(&ch);
	if(ch == "#"){
		T = NULL;
	}else{
		//内存中分配结点空间
		if(!(T = (BiTNode *)malloc(sizeof(BiTNode)))){
			exit(OVERFLOW);
		}
		T->data = ch; //生成结点
		CreateBiTree(T->lchild); //构造左子树
		CreateBiTree(T->rchild); //构造右子树
	}
	return OK;
}

2. —— 复制二叉树

将一颗树，复制到一颗新树上

1
2
3
4
5
6
7
8
9
10
11
12
13
int Copy(BiTree T,BiTree &NewT){
	if(T==NULL){
		NewT = NULL;
		return 0;
	}else{
		//复制根节点
		NewT = newBiTNode;
		NewT->data = T->data;

		Copy(T->lchild,NewT->lchild);
		Copy(T->rchild,NewT->rchild);
	}
}

3. —— 计算二叉树深度

1
2
3
4
5
6
7
8
9
10
11
12
13
int Depth(BiTree T){
	if(T == NULL){
		return 0;
	}else{
		l = Depth(T->lchild);
		r = Depth(T->rchild);
		if(l>r){
			return l + 1;
		}else{
			return r + 1;
		}
	}
}

4. —— 计算二叉树结点总数

1
2
3
4
5
6
7
8
int NodeCount(BiTree T){
	if(T == NULL){
		return 0;
	}else{
		return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
	}

}

5. —— 计算二叉树叶子结点数

1
2
3
4
5
6
7
8
9
int LeadCount(BiTree T){
	if(T == NULL) return 0;

	if(T->lchild == NULL && T->rchild == NULL){
		return 1;
	}else{
		return LeadCount(T->lchild) + LeadCount(T->rchild);
	}
}

4.线索二叉树

利用二叉链表中的空指针域(n+1)：
如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱
如果某个结点的右孩子为空，则将空的右孩子指针域改为指向其后继
——这种改变指向的指针 称为 “线索”
(按照某一遍历顺序的前驱和后继)
线索二叉树例题.png

为了区分lchild和rchild指针到底是指向孩子的指针还是指向前驱或者后继的指针，对二叉链表中每个结点增设两个标志域 ltag 和 rtag，并约定：
ltag = 0，lchild指向该结点的左孩子
ltag = 1，lchild指向该结点的前驱
rtag = 0，rchild指向该结点的右孩子
rtag = 0，rchild指向该结点的后继

结点的结构：

1
2
3
4
5
typedef struct BiThrNode{
	int data;
	int ltag,rtag;
	struct BiThrNode *lchild,rchild;
}BiThrNode,*BiThrThree;

为了避免悬空态，增设一个头结点(让悬空的指针指向头结点)
头结点：
①ltag = 0，lchild指向根节点，
②rchild = 1，rchild指向遍历序列中最后一个结点
遍历序列中第一个结点的lchild域和最后一个结点的rchild域都指向头结点

5.树和森林

(1)树的存储结构

1.双亲表示法
双亲表示法1.png 双亲表示法2.png
数据域：存放结点本身信息
双亲域：指示本结点的双亲结点在数组中的位置
找双亲容易，找孩子难
结点的类型定义
结点结构：「data | parent」

1
2
3
4
typedef struct PTNode{
	TElemType data;
	int parent; //双亲位置域
}PTNode;

树结构

1
2
3
4
5
#define MAX_TREE SIZE 100
typedef struct{
	PTNode node[MAX_TREE SIZE];
	int r,n; //根节点的位置和结点个数
}PTree

2.孩子链表
孩子链表.png
找孩子容易，找双亲难

孩子结点结构：「child | next」 

1
2
3
4
typedef struct CTNode{
	int child;
	struct CTNode *next;
}*ChildPtr;

双亲结点结构：「data | firstchild」

1
2
3
4
typedef srtuct{
	TElem Type data;
	ChildPtr firstchild; //孩子链表头指针
}CTBox;

树结构

1
2
3
4
typedef struct{
	CTBox nodes[MAX_TREE_SIZE];
	int n,r;//根节点的位置和结点个数
}

3.带双亲的孩子链表
带双亲的孩子链表.png

4.孩子兄弟表示法(二叉树表示法/二叉链表表示法)
孩子兄弟表示法.png
二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点

1
2
3
4
typedef struct CSNode{
	ElemType data;
	struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;

(2)树和二叉树的转换

二叉树和数都可以用二叉链表表示：
二叉树：两个指针域分别指向左孩子&&右孩子
树：第一个孩子&&下一个兄弟
树 → 二叉树
树→二叉树.png
兄弟相连留长子(以树的根结点为轴心，将树顺时针转45°)
二叉树 → 树
二叉树→树.png
左孩右右连双亲，去掉原来右孩线(调整到按层次排列)

(3)森林转换成二叉树

森林 → 二叉树
森林→二叉树.png
树变二叉根相连
二叉树 → 森林
二叉树→森林.png
去掉全部右孩线，孤立二叉再还原

(4)树与森林的遍历

  1. 树的遍历(三种方式)
    ①先根遍历：先根后子树
    ②后根遍历：先子树后跟
    ③层次遍历：自上而下，自左至右
  2. 森林的遍历
    将森林看作由三部分构成：
    森林看作三部分.png
    ①森林中第一颗树的根结点；
    ②森林中第一颗树的子树森林；
    ③森林中其它树构成的森林。
    有先序遍历、中序遍历

6.哈夫曼树(最优二叉树)及其应用

(1)哈夫曼树的基本概念

路径：从树中一个结点到另一个结点之间的 分支 构成这两个结点间的路径。
结点的路径长度：两结点间路径上的分支树。
树的路径长度：从树根到每个结点的路径长度之和。记作：TL
     结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树。

权：将树中结点赋给一个有着某种含义的数值，这个数值称为该结点的权。
结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积。路径长度×权
树的带权路径长度：树中所有叶子结点的带权路径长度之和。
     记作：WPL = ∑(k=1到n)wl (Weighted Path Length)

哈夫曼树：最优二树(带权路径长度WPL最短的二叉数)
     “带权长度最短”是在“度相同”的树中比较而得的结果，因此有最优二叉树、最优三叉树
     ①满二叉树不一定是哈夫曼树
     ②哈夫曼树中权越大的叶子离根越近
     ③具有相同带权结点的哈夫曼树不唯一

(2)哈夫曼树的构造算法

哈夫曼算法(构造哈夫曼树的方法)
①构造森林全是根
②选用两小造新树(新树的根为两小之和)
③删除两小添新人
④重复②③直到森林只有一颗树为止
构造哈夫曼树的例子.png
总结：
初始有n颗二叉树，要经过n - 1次合并最终形成哈夫曼树
经过n - 1次合并产生n - 1个新结点，且这n - 1个新结点都是具有两个孩子的分支结点
哈夫曼树中共有n+n-1 = 2n-1个结点，且所有分支结点的度都不为1

HT[i].lch = s1;
顺序存储结构 —— 一维结构数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//构造哈夫曼树 ——哈夫曼算法
void CreateHuffmanTree(HuffmanTree HT,int n){ //n个初始元素
	if(n <= 1) return;
	m = 2*n - 1; //数组共2*n - 1个元素
	HT = new HTNode[m + 1]; //0号单元未用，HT[m]表示顶层根结点
	for(i = 1; i <= m; ++i){
		//将2n - 1个元素的lch、rch、patent初始值设置为0
		HT[i].lch = 0;
		HT[i].rch = 0;
		HT[i].parent = 0;
	}
	//输入前n个元素的weight值
	for(i = 1; i <= n; ++i){
		cin >> HT[i].weight;
	}


	//初始化结束，下面开始建立哈夫曼树
	for(i = n+1; i <= m;i++){ //合并产生n - 1个结点 —— 构造Huffman树
		//在HT[k](1<=k<=i-1)中选择两个其双亲域为0，且权值最小的结点，并返回它们在HT中的序号s1和s2
		Select(HT,i-1,s1,s2); 

		//从F中删除s1,s2(两者已经有双亲了，不再是独立的根结点了)
		HT[s1].parent = i;
		HT[s2].parent = i;

		//s1,s2分别作为i的左右孩子
		HT[i].lch = s1;
		HT[i].rch = s2;

		//i的权值为左右孩子权值之和
		HT[i].weight = HT[s1].weight + HT[s2].weight;
	}
}

(3)哈夫曼编码

哈夫曼编码可以使电文总长最短

设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀 —— 这种编码称做前缀编码

方法：

  1. **统计每个字符出现的概率(概率越大，要求编码越短)
  2. 将每个字符的概率值作为权值，构造哈’夫曼树
  3. 结点的左分支标0，右分支标1**
         把每个叶子的路径上的标号连接起来，作为该叶子代表的字符的编码

哈夫曼编码例子.png

(4)哈夫曼编码的算法实现

哈夫曼编码的实现过程.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
void CreateHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n){
	//分配n个字符编码的头指针矢量
	//HC是一个指针数组，有n个元素，每一个都是一个指针，指向一个字符数组
	//HC每一个元素都是一个字符数组的地址
	HC = new char *[n + 1]; 
	cd = new char [n]; //分配临时存放编码的动态数组空间
	cd[n - 1] = '\0'; //编码结束符

	//逐个字符求哈夫曼编码
	for(i = 1 ; i <= n; ++i){
		start = n-1;
		c = i;
		f = HT[i].patent;
		while(f != 0){ //从叶子结点开始向上回溯，直到根结点
			--start; //回溯一次start指向前一个位置
			if(HT[f].lchild == c){
				cd[start] = '0'; //结点c是f的左孩子，则生成代码0
			}else{
				cd[start] = '1'; //结点c是f的右孩子，则生成代码1
			}
		}

		//为第i个字符串编码分配空间
		HC[i] = new char[n - start];
		//将求得的编码从临时空间cd复制到HC的当前行中
		strcpy(HC[i],&cd[start]);
	}

	//释放临时空间
	delete cd;
}

(5)文件的编码和解码

  1. 编码
    ①输入各字符及其权值
    ②构造哈夫曼树 —— HT[i]
    ③进行哈夫曼编码 —— HC[i]
    ④查HC[i],得到各个字符的哈夫曼编码

  2. 解码
    ①构造哈夫曼树
    ②依次读入二进制码
    ③读入0，则走左孩子；读入1则走右孩子
    ④一旦到达某叶子时，即可译出字符
    ⑤然后再从根出发继续译码，直到结束

Donate
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.

扫一扫，分享到微信

微信分享二维码
  • Copyrights © 2023-2025 Annie
  • Visitors: | Views:

嘿嘿 请我吃小蛋糕吧~

支付宝
微信