首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >数据结构—— 初识二叉树

数据结构—— 初识二叉树

作者头像
迷迭所归处
发布2024-11-19 17:05:15
发布2024-11-19 17:05:15
12600
代码可运行
举报
文章被收录于专栏:动态规划动态规划
运行总次数:0
代码可运行

1.树概念及结构

1.1树的概念

树是由根和子树构成

树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的

1. 树有一个特殊的结点,称为根结点,根结点就是第一个节点

2. 除根结点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i<= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个子节点

3. 树是递归定义的

4.在树形结构中,子树之间不能有交集,否则就不是树


1.2 树的相关概念

节点的度:一个节点含有的子树的个数称为该节点的度:如上图:A的为6(A B C D E F G)

重要部分:

* 叶节点或终端节点:子节点为0的节点称为叶节点; 如上图:B、C、H、I...等节点为叶节点

* 非终端节点或分支节点:度不为0的节点; 如上图:D、E、F、G...等结点为分支节点

* 双亲结点或父结点:若一个结点含有子结点,则这个节点称为其子节点的父节点; 如上图:A是B的父节点

* 孩子节点或子节点:一个节点含有的子树的根节点称为该结点的子结点; 如上图:B是A的孩子节点

* 树的高度或深度:树中节点的最大层次; 如上图:树的高度为4


了解一下:

兄弟节点:具有相同父节点的节点互称为兄弟节点; 如上图:B、C是兄弟节点

树的度:一棵树中,最大的节点的度称为树的度; 如上图:树的度为6(A B C D E F G)

结点的层次:从根开始定义起,根为第1层,根的子结点为第2层,以此类推

堂兄弟结点:双亲在同一层的节点互为堂兄弟;如上图:H、I互为兄弟节点

结点的祖先:从根到该结点所经分支上的所有结点;如上图:A是所有节点的祖先

子孙:以某结点为根的子树中任一结点都称为该结点的子孙。如上图:所有节点都是A的子孙

森林:由m(m>0)棵互不相交的树的集合称为森林(并查集,文件系统)


1.3 树的表示方法

树结构存储表示起来比较麻烦,既然保存值域,也要保存结点和结点之间

这里使用 "左孩子右兄弟 "表示法(子节点和兄弟节点)

也就是说不管有多少个孩子,每个节点只指向第一个孩子

1.A指向子节点B,A没有兄弟节点,指向空 

2.B指向子节点D,B指向兄弟节点C,C没有兄弟节点,指向空 

3.D没有子节点,D指向兄弟节点E,E指向兄弟节点F,F没有兄弟节点,指向空

4.E指向子节点H,H指向兄弟节点I,I没有兄弟节点,指向空 

代码语言:javascript
代码运行次数:0
运行
复制
struct TreeNode
{
    int val;

    struct Node* leftchild;
    struct Node* rightBrother;

};

2.二叉树概念及结构

2.1概念

一棵二叉树是结点的一个有限集合,该集合:

                                                1. 或者为空

                                                2. 由一个根结点加上两棵别称为左子树和右子树的二叉树组成 

3. 二叉树不存在度大于2的结点

                                                4.二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树


2.2 特殊的二叉树:

1. 满二叉树:每一个层的节点数都达到最大值,则这个二叉树就是满二叉树

也就是说,如果一棵二叉树的层数为K,且结点总数是(2^k - 1),则它就是满二叉树

 2. 完全二叉树:前h-1层都是满的,最后一层不是满的,最后一层从左到右必须是连续的,如果不是连续的那么就不是完全二叉树

连续的:

不连续的: 

满二叉树是一种特殊的完全二叉树,但是完全二叉树不是满二叉树


2.3 满二叉树和完全二叉树的位置计算

假设父节点在数组中的下标为i,那么:

                                                        1.左孩子在数组中的下标为:2*i+1 

                                                        2.右孩子在数组中的下标为:2*i+2

假设孩子在数组中的下标为i,那么:

                                                        父在数组中的下标为:(i - 1)/ 2

在这里不区分左孩子和右孩子,因为除以会向下取整


3. 堆的概念及结构

3.1 

1. 堆中某个结点的值总是不大于或不小于其父结点的值

2. 堆在逻辑上是一棵完全二叉树,物理上就是数组

3. 堆分为小堆和大堆

大堆:a. 完全二叉树

           b. 任何一个父亲 > = 儿子

特点:根是最小

小堆: a. 完全二叉树

           b. 任何一个父亲 < = 儿子

特点:根是最大


3.2 堆的实现

Heap.h

代码语言:javascript
代码运行次数:0
运行
复制
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>


typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;



//堆的初始化
void HPInit(HP* php);

//堆的销毁
void HPDestroy(HP* php);

//堆的插入
void HPPush(HP* php, HPDataType x);

//堆的删除
void HPPop(HP* php);

// 取堆顶的数据
HPDataType HPTop(HP* php);

//堆的判空
bool HPEmpty(HP* php);


void Swap(HPDataType* p1, HPDataType* p2);


void AdjustUp(HPDataType* a, int child);


void AdjustDown(HPDataType* a, int n, int parent);

Heap.c分解分析

