devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C语言数据结构之树超全详解_c语言树

作者：知新_RL | 2024-06-04 01:38:39

赞

踩

c语言树

目录


因为时间原因里面还有一些代码没有完善，有时间我会补充上去。

基础知识

二叉树的一些基本概念

在这里插入图片描述
度：结点拥有的子树数称为该结点的度,结点B的结点为2
分支结点（非终端结点）： 度不为0的结点
叶子（终端结点）：度为0的结点
树的度：树内各结点的度的最大值，上图中D结点的度最大为3，所以这个树的度为3
孩子：结点的子树的根，该结点称为孩子的双亲
兄弟：同一个双亲的孩子之间互称兄弟
祖先：从根到该节点所经分支的所有结点
子孙：以某结点为根的子树中任一结点都是该结点的子孙
堂兄弟：双亲在同一层的结点互为堂兄弟
结点的层次：从跟开始定义，根为第一层，根的孩子为第二层
若某结点在第n层，其子树的根就在(n+1)层
树的深度（高度）：树中结点的最大层次
结点的深度，高度，和层次

  • 结点的层次从树根开始定义，根节点为第一层（有的教材定义为第0层），根节点的子节点为第二层
  • 结点的深度：从根节点开始自顶向下逐层累加到该结点
  • 结点的高度：从叶子结点开始自低向上逐层累加到该结点

路径和路径长度：

  • 树中两个结点之间的路径是由这两个结点之间所经历的结点序列构成的，
  • 而路径长度是路径上所经历的边的个数

森林：m(m>=0)棵互不相交的树的集合

树的性质

  1. 书中的结点数等于所有结点的度数加1
  2. 度为m的书中第i层上之多由m的(i-1)次方个结点
  3. 高度为h的m叉树至多有
  4. 具有n个结点的m叉树的最小高度wei

二叉树的一些基本性质

性质 1 ：在二叉树的第 i 层上至多有2i-1 个结点(i ≥ 1)。
性质 2 ：深度为 k 的二叉树上至多含 2k-1 个结点（k≥1）。
性质 3 ：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。
两类特殊的二叉树：
满二叉树：指的是深度为k且含有2k-1个结点的二叉树。（左图）
完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。（右图）

在这里插入图片描述

操作部分

二叉树的存储结构

上面啰嗦了这么多，下面开始进入正题啦，下面介绍二叉树的几种存储结构

1.顺序存储结构

在这里插入图片描述

#define MAX_TREE_SIZE 100
typedef TElemType SqBiTREE[MAX_TREE_SIZE];
SqBiTree bt;

  • 1
  • 2
  • 3

顺序存储结构仅适用于完全二叉树

2.链式存储结构

(1). 二叉链表
二叉树链式存储的结点结构
在这里插入图片描述

typedef struct BiTNode { // 结点结构
    TElemType      data;
    struct BiTNode  *lchild, *rchild;// 左右孩子指针
} BiTNode, *BiTree;

  • 1
  • 2
  • 3
  • 4

在这里插入图片描述
看一个简单的创建并遍历二叉树的程序：

# include <stdio.h>
# include <stdlib.h>
#define TElemType int

/*二叉树的结点结构*/
typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

/*创建二叉树*/
BiTree CreateBiTree(){

	BiTree T;

	/*分配存储空间*/
	T = (BiTNode *)malloc(sizeof(BiTNode));
	T->lchild = (BiTNode *)malloc(sizeof(BiTNode));
	T->rchild = (BiTNode *)malloc(sizeof(BiTNode));
	T->lchild->lchild= (BiTNode*)malloc(sizeof(BiTNode));

	/*赋值*/
	T->data = 1;
	T->lchild->data = 2;
	T->rchild->data = 3;
	T->lchild->lchild->data = 4;

	/*让结点的指针域为空*/
	T->lchild->lchild->lchild = NULL;
	T->lchild->lchild->rchild = NULL;
	T->lchild->rchild = NULL;
	T->rchild->lchild = NULL;
	T->rchild->rchild = NULL;
	return T;
}	

int main(){
	/*创建二叉树*/
	BiTree Tree = CreateBiTree();
	printf("%d",Tree->lchild->lchild->data);
	return 0;
}

  • 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
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42

输出结果为：4
这个二叉树的结构如下：
在这里插入图片描述

但是实际应用中，不可能在创建的时候手动给二叉树赋值，一般都是动态加入的。
代码如下：

#include <stdio.h>
#include <stdlib.h>
#define OVERFLOW -2

