一篇搞懂树、二叉树和森林

程序、数据结构与算法,数据结构额外说明

收录于:17天前

树简介

树结构是n个具有一定关系的节点的集合。树结构是一种递归定义。树结构有一个且唯一的一个节点，称为根。每个节点都是一定关系的集合，是根节点的子树。

在这里插入图片描述

一棵树有且只有一个根节点，子树的节点彼此不相交。

节点：是树种一个独立的元素，指向字数的分支。

节点度：结点拥有字树的个数。

树的度数：树中结点度的最大值。

叶子：度为0的结点（没有字树的结点）也叫终端结点。

父母和孩子：结点的字树称为孩子，字树的根结点称为双亲。

等级：结点的层次从根节点开始且定义为第一层，层次累加。

树深度：树中结点最大的层次，称为树的深度或高度。

有序树和无序树：将树的结点按从左向右的有次序的树，称为有序树，否则反之。

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

二叉树

二叉树是一种特殊的树，定义为每个节点最多有两个子树，词树可分为左树和右树。

满二叉树

每个节点都有左词树和右词树。

完全二叉树

当数字 1-n 对应从上到下、从左到右的节点位置时，二叉树称为完全二叉树。

在这里插入图片描述

从树的定义可以看出，树是具有一定关系的集合。元素是分散的，存储空间必须是连续的。这类似于链表。

二叉树树的存储结构

由于二叉树的特殊性及其一定的规律性，二叉树比一般树更容易实现。

顺序存储结构

完全二叉树从上到下、从左到右与节点一一对应，因此可以存储在地址连续的空间中。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef struct{
    
	int elem[100];
	int length;
}ZxTree;

//初始化二叉树
ZxTree Init(){
    
	ZxTree tree;
	tree.elem[0] = 0;
	tree.length = 0;
	return tree;
}

//创建二叉树
void Create(ZxTree *tree,int e){
    
	if(tree->length == 0){
    
		tree->elem[0] = e;
		tree->length ++;
	}else{
    
		tree->elem[tree->length] = e;
		tree->length ++;
	}
}

//返回二叉树深度
int treeDepth(ZxTree tree){
    
	//因为是二叉树满足层次满足2^(k-1),所有结点满足2^k-1 
	// 实际二叉树结点 n 2^(k-1)<n<2^k-1 
	double tmp = log2(tree.length);
	int reault = floor(tmp+1.0);
	return reault;
}

//返回二叉树的根结点
int treeRoot(ZxTree tree){
    
	return tree.elem[0];
}

//查找
int treeQuery(ZxTree tree, int e){
    
	for(int i=0;i<tree.length;i++){
    
		if(tree.elem[i] == e){
    
			return i;
		}
	}
	return -1;
}

//修改
int treeModify(ZxTree *tree, int e,int x){
    
	for(int i=0;i<tree->length;i++){
    
		if(tree->elem[i] == e){
    
			tree->elem[i] = x;
			return 1;
		}
	}
	return -1;
}

//打印二叉树
void display(ZxTree tree){
    
	printf("打印二叉树：");
	for(int i=0;i<tree.length;i++){
    
		//TODO
		printf("%d",tree.elem[i]);
	}
	printf("\n");
}
int main(){
    
	ZxTree tree = Init();
	//printf("%d\n",tree.elem[0]);
	//printf("%d",tree.elem[1]+tree.elem[0]);
	Create(&tree,2);
	Create(&tree,3);
	Create(&tree,4);
	Create(&tree,5);
	display(tree);
	
	int a = treeDepth(tree);
	printf("%d",a);
	
	
}

完全二叉树由于其特殊的性质，满足2^(k-1)和(2^k)-1和有序性，从而能够计算出结点位置和其他属性。

对于非完全二叉树，没有顺序的限定，因此位置和计算公式没有绝对的关系，那么有些位置可能没有结点，在没有结点处用0代替。

在这里插入图片描述

链式存储结构

在二叉树中，每个节点需要指向左右子树，因此需要两个指针字段。如果需要记录父节点，还需要一个parent字段。

在这里插入图片描述
不论是那种方式都需要一个头结点记录根结点地址。

在这里插入图片描述
对于顺序存储的二叉树通过循环遍历即可，但是对于二叉链表，需要按照链表的逻辑依次遍历了。