堆的初始化

代码语言:javascript
代码运行次数:0
运行
复制
//堆的初始化
void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}

堆的销毁

代码语言:javascript
代码运行次数:0
运行
复制
//堆的销毁
void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

堆的插入 

代码语言:javascript
代码运行次数:0
运行
复制
//堆的插入
void HPPush(HP* php, HPDataType x)
{
	assert(php);

	//判断内存是否满
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		php->a = tmp;
		php->capacity = newcapacity;
	}

	//插入数据
	php->a[php->size] = x;
	php->size++;

	//插入数据之后需要向上调整
	AdjustUp(php->a, php->size - 1);
}

堆的插入逻辑交换图表(向上调整)

堆的插入数据之后是否向上调整

代码语言:javascript
代码运行次数:0
运行
复制
//堆的插入数据之后是否向上调整
void AdjustUp(HPDataType* a, int child)
{
	//孩子/2找到父节点
	int parent = (child - 1) / 2;
	//孩子大于0就进入/继续
	while (child > 0)
	{
		//如果孩子小于父亲
		if (a[child] < a[parent])
		{
			
			Swap(&a[child], &a[parent]);//交换
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

堆的交换

代码语言:javascript
代码运行次数:0
运行
复制
//堆的交换
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

堆的删除:一般是删除根

思路:排序删除:交换根和最后一个子节点的位置,再删除根,之后再进行向下调整算法(向下调整的前提是左右子树都是大小堆),然后根据左右子树的大小选择小的那个进行调整

代码语言:javascript
代码运行次数:0
运行
复制
//堆的删除
void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	//交换下标为0的根和末尾数据的位置
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;//删除
	//向下调整
	AdjustDown(php->a, php->size, 0);
}

堆的向下调整

思路:先假设左孩子小,然后找出小的那个孩子,再判断右孩子是否小于n并且右孩子小于左孩子 

                                          向下调整的前提是左右子树都是大小堆                                                

代码语言:javascript
代码运行次数:0
运行
复制
//堆的向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
	// 先假设左孩子小
	int child = parent * 2 + 1;

	// child >= n说明孩子不存在,调整到叶子了
	while (child < n) 
	{
		// 找出小的那个孩子
		//判断右孩子是否小于n并且右孩子小于左孩子 
		if (child + 1 < n && a[child + 1] < a[child])
		{
			++child;
		}

	//if (a[child] > a[parent]) 大堆
	//孩子小于父亲
	if (a[child] < a[parent])//小堆
	{
		//交换
		Swap(&a[child], &a[parent]);
		parent = child;//赋予
		//继续算左孩子
		child = parent * 2 + 1;
	}
	else
	{
		break;
	}
}

取堆顶的数据

代码语言:javascript
代码运行次数:0
运行
复制
// 取堆顶的数据
HPDataType HPTop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	return php->a[0];
}

堆的判空

代码语言:javascript
代码运行次数:0
运行
复制
//堆的判空
bool HPEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

Heap.c全部代码

代码语言:javascript
代码运行次数:0
运行
复制
#include"Heap.h"

//堆的初始化
void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}

//堆的销毁
void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

//堆的插入
void HPPush(HP* php, HPDataType x)
{
	assert(php);

	//判断内存是否满
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		php->a = tmp;
		php->capacity = newcapacity;
	}

	//插入数据
	php->a[php->size] = x;
	php->size++;

	//插入数据之后需要向上调整
	AdjustUp(php->a, php->size - 1);
}

//堆的插入数据之后是否向上调整
void AdjustUp(HPDataType* a, int child)
{
	//孩子/2找到父节点
	int parent = (child - 1) / 2;
	//孩子大于0就进入/继续
	while (child > 0)
	{
		//如果孩子小于父亲
		if (a[child] < a[parent])
		{
			
			Swap(&a[child], &a[parent]);//交换
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//堆的交换
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//堆的删除
void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	//交换下标为0的根和末尾数据的位置
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;//删除
	//向下调整
	AdjustDown(php->a, php->size, 0);
}

//堆的向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
	// 先假设左孩子小
	int child = parent * 2 + 1;

	// child >= n说明孩子不存在,调整到叶子了
	while (child < n) 
	{
		// 找出小的那个孩子
		//判断右孩子是否小于n并且右孩子小于左孩子 
		if (child + 1 < n && a[child + 1] < a[child])
		{
			++child;
		}


		//if (a[child] > a[parent]) 大堆
		//孩子小于父亲
		if (a[child] < a[parent])//小堆
		{
			//交换
			Swap(&a[child], &a[parent]);
			parent = child;//赋予
			//继续算左孩子
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

// 取堆顶的数据
HPDataType HPTop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	return php->a[0];
}

//堆的判空
bool HPEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

感谢观看~

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-08-21,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1.树概念及结构
    • 1.1树的概念
    • 1.2 树的相关概念
    • 1.3 树的表示方法
  • 2.二叉树概念及结构
    • 2.1概念
    • 2.2 特殊的二叉树:
    • 2.3 满二叉树和完全二叉树的位置计算
  • 3. 堆的概念及结构
    • 3.1 
    • 3.2 堆的实现
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档