typedef char TElemType;

/*二叉树的结点结构*/
typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

/*创建二叉树*/
BiTree CreateBiTree(BiTree T){
	/*分配存储空间*/
	T = (BiTNode *)malloc(sizeof(BiTNode));

	char ch;
	scanf("%c",&ch);
	//如果输入为空，则二叉树是空树
	if(ch=='#'){
		T = NULL;
	}else{
		if(!T){
			printf("分配存储空间失败！");
			exit(OVERFLOW);
		}
		T->data = ch;//先输入根结点
		T->lchild = CreateBiTree(T->lchild);//递归生成左子树
		T->rchild = CreateBiTree(T->rchild);//递归生成右子树
	}
	return T;
}	


int main(){
	/*创建二叉树*/
	BiTree T;
	printf("请输入二叉树中的元素 # 表示空\n");
	BiTree Tree = CreateBiTree(T);
	return 0;
}

  • 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
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42

需要注意的是递归创建左右子树的时的代码：

T->lchild = CreateBiTree(T->lchild);//递归生成左子树
T->rchild = CreateBiTree(T->rchild);//递归生成右子树

  • 1
  • 2

输入：124##5##3##
二叉树就创建成功了，遍历二叉树会在后面介绍到
在这里插入图片描述
创建的二叉树为：
在这里插入图片描述

(2)．三叉链表
由二叉链表的结点结构可知，想要找到结点的双亲是比较困难的，为了找到结点的双亲，可以在结点结构中增加一个指向双亲的指针域。如下所示
在这里插入图片描述
由这种结点结构所构成的二叉树的存储结构分别称为三叉链表。
在这里插入图片描述

typedef struct TriTNode { // 结点结构
  TElemType       data;
  struct TriTNode  *lchild, *rchild;// 左右孩子指针
  struct TriTNode  *parent;  //双亲指针 
} TriTNode, *TriTree;


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

(3)．双亲链表
结点结构：
在这里插入图片描述

typedef struct BPTNode { // 结点结构
     TElemType  data;
     int  *parent;     // 指向双亲的指针
     char  LRTag;    // 左、右孩子标志域
} BPTNode
typedef struct BPTree{ // 树结构
     BPTNode nodes[MAX_TREE_SIZE];
     int  num_node;     // 结点数目
     int  root;                // 根结点的位置
} BPTree

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

(4).线索链表

使用二叉链表创建二叉树：

BiTree CreateBiTree(BiTNode *T)
{
 char c;
 scanf("%c",&c);
 if(c==' '){
  T=NULL;
 } else{
  T=(BiTNode *)malloc(sizeof(BiTNode));
  T->data=c;
  T->lchild=CreateBiTree(T->lchild);
  T->rchild=CreateBiTree(T->rchild);
 }
 return T;
}

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

3.线索二叉树

当以二叉链表作为存储结构时，无法直接得到在任一序列中结点的前驱和后继信息，这种信息只有在遍历的动态过程中才能得到。
如何保存这种在遍历过程中得到的信息呢？
可以做如下规定：
若结点有左子树，则其lchild域 指示其左孩子，否则令 lchild域 指示其前驱；
若结点有右孩子，则其rchild域 指示其右孩子，否则令 rchild域 指示其后继。
为避免混淆，在结点结构上增加两个标志域
在这里插入图片描述
LTag=

  • 0 lchild域指示结点的左孩子
  • 1 lchild域指示结点的前驱

RTag=

  • 0 rchild域指示结点的左孩子
  • 1 rchild域指示结点的前驱
    以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索，加上线索的二叉树称之为线索二叉树
    线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化
    在线索树上进行遍历，只需要先找到 序列中的第一个结点，然后依次找结点后继直到其后继为空时即止。
    看一个中序线索链表

在这里插入图片描述
注意： a 才是根节点，根节点是模仿线性表的存储结构，在二叉树的线索链表上也添加一个头节点，并令其lchild 域的指针指向二叉树的根节点，其rchild 域的指针指向中序遍历时访问的最后一个结点，
并使中序遍历序列中第一个结点的lchild 域指针，和最后一个结点的rchild域指针均指向头节点。
好比为二叉树建立了一个双向线索链表，既可从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历

前驱与后继

可以看到，树中所有叶子节点的右链是线索，右链域直接指示了结点的后继。

但是树中非终端结点的右链均为指针，怎么能得到后继的信息呢？