对于单链表来说通过node->next != NULL即可，但是二叉树有其独特的结构。每个结点有三个域，数据域和左右子树域。三个域均可作为第一个访问的元素，那么就有6中访问形式。在完全二叉树中限定了左右子树不可颠倒，因此遍历也需要从左到右。因此访问顺序就变成了3种：根结点-----左字树-----右字树；左字树-------根结点------右字树；左字树------右字树------根结点。分别称为先序遍历，中序遍历，后序遍历（以根结点访问循序决定）。

#include<stdio.h>
#include<stdlib.h>

typedef int Elem;

typedef struct Node{
    
	Elem data;
	struct Node *Lnode, *Rnode;
}TreeNode,ZxTree;

中序遍历

头节点首先访问根节点，然后访问左子树，最后访问右子树。

#include<stdio.h>
#include<stdlib.h>

typedef int Elem;

typedef struct Node{
    
	Elem data;
	struct Node *Lnode, *Rnode;
}TreeNode,ZxTree;

//初始化
void Init(ZxTree *tree){
    
	tree = (TreeNode*)malloc(sizeof(TreeNode));  //初始化头结点
	tree->Lnode = NULL;
	tree->Rnode = NULL;     
}
//创建二叉树 
void Create(ZxTree *tree,Elem e){
     
	//根结点(二叉树本身地址为头结点，其左字树指向根结点)
	TreeNode *head = tree; 
	//新结点作为根结点
	TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));    
	node->data = e;              
	node->Lnode = NULL;
	node->Rnode = NULL;
	if(head->Lnode == NULL){
      //左字树为空左子树指向新结点，否则右子树指向新结点
		head->Lnode = node;
	}else{
    
		head->Rnode = node;
	}
}

//中序遍历
void display(ZxTree *tree){
    
	if(tree != NULL){
    
		printf("%d~",tree->data);
		display(tree->Lnode);
		//printf("%d-",tree->);
		display(tree->Rnode);
	}else{
    
		return;
	}
}
int main(){
    
	ZxTree tree;
	Init(&tree);
	Create(&tree,2);
	Create(&tree,4);
	Create(&tree,6);
	display(&tree);
	return 1;
}

在这里插入图片描述
可以看到上述代码只能创建一个如下所示的二叉树，不能再多一点。

在这里插入图片描述

上面创建二叉树的代码显然是错误的，但是中序遍历的递归方法确实是正确的。创建二叉树也需要遍历。

非递归实现

非递归实现遍历需要借助栈，因为遍历过程中节点会移动到叶子节点并且无法返回。需要使用栈来保存之前的节点并再次检索右词树。

在这里插入图片描述

创建二叉树并遍历它

由于链表的指针字段依次指向下一个地址，因此可以创建一个连续的链表。二叉链表中，由于左右词树的存在，无法批量创建。

int main(){
    	
	//创建所需二叉树
	TreeNode* nodeList[10];
	for(int i=0;i<6;i++){
    
		TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode)); 
		node->data = i+1;
		node->Lnode = NULL;
		node->Rnode = NULL;   
		nodeList[i] = node;
	}
	
	nodeList[0]->Lnode=nodeList[1];
	nodeList[0]->Rnode=nodeList[2];
	
	nodeList[1]->Lnode=nodeList[3];
	nodeList[1]->Rnode=nodeList[4];
	
	nodeList[2]->Lnode=nodeList[5];
	
	ZxTree tree;
	
	tree.Lnode = nodeList[0];
	
	display(&tree);
	
	
	return 1;
}

在这里插入图片描述

中序遍历

//递归中序遍历
//中序遍历
void display(ZxTree *tree){
    
	if(tree != NULL){
    
		display(tree->Lnode);
		printf("%d~",tree->data);
		display(tree->Rnode);
	}
}

中序遍历首先操作该节点的左子树，最后操作右子树，因此输出顺序为425163。

在这里插入图片描述

前序遍历

前序遍历首先访问节点，然后访问左子树，最后访问右子树。订单应为 124536。

void display(ZxTree *tree){
    
	if(tree != NULL){
    
		printf("%d~",tree->data);
		display(tree->Lnode);
		display(tree->Rnode);
	}
}

在这里插入图片描述

后序遍历

后序遍历首先访问左子树，然后访问右子树，最后访问节点。订单应为 452631。

void display(ZxTree *tree){
    
	if(tree != NULL){
    
		display(tree->Lnode);
		display(tree->Rnode);
		printf("%d~",tree->data);
	}
}

在这里插入图片描述

数据结构-二叉树遍历的四种类型：前序、中序、后序和层级（C语言版）文章以动画的形式解析了三种遍历方法的过程，生动形象，感谢作者大大。

树的存储结构

上面已经研究了二叉树的存储结构。接下来是普通的树。有没有一种特殊的树可以推广到普通的树上呢？链式存储结构中定义了左子树和右子树，但普通树上子树的数量是不确定的，所以不能使用链式结构。

家长代表

除了数据字段之外，每个节点还配备有父字段，以指示其父节点的位置。如下：

在这里插入图片描述

当多个节点组成一棵树时，parent 指向父节点的坐标。

在这里插入图片描述

对于 0 坐标 R，根节点坐标为 -1。 A、B、C分别是它们的子树，那么它们的父节点指向坐标0，即R的根节点。同样，D和E的父节点是A，指向A的坐标是1（顺序坐标本身决定子树的左右顺序）。

该实现方法将树的节点存储在连续的空间中，每个节点包含数据字段和父节点的位置。

//节点定义
typedef struct Node{
    
	int data;
	int parent;
}Node;

//树定义
typedef struct{
    
	Node Tree[100];
	int head,number;
}PTree;

//创建树

#include<stdio.h>
#include<stdlib.h>

/* 树的双亲表示法 */
//双亲表示法的结点
typedef struct PNode{
    
	char data;
	int parent;
} PNode;

//结点生成树
typedef struct{
    
	PNode node[10];    //树有10个结点
	int tree_length;    //树的长度
}PTree;

//树是具有一定关系的结点
//初始化
PTree* treeInit(char e){
    
	PNode *node = (PNode*)malloc(sizeof(PNode));
	node->data = e;
	node->parent = -1;
	PTree *tree = (PTree*)malloc(sizeof(PTree));
	(*tree).node[0] = *node;
	tree->tree_length = 0;
	return tree;
}
//创建树
void catrePTree(PTree *tree){
    
	//A结点
	PNode *node_a = (PNode*)malloc(sizeof(PNode));
	node_a->data = 'A';
	node_a->parent  = 0;
	tree->tree_length++;
	(tree->node)[tree->tree_length] = *node_a;
	
	//printf("%c",(tree->node)[1].data);
	//printf("%c,%d",tree->node->data,tree->node->parent);
	//printf("%c,%d",node_a->data,node_a->parent);
	
	
	//B结点
	PNode *node_b = (PNode*)malloc(sizeof(PNode));
	node_b->data = 'B';
	node_b->parent  = 0;
	tree->tree_length++;
	((*tree).node)[tree->tree_length] = *node_b;
	
	
	//C结点
	PNode *node_c = (PNode*)malloc(sizeof(PNode));
	node_c->data = 'C';
	node_c->parent  = 0;
	tree->tree_length++;
	((*tree).node)[tree->tree_length] = *node_c;
	
	
	//d结点
	PNode *node_d = (PNode*)malloc(sizeof(PNode));
	node_d->data = 'D';
	node_d->parent  = 1;
	tree->tree_length ++;
	(*tree).node[tree->tree_length] = *node_d;
	
	
	//E结点
	PNode *node_e = (PNode*)malloc(sizeof(PNode));
	node_e->data = 'E';
	node_e->parent  = 1;
	tree->tree_length ++;
	(*tree).node[tree->tree_length] = *node_e;
	
	
	//f结点
	PNode *node_f = (PNode*)malloc(sizeof(PNode));
	node_f->data = 'F';
	node_f->parent  = 3;
	tree->tree_length ++;
	(*tree).node[tree->tree_length] = *node_f;
	
	//g结点
	PNode *node_g = (PNode*)malloc(sizeof(PNode));
	node_g->data = 'G';
	node_g->parent  = 6;
	tree->tree_length ++;
	(*tree).node[tree->tree_length] = *node_g;
	
	//h结点
	PNode *node_H = (PNode*)malloc(sizeof(PNode));
	node_H->data = 'H';
	node_H->parent  = 6;
	tree->tree_length ++;\
	(*tree).node[tree->tree_length] = *node_H;
	
	//k结点
	PNode *node_K = (PNode*)malloc(sizeof(PNode));
	node_K->data = 'K';
	node_K->parent  = 6;
	tree->tree_length ++;
	(*tree).node[tree->tree_length] = *node_K;

	

}
int main(){
    
	PTree *tree = treeInit('R');
	catrePTree(tree);
	for(int i=0;i<=tree->tree_length;i++){
    
		printf("[%c,%d]",(tree->node)[i].data,(tree->node)[i].parent);
	}
	
}