在中序线索链表中：
根据中序遍历的规律可知，结点的后继应该是遍历其右子树时访问的第一个结点，即右子树最左下的结点，

如在找b 的后继时，先沿右指针找到其右子树的根节点 e ，然后顺着 e 的左指针往下找一直找到左标志为 1 的结点，即为 b 的后继（图中e下面只有一层，如果是多层，也是一直往左找），所以可以看到图中g 的前驱为 b ，

如何找结点的前驱呢？
若其左标志为1，则左链为线索，指示其前驱。如图中 g 的前驱是b，c的前驱是a
若其左标志为0，则遍历左子树时最后访问的一个结点（左子树的右下角）为其前驱
如上图中，a 的前驱是h，因为a左子树最后访问的结点是h。

遍历这个中序线索链表如下紫色线条
在这里插入图片描述
在后序线索树中找结点的后继
可分三种情况

  1. 二叉树的根后继为空（后序遍历最后访问根）
  2. 若结点x 是双亲的右孩子， 或者是双亲的左孩子(当x为左孩子时双亲没有右子树)，其后继为双亲结点
  3. 若结点x 是双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历列出的第一个结点。
    在这里插入图片描述
线索二叉树的存储表示

二叉树的二叉线索存储表示：

typedef int TElemType;
typedef int PointerTag;
typedef enum PointerTag{ Link, Thread};// Link == 0: 指针，Thread == 1: 线索

/*结点的定义*/
typedef struct BiThrNode{
	TElemType data;            //数据域
	BiThrNode *lchild, *rchild;//结点的左右孩子
	PointerTag LTag,RTag;      //标志域
}BiThrNode, *BiThrTree; 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

要获得线索二叉树，首先创建一个普通二叉链表树：