在这里插入图片描述
如上图所示创建了双亲结点表示的树。

儿童代表

方法一

树中的每个节点可能有多个子树，因此可以使用多个链表。即有多个链表指向一个节点。那么就需要知道每个节点存在的词树的格式（节点的度），而每个节点的度是不同的，所以一般采用树的度作为每个节点的度（节点的度数必须小于或等于树的度数）。

在这里插入图片描述

但是实际使用的结点一定小于分配内存，造成了空间浪费。而且还能计算出浪费指针域：在一棵有n个结点度为K 的
树中必有n(k-1) + 1个空链域。

方法二

节点中添加了一个新的数据字段来存储指向该节点的度数，并且为每个节点分配了一个带有度数的指针字段。

在这里插入图片描述
这样每个结点需要多少指针域就分配多少不会造成空间浪费。

方法三

序列表用于存储节点，链表用于表示节点的子节点。

在这里插入图片描述

方法四

父子表示结合了两种方法。

在这里插入图片描述

弟弟代表

这种方法也称为二叉树表示法，或二叉链表表示法，它使用二叉链表作为树的存储结构。

子兄弟表示的实现是每个节点都有左右子树，左子树指向该节点的子节点，右子树指向兄弟节点。

一般树表示：
在这里插入图片描述
孩子兄弟表示（二叉树表示）：

链表中节点的两个链接字段分别指向该节点的第一个子节点和下一个兄弟节点。

R的左词树指向子节点A，右词树指向兄弟节点（无）。这种表示的奇妙之处在于它可以充分利用表示节点并发展节点的一定层次关系。

二叉树表示法的每个结点的左子树（包含左子树）的所有右子树的结点都是该节点的孩子结点，是左子树的兄弟结点。

这种存储结构的优点是它与二叉树的二叉链表表示完全相同。它将一般的树结构转换为二叉树进行处理，并使用二叉树算法来操作树。（最常用的存储方式）

#include<stdio.h>
#include<stdlib.h>

//树的二叉表示法
//结点
typedef struct SNode{
    
	struct SNode *child;
	char data;
	struct SNode *brother;
}SNode,STree;

//
STree* init(char e){
    
	SNode *node = (SNode*)malloc(sizeof(SNode));
	node->data = 'R';
	node->brother = NULL;
	node->child = NULL;
	return node;
}
//
void create(STree *tree){
    
	//A
	SNode *node_a = (SNode*)malloc(sizeof(SNode));
	node_a->data = 'A';
	node_a->brother = NULL;
	node_a->child = NULL;
	tree->child = node_a;
	
	
	//b
	SNode *node_b = (SNode*)malloc(sizeof(SNode));
	node_b->data = 'B';
	node_b->brother = NULL;
	node_b->child = NULL;
	node_a->brother = node_b;
	
	//c
	SNode *node_c = (SNode*)malloc(sizeof(SNode));
	node_c->data = 'C';
	node_c->brother = NULL;
	node_c->child = NULL;
	node_b->brother = node_c;
	
	//d
	SNode *node_d = (SNode*)malloc(sizeof(SNode));
	node_d->data = 'D';
	node_d->brother = NULL;
	node_d->child = NULL;
	node_a->child = node_d;
	
	//e
	SNode *node_e = (SNode*)malloc(sizeof(SNode));
	node_e->data = 'E';
	node_e->brother = NULL;
	node_e->child = NULL;
	node_d->brother = node_e;
	
	//f
	SNode *node_f = (SNode*)malloc(sizeof(SNode));
	node_f->data = 'F';
	node_f->brother = NULL;
	node_f->child = NULL;
	node_c->child = node_f;
	
	//G
	SNode *node_G = (SNode*)malloc(sizeof(SNode));
	node_G->data = 'G';
	node_G->brother = NULL;
	node_G->child = NULL;
	node_f->child = node_G;
	
	//h
	SNode *node_h = (SNode*)malloc(sizeof(SNode));
	node_h->data = 'H';
	node_h->brother = NULL;
	node_h->child = NULL;
	node_G->brother = node_h;
	
	//k
	SNode *node_k = (SNode*)malloc(sizeof(SNode));
	node_k->data = 'K';
	node_k->brother = NULL;
	node_k->child = NULL;
	node_h->brother = node_k;
	
	
}