/*创建二叉树*/
BiThrTree CreateBiThrTree(BiThrTree BT){
	BT = (BiThrNode *)malloc(sizeof(BiThrNode));//分配存储空间
	if(!BT){
		printf("分配存储空间失败\n");
	}
	TElemType ch;

	scanf("%c",&ch);
	if(ch =='#'){
		BT = NULL;
	}else{
		BT->data = ch;
		BT->lchild = CreateBiThrTree(BT->lchild);
		BT->rchild = CreateBiThrTree(BT->rchild);
	}
	return BT;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

然后再在遍历二叉树的时候将二叉树线索化，即将二叉链表中的控制很改为指向前驱或者后继的线索。

/*中序遍历进行线索化*/
void InThreading(BiThrTree T){
	BiThrTree preT;
	preT = (BiThrNode *)malloc(sizeof(BiThrNode));
	if(T){
		InThreading(T->lchild);//左子树线索化

		/*根节点线索化*/
		if(!T->lchild){//如果跟结点的左孩子为空
			T->LTag = Thread;//结点的左标志为1，指向前驱
			T->lchild = preT;//结点的左指针域指向前驱
		}
		if(!preT->rchild){//如果双亲结点没有右孩子
			T->RTag = Thread;//结点的右标志为1，指向后继
			preT->rchild = T;//结点的双亲结点的后继指向该结点
		}
		preT = T;//preT指向T 的前驱

		InThreading(T->rchild);
	}
}


/*将中序遍历二叉树并将其线索化*/
BiThrTree InOrderThreading(BiThrTree T){
	BiThrTree preT;
	
	preT = (BiThrNode *)malloc(sizeof(BiThrNode));

	BiThrTree Thr;//指向头节点
	if(!(Thr = (BiThrNode *)malloc(sizeof(BiThrNode)))) exit(-2);//分配存储空间
	//建立头节点
	Thr->LTag = Link;//左标志为0，指向左孩子
	Thr->RTag = Thread;//右标志为1，指向后继
	Thr->rchild = Thr;//右指针回指
	if(!T) Thr->lchild = Thr;//若二叉树为空，左指针回指
	else{
		Thr->lchild = T;//头节点的左孩子是根节点
		preT = Thr;
		InThreading(T);//中序遍历进行中序线索化
		preT->rchild = Thr;
		preT->RTag = Thread;//最后一个结点线索化
		Thr->rchild = preT;//
	}

	return T;
}

  • 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
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47

二叉树的遍历

遍历是二叉树各种操作的基础，可以在遍历过程中对节点进行各种操作。

顺着某一条搜索路径巡防二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。

如果是线性表之类的线性结构而言，遍历很简单，因为只有一条搜索路径。但是二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按照什么样的搜索路径遍历的问题。
二叉树由以下三个部分组成。根节点，左子树，右子树
在这里插入图片描述
由二叉树的这种结构，一般遍历时都是先遍历左子树，再遍历右子树。
所以有三种方法（这三种方法都是二叉树不为空的前提下进行的）：

先（根）序遍历

  • 访问根节点
  • 先序遍历左子树
  • 先序遍历右子树
    在这里插入图片描述
    看一下遍历的代码：
#include <stdio.h>
#include <stdlib.h>
#define OVERFLOW -2

typedef char TElemType;

/*二叉树的结点结构*/
typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

/*创建二叉树*/
BiTree CreateBiTree(BiTree T){
	/*分配存储空间*/
	T = (BiTNode *)malloc(sizeof(BiTNode));

	char ch;
	scanf("%c",&ch);
	//如果输入为空，则二叉树是空树
	if(ch=='#'){
		T = NULL;
	}else{
		if(!T){
			printf("分配存储空间失败！");
			exit(OVERFLOW);
		}
		T->data = ch;//先输入根结点
		T->lchild = CreateBiTree(T->lchild);//递归生成左子树
		T->rchild = CreateBiTree(T->rchild);//递归生成右子树
	}
	return T;
}	

void PrintElement(BiTree T){
	printf("%c\n",T->data);
}

/*先序遍历二叉树*/
void PreOrderTraverse(BiTree T){
	if(T){
	
		PrintElement(T);//先访问根结点
		PreOrderTraverse(T->lchild);//递归访问左子树
		PreOrderTraverse(T->rchild);//递归访问右子树
	}
	return;//如果树为空，返回上一次
}

int main(){
	/*创建二叉树*/
	BiTree T;
	printf("请输入二叉树中的元素 # 表示空\n");
	BiTree Tree = CreateBiTree(T);

	/*先序遍历二叉树*/
	printf("二叉树为:\n");
	PreOrderTraverse(Tree);
	return 0;
}

  • 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
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60

先序遍历结果：
在这里插入图片描述
二叉树的结构如下，# 代表这个节点为空：
在这里插入图片描述

中（根）序遍历

  • 中序遍历左子树
  • 访问根节点
  • 中序遍历右子树

在这里插入图片描述

原理和先序遍历一样：

......

void PrintElement(BiTree T){
	printf("%c\n",T->data);
}

/*中序遍历二叉树*/
void LastOrderTraverse(BiTree T){
	if(T){
	
		LastOrderTraverse(T->lchild);//递归访问左子树
		PrintElement(T);
		LastOrderTraverse(T->rchild);//递归访问右子树
	}
	return;//如果树为空，返回上一次
}

......

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

在这里插入图片描述

后（根）序遍历

  • 后序遍历左子树
  • 后序遍历右子树
  • 访问根节点

在这里插入图片描述

void PrintElement(BiTree T){
	printf("%c\n",T->data);
}

/*后序遍历二叉树*/
void PreOrderTraverse(BiTree T){
	if(T){
	
		PreOrderTraverse(T->lchild);//递归访问左子树
		
		PreOrderTraverse(T->rchild);//递归访问右子树
		PrintElement(T);
	}
	return;//如果树为空，返回上一次
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

在这里插入图片描述
看一个简单的例子：
在这里插入图片描述

层次遍历

按照二叉树中的层次从上到下，从左到右依次遍历每层中的结点
在这里插入图片描述
具体的实现思路是：
通过使用队列的数据结构，从树的根结点开始，依次将其左孩子和右孩子入队。而后每次队列中一个结点出队，都将其左孩子和右孩子入队，直到树中所有结点都出队，出队结点的先后顺序就是层次遍历的最终结果。

二叉树的相关操作

求二叉树的深度


/*求二叉树深度*/
int TreeDepth(BiTree T){
	int treedepth;//二叉树深度
	int ldepth;//左子树深度
	int rdepth;//右子树深度
	if(!T){
		treedepth = 0;
	}else{
		ldepth = TreeDepth(T->lchild);
		rdepth = TreeDepth(T->rchild);
		if(ldepth>rdepth){
			treedepth = ldepth + 1;
		}else{
			treedepth = rdepth + 1;
		}
	}
	return treedepth;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

统计二叉树中叶子结点的个数

待添加

复制二叉树

待添加

树和森林

树的存储结构

双亲表示法

假设一组连续空间存储树的结点，同时在每一个结点中附设一个指示器指示其双亲结点在链表中的位置，

#define MAX_TREE_SIZE 100
//结点结构
typedef struct PTNode{
	TElemType data;//数据域
	int parent;  //双亲位置域
}PTNode;
//树结构
typedef struct {
	PTNode nodes[MAX_TREE_SIZE];
	int r,n;//树的位置和节点数
}PTree;

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

这种存储结构利用了除了根节点外每个结点只有一个双亲的性质，PARENT(T,x)操作可以在常量时间内实现，反复调用PARENT 操作，直到遇见无双亲的结点时，便找到了树的根，这就是ROOT(x)操作的执行方法，但是在这种表示法中，求结点的孩子时需要遍历整个结构。
在这里插入图片描述

孩子表示法

由于树中每个结点可能会有多课子树，则可以使用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根节点，此时链表中的结点可以有如下两种结点格式
在这里插入图片描述
采用上面这种结点格式，则多重链表中的结点是同构的，其中d 为树的度，由于树中很多结点的度小于d，所以链表中很多空链域，空间较浪费，在一颗有n 个结点的，度为k 的树中，必有n(k-1)+1 个空链域。
在这里插入图片描述
采用这种结点格式，多重链表中的结点是不同构的，其中d 为结点的度，degree 域的值同d，此时虽然节约存储空间，但是操作不方便。

还有一种方法是将每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作为存储结构，n个结点有n个孩子链表，叶子的孩子链表为空表。而n个头指针又组成一个线性表，为了便于查找，可采用顺序存储结构，如下：

typedef struct CTNode{
	int child;
	struct CTNode *next;
}*ChildPtr;
typedef struct{
	TElemType data;
	ChildPtr firstchild;//孩子链表头指针
}CTBox;
typedef struct {
	CTBox nodes[MAX_TREE_SIZE];
	int n,r;//结点数和根的位置
}CTree;

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

森林和二叉树的转换

由于二叉树和树都可以用二叉链表作为存储结构，则以二叉链表作为媒介可以导出树与二叉树之间的一个对应关系。
也就是说，给定一棵树，可以找到唯一的一颗二叉树与之对应，从物理结构来看，他们的二叉链表是相同的，只是解释不同而已

树转换为二叉树

下面是一个树和二叉树的对应关系示例
在这里插入图片描述
树转换为二叉树的过程如下
在这里插入图片描述

从树的二叉链表表示的定义可知，任何一颗和树对应的二叉树，其右子树必定为空。
若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可以到处森林和二叉树的对应关系。

一一对应的关系导致森林或树或二叉树可以相互转换，其形式定义如下；

二叉树转换为树

  1. 加线。若某结点的左孩子结点存在，则将这个孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点……，反正就是左孩子的n个右孩子结点都作为此结点的孩子。将该结点与这些右孩子结点用线连接起来。
  2. 去线。删除原二叉树中所有节点与右孩子结点的连线。
  3. 层次调整。使之结构层次分明。
    在这里插入图片描述

森林转换成二叉树

方法一
如果F= {T1,T2,····,Tm}是森林，可按如下规则转换成一棵二叉树，B = (root, LB, RB)。

  1. 若F为空，即m = 0，B为空树
  2. 若F非空，即m != 0，
    则B的根 root 几位森林中第一棵树的根 ROOT(T1)
    B的左子树LB是从T1的根结点的子树森林 F1 = {T1， T12， T1m1}转换而成的二叉树，
    B的右子树RB是从森林F` = {T2, T3, ······,Tm}转换而成的二叉树

方法二
1.把每棵树转换为二叉树（参考上述方法）。
2.第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。在这里插入图片描述

二叉树转换成森林

方法一
如果B=(root,LB,RB) 是一颗二叉树，可按如下规则转换成森林

  1. 若B空，则F空
  2. 若B非空，则F中第一棵树T1 的根ROOT(T1)即为二叉树B的根root，T1 中根结点的子树森林F1是由B的左子树LB转换而成的森林，F中除T1之外其余树组成的森林 F` ={T2,T3,·····,Tm}是由B的右子树RB转换而成的森林。

方法二
判断一棵二叉树能够转换成一棵树还是森林，标准很简单，只要看这棵树的根结点有没有右孩子，有的话就是森林，没有的话就是一棵树。

将二叉树转换为森林的步骤如下：

  1. 从根结点开始，若右孩子存在，则将其与右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除……直到所有右孩子的连线都删除为止，得到分离后的二叉树。

  2. 将每棵分离后的二叉树转换为树即可。
    在这里插入图片描述

树和森林的遍历

树的遍历

由树的结构可以引出两种次序遍历树的方法，
一种是先根（次序）遍历树：先访问根结点，再依次先根遍历根的每棵子树；
另一种是后根（次序）遍历树：先依次后根遍历每棵子树，然后访问根结点。
这里没有中根遍历树，因为二叉树的根结点只有左子树和右子树两棵树，而树的根结点可能有多棵树。
在这里插入图片描述

森林的遍历

森林和树一样，也有两种遍历方法

  1. 先序遍历森林
    若森林非空，可以按照下述规则遍历：

    1. 访问森林中第一棵树的根结点
    2. 先序遍历第一棵树中根结点的子树森林
    3. 先序遍历除去第一棵树之后剩余的树构成的森林

  2. 中序遍历森林
    若森林非空，按照如下规则遍历

    1. 中序遍历森林中第一棵树的根结点的子树森林
    2. 访问第一棵树的根结点
    3. 中序遍历除去第一棵树之后剩余的树构成的森林
      在这里插入图片描述

当森林转换成二叉树时，其第一颗树的子树森林转换成左子树，剩余树的森林转换成右子树，则上述森林的先序和中序遍历即为其对应的二叉树的先序和中序遍历。
由此可见，当以二叉链表作树的存储结构时，树的先根遍历和后根遍历可借用二叉树的先序遍历和中序遍历算法实现。

赫夫曼树及其应用

赫夫曼树又称最优树，是一类带权路径长度最短的树

赫夫曼树

路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径
路径长度：路径上的分支数目称作路径长度。
树的路径长度：从树根到每一个结点的路径长度之和。完全二叉树就是路径长度最短的二叉树
结点的带权路径长度：该节点到树根之间的路径长度与结点上权的乘积
树的带权路径长度：树中所有叶子节点的带权路径长度之和 通常记作
在这里插入图片描述
在这里插入图片描述
赫夫曼树： 假设有n个权值(w1,w2…wn)，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi ，则其中带权路径长度WPL最小的二叉树称作最优二叉树或赫夫曼树。

赫夫曼树的特点
  1. 权值越大的叶子节点越靠近根结点，权值越小的叶子节点越远离根结点。
  2. 只有度为0（叶子节点）和度为2的（分支节点）的结点，不存在度为1 的结点

构造赫夫曼树/赫夫曼算法

赫夫曼最早给出了一个带有一般规律的算法，俗称赫夫曼算法。
基本思想：

  1. 初始化
    由给定的n 个权值{w1, w2,···,wn}构造n棵只有一个根结点的二叉树，从而得到一个二叉树集合F={T1, T2, ···, Tn}；
  2. 选取与合并
    在F 中选取根结点的权值最小的两棵二叉树分别作为左，右子树构造一棵新的二叉树，这棵新的二叉树的根节点的权值为其左右子树根节点的权值之和。
  3. 删除与加入
    在F中删除作为左右子树的两棵二叉树，并将新建立的二叉树加入到F 中；
  4. 重复2.3 步骤，当集合F中 只剩下一棵二叉树时，这棵二叉树就是哈夫曼树

演示一下：

  • 在这里插入图片描述
    重复上面步骤：
    在这里插入图片描述

赫夫曼树存储

存储结构

struct element{
	int weight;
	int lchild, rchild, parent;
};

  • 1
  • 2
  • 3
  • 4

设置一个数据huffTree[2n-1] 保存赫夫曼树中个点信息，数组元素的结点结构
在这里插入图片描述
weight : 权值域，保存该节点的权值
lchild: 指针域，结点的左孩子结点在数组中的下标
rchild: 指针域，结点的右孩子结点在数组中的下标
parent: 指针域，该节点的双亲结点在数组中的下标

为何存储数组的元素个数为 2n - 1

在这里插入图片描述
过程演示：
因为有四个元素，所以分配7个内存空间：

在这里插入图片描述
初始化：
每一棵树都是一个根节点，没有双亲也没有孩子
在这里插入图片描述
填入权值：

在这里插入图片描述
找到权值最小，且parent 为 -1 的两个结点合并，并修改其parent 值
在这里插入图片描述
修改k对应的左孩子右孩子对应的值：
在这里插入图片描述
继续循环，这里有两个5，扫描的时候会先选中前面的结点：
在这里插入图片描述
再循环：
在这里插入图片描述
伪代码：
在这里插入图片描述

在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/669820
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号