//二叉树递归遍历(先序遍历)
void bianli(STree *tree){
    
	if(tree == NULL){
    
		return;
	}
	printf("%c",tree->data);
	bianli(tree->child);
	bianli(tree->brother);
}


int main(){
    
	STree *tree = init('R');
	create(tree);
	bianli(tree);
}

在构造的二叉树表示上使用前序遍历的结果也完全一致。

在这里插入图片描述
这种存储结构的优点是它和二叉树的二叉链表表示完全一样，便千将一般的树结构转换为二叉树进行处理，利用二叉树的算法来实现对树的操作。

森林存储方式

从树的二叉链表表示的定义可以看出，任何和树都有对应的二叉树表示，并且其二叉树表示的根节点的右子树必须为空。森林也是树木的集合。如果将森林的第二棵树视为第一棵树的二值表示的右根树。然后将森林合并成二叉树。

以此类推，森林中的多棵树变换后的二值表示就是前一棵树的二值表示的根节点的右子树，这样森林中的所有树就合并成了二值表示。

在这里插入图片描述

森林使用二叉树表示来存储，二叉树遍历一般包括前序、中序、后序和层次遍历。

父存储和子表示的树没有统一的规则，不能使用递归，但二叉树表示可以。

== 树没有中序遍历 ==

由于森林使用二叉树表示法，满足二叉树的特性因此可以使用二叉树的变量方法。但是缺也有一些限制，如没有中序遍历的树的二叉树表示。

原因是，树的二叉树表示法树的孩子结点可以任意交换顺序，这是树并没有变化，但是兄弟结点有多个，不符合中序遍历。
在这里插入图片描述

二叉树有一阶、末阶和中阶，因为二叉树由三部分组成：根、左子树和右子树。但树不一定只有三个部分，所以只能大致分为两部分：根和子树。因此，遍历有首根和末根。

没有后续的森林遍历

为什么普通树没有中序遍历，森林没有后序遍历？

. . .

一篇搞懂树、二叉树和森林

树简介

二叉树树的存储结构

树的存储结构

森林存储方式

相关推荐

Springboot——使用POI导出、下载excel文件

2021 PostgreSQL中国技术大会PPT下载

欧拉图（欧拉电路和欧拉路径）

软件测试面试必备文章：【2023年软件测试面试八篇作文指南】

还在使用Window原始的CMD界面？教你一招进行界面完美优化

atoi的使用及实现

nacos 的基本配置 yml, gateway基本配置 yml

使用VMVare虚拟机Centos7 搭建KVM虚拟机笔记

独立的小易(Java实现)

云原生中间件RocketMQ-生产者消息返回状态，延迟消息,自定义消息发送规则，netty框架部分代码分析

热门推荐

git 获取最后一次提交记录，只显示提交...

使用Redis Hash存储Java对象

day11_bootstrap

Python 第四节第八课

VS2010 MFC工程的MFC库使用方...

【实用 Python 库】Python ...

安卓案例：帧式布局演示（切换颜色）

一、 Mysql索引

一文详解接口测试(调试)工具postma...

【重学数据结构】栈与队列

最新推荐

将原来的ubuntu子系统从wsl1更改...

基础算法题_最古老的树（java）

笨方法学python 习题36

Direct3D 12——曲面细分阶段—...

【Unity3D编辑器开发】Unity3...

JVM学习（一）使用netbeans调试...

设计模式之状态模式

【CV 向】如何打造一个“数串串神器“

使用bootstrap编写登录注册页面，...

由于找不到d3dx9_33.dll文件导...