首页 > 编程语言 >数据结构与算法（二叉树）

数据结构与算法（二叉树）

时间：2024-11-01 10:50:47浏览次数：3  
标签：ps arr DataType 结点 算法 二叉树 child 数据结构

鲸饮未吞海，剑气已横秋。 

前言 

  这是我学习数据结构的第五份笔记，有关二叉树的知识。后期我会继续将数据结构知识的笔记补全。

  上一期笔记有栈与列队，没看过的同学可以去看看：
有关栈与列队的笔记icon-default.png?t=O83Ahttps://blog.csdn.net/hsy1603914691/article/details/143064674?spm=1001.2014.3001.5502

树

树的概念与结构

1. 树是⼀种非线性的数据结构，它是由 n 个有限结点组成的⼀个具有层次关系的集合。 2. 之所以把它叫做树，是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，而叶朝下。 2. 有⼀个特殊的结点，称为根结点，根结点没有前驱结点（父节点）。

3. 除根结点外，其余结点被分成 M(M>0) 个互不相交的集合，其中每⼀个集合又是⼀棵结构与树类似的子树。

4. 每棵子树的根结点有且只有⼀个前驱，可以有 0 个或多个后继（子节点）。因此，树是递归定义的。

5. 树形结构中，子树之间不能有交集，否则就不是树形结构。

6. 除了根结点外，每个结点有且仅有⼀个父结点（根节点没有父节点）。

7. ⼀棵N个结点的树有N-1条线（每多一个节点，就多一条线）。

树的相关术语

1. 父结点：若⼀个结点含有子结点，则这个结点就称为其子结点的父结点； 如上图：A是B的父结点。

2. 子结点：⼀个结点含有的子树的根结点，就称为该结点的子结点； 如上图：B是A的子结点。

3. 结点的度：⼀个结点有几个子节点，他的度就是多少；比如A的度为6，F的度为2，K的度为0。

4. 兄弟结点：具有相同父结点的结点，互称为兄弟结点； 如上图： B、C 是兄弟结点。

5. 树的度：⼀棵树中，最大的结点的度称为树的度； 如上图：树的度为 6。

6. 叶子结点：度为 0 的结点称为叶结点； 如上图： B、C、H、I... 等结点为叶结点。

7. 分支结点：度不为 0 的结点； 如上图： D、E、F、G... 等结点为分支结点。

8. 结点的层次：从根开始定义起，根为第 1 层，根的子结点为第 2 层，以此类推。

9. 树的高度（深度）：树中结点的最大层次； 如上图：树的高度为 4。

10. 结点的祖先：从根到该结点所经分支上的所有结点；如上图： A 是所有结点的祖先。

11. 结点的子孙：以某结点为根的子树中任⼀结点都称为该结点的子孙。如上图：所有结点都是A的子孙。

12. 路径：⼀条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列；比如A到Q的路径为： A-E-J-Q；H到Q的路径H-D-A-E-J-Q。

13. 森林：由 m  棵互不相交的树的集合称为森林。

树的表示 

1. 相对线性表结构，树结构更加复杂，既然保存值域，也要保存结点和结 点之间的关系。

2. 实际中，树有很多种表示方法如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子

兄弟表示法等。 3. 我们这里就简单的了解其中最常用的 孩子 兄弟表示法。 
#define _CRT_SECURE_NO_WARNINGS
typedef struct TreeNode
{
	struct TreeNode* child;
	struct TreeNode* brother;
	int data;
}TreeNode;

二叉树

1. 在树形结构中，我们最常用的就是二叉树，⼀棵二叉树是结点的⼀个有限集合，该集合由⼀个根结点加上两棵别称为左子树和右子树的二叉树组成（或者为空）。 2. 二叉树不存在度大于 2 的结点。 3. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。

 

 满二叉树

1. ⼀个二叉树，如果每⼀个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果⼀个二叉树的层数为 K ，且结点总数是 2^k − 1 ，则它就是满二叉树。

完全二叉树 

1. 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。 2. 要注意的是满二叉树是⼀种特殊的完全二叉树。 3. 假设二叉树层数为K层，除了第K层外，每层节点的个数达到最大节点的个数，而第K层节点个数不一定达到最大节点数，并且第K层节点顺序是严格从左到右的，那么这个二叉树就是完全二叉树。

 二叉树的性质

1. 若规定根结点的层数为 1 ，则⼀棵非空二叉树的第 i 层上最多有 2^（i−1）个结点。

2. 若规定根结点的层数为 1 ，则深度为 h 的二叉树的最大结点数是 2^h − 1。

3. 若规定根结点的层数为 1 ，具有 n 个结点的满二叉树的深度 h = log2 (n + 1) ( log

以2为底，（ n+1） 为对数)。

 二叉树存储结构

二叉树⼀般可以使用两种结构存储，⼀种顺序结构，⼀种链式结构。

顺序结构 

1. 二叉树的顺序结构存储就是使用数组来存储，⼀般使用数组只适合表示完全⼆叉树，因为不是完全二叉树会有空间的浪费，完全二叉树更适合使用顺序结构存储。 2. 我们通常把堆（⼀种二叉树）使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统 虚拟进程地址空间中的堆是两回事，⼀个是数据结构，⼀个是操作系统中管理内存的⼀块区域分段。 3. 根据数学关系我们可以得到数学公式，再根据顺序结构中不能跳的原则，从而得出节点的信息。

 链式结构

1. 二叉树的链式存储结构是指：用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 2. 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩 子所在的链结点的存储地址 。

3. 链式结构又分为二叉链和三叉链（多了一个指向父节点的指针），博客中⼀般都是二叉链。

堆

1. 堆是⼀种特殊的二叉树，具有二叉树的特性的同时，还具备其他的特性。 2. 堆一般使用顺序结构的数组来实现。

 堆的性质与结构

1. 堆中某个结点的值总是不大于或不小于其父结点的值。（可以等于）

2. 越往上，值越大的堆，就是大根堆；越往上，值越小的堆，就是小根堆。

3. 小根堆的堆顶是最小值；大根堆的堆顶是最大值。

4. 堆总是⼀棵完全二叉树。

1. 对于具有 n 个结点的完全二叉树，按照从上至下、从左至右的数组顺序对所有结点从 0 开始编号，最后节点的序号为（n-1）。

2. 若 i>0 ，则 i 结点的父节点序号为： ( i - 1 ) / 2 ；若 i=0 ，则 i 为根结点编号，无父结点。

3. 若 2i+1<n ，左孩子序号： 2i+1 ； 2i+1>=n 否则无左孩子，发生了越界。

4. 若 2i+2<n ，右孩子序号： 2i+2 ； 2i+2>=n 否则无右孩子，发生了越界。

分步实现堆的功能

定义一个堆的结构体 

typedef int DataType;
typedef struct Heap//定义一个堆的结构体
{
	DataType* arr;
	int size;
	int capacity;
}Heap;

 堆的初始化

void HeapInit(Heap* sp)
{
	assert(sp);//sp不能指向空指针，如果指向空指针，那么就不能对其进行解引用操作。
	sp->arr = NULL;
	sp->capacity = sp->size = 0;
}

交换两边值函数 

void Swap(DataType* a, DataType* b)//小心不要搞成交换指针
{
	DataType tmp = *a;
	*a = *b;
	*b = tmp;
}

 向上调整算法（为了实现小堆）

void UpAdjust(DataType* arr, DataType child)//child都是序号，而储存的数据是arr[child]
{
	int parent = (child - 1) / 2;
	while (child > 0)//不需要等于，如果孩子节点序号为0，则已经是根节点，不需要再向上调整。
	{
		if (arr[parent] > arr[child])
		{
			Swap(&arr[parent], &arr[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

向堆中插入数据 

void HeapPush(Heap* sp, DataType x)
{
	assert(sp);//sp不能指向空指针，如果指向空指针，那么就不能对其进行解引用操作。
	if (sp->capacity == sp->size)
	{
		int newcapacity = sp->capacity == 0 ? 4 : 2 * sp->capacity;
		DataType* tmp = (DataType*)realloc(sp->arr, sizeof(DataType)* newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		sp->arr = tmp;
		sp->capacity = newcapacity;
	}
	sp->arr[sp->size] = x;
    UpAdjust(ps->arr, ps->size);//变成小堆
    ps->size++;
}

向下调整算法（为了实现小队） 

void DownAdjust(DataType* arr, DataType parent, DataType n)
{
	DataType child = parent * 2 + 1;
	while(child<=n)
	{
		if ((child + 1 <= n) && (arr[child] > arr[child + 1]))
		{
			child++;
		}
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

从堆中删除元素 （只能从堆顶）

void HeapPop(Heap* ps)
{
	assert(ps->arr);//删除数据时候，堆里面要有数据,即ps->arr不能为空
	Swap(&(ps->arr[0]), &(ps->arr[ps->size-1]));
	ps->size--;
	DownAdjust(ps->arr, 0, ps->size-1);
}

 查询堆顶元素

DataType HeapTop(Heap* ps)
{
	assert(ps->size!=0);
	return ps->arr[0];//返回的是堆顶元素
}

 判断堆是否为空

bool HeapEmpty(Heap* ps)
{
	return (ps->size == 0);//不能通过判断ps->arr是否为NULL从而判断堆是否为空，因为即使ps->arr不是NULL，堆也可能为空（即ps->size==0）。
}

 销毁堆

void HeapDestroy(Heap* sp)
{
	assert(sp);//sp不能指向空指针，如果指向空指针，那么就不能对其进行解引用操作。
	if (sp->arr != NULL)
	{
		free(sp->arr);
	}
	sp->arr = NULL;
	sp->capacity = sp->size = 0;
}

完整代码实现

<heap.h>文件 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int DataType;
typedef struct Heap
{
	DataType* arr;
	int size;
	int capacity;
}Heap;

void HeapInit(Heap* ps);

void HeapDestroy(Heap* ps);

void HeapPush(Heap* ps, DataType x);

void UpAdjust(DataType* arr, DataType child);

void HeapPop(Heap* ps);

void Swap(DataType* a, DataType* b);

void DownAdjust(DataType* arr, DataType parent, DataType n);

DataType HeapTop(Heap* ps);

bool HeapEmpty(Heap* ps);

 <heap.c>文件 

#include "heap.h"

void HeapInit(Heap* ps)
{
	assert(ps);//ps不能指向空指针，如果指向空指针，那么就不能对其进行解引用操作。
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

void HeapDestroy(Heap* ps)
{
	assert(ps);//ps不能指向空指针，如果指向空指针，那么就不能对其进行解引用操作。
	if (ps->arr != NULL)//判断指向动态数组的指针是否为空
	{
		free(ps->arr);//如果不为空，则释放动态数组的空间
	}
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

void HeapPush(Heap* ps, DataType x)
{
	assert(ps);//ps不能指向空指针，如果指向空指针，那么就不能对其进行解引用操作。
	if (ps->capacity == ps->size)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		DataType* tmp = (DataType*)realloc(ps->arr, sizeof(DataType)* newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
	ps->arr[ps->size] = x;
	UpAdjust(ps->arr, ps->size);//变成小堆
	ps->size++;
}

void Swap(DataType* a, DataType* b)//小心不要搞成交换指针
{
	DataType tmp = *a;
	*a = *b;
	*b = tmp;
}

void UpAdjust(DataType* arr, DataType child)//child都是序号，而储存的数据是arr[child]
{
	int parent = (child - 1) / 2;
	while (child > 0)//不需要等于，如果孩子节点序号为0，则已经是根节点，不需要再向上调整。
	{
		if (arr[parent] > arr[child])
		{
			Swap(&arr[parent], &arr[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void HeapPop(Heap* ps)
{
	assert(ps->arr);//删除数据时候，堆里面要有数据,即ps->arr不能为空
	Swap(&(ps->arr[0]), &(ps->arr[ps->size-1]));
	ps->size--;
	DownAdjust(ps->arr, 0, ps->size-1);
}

void DownAdjust(DataType* arr, DataType parent, DataType n)
{
	DataType child = parent * 2 + 1;
	while(child<=n)
	{
		if ((child + 1 <= n) && (arr[child] > arr[child + 1]))
		{
			child++;
		}
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

DataType HeapTop(Heap* ps)
{
	assert(ps->size!=0);
	return ps->arr[0];//返回的是堆顶元素
}

bool HeapEmpty(Heap* ps)
{
	return (ps->size == 0);//不能通过判断ps->arr是否为NULL从而判断堆是否为空，因为即使ps->arr不是NULL，堆也可能为空（即ps->size==0）。
}

 <test.c>文件

#include "heap.h"
int main()
{
	Heap heap;
	HeapInit(&heap);
	HeapPush(&heap, 1);
	HeapPush(&heap, 2);
	HeapPush(&heap, 3);
	HeapPush(&heap, 4);
	HeapPush(&heap, 5);
	HeapPop(&heap);
	while (!HeapEmpty(&heap))
	{
		printf("%d ", HeapTop(&heap));
		HeapPop(&heap);
	}
	HeapDestroy(&heap);
	return 0;
}

 致谢

  感谢您花时间阅读这篇文章！如果您对本文有任何疑问、建议或是想要分享您的看法，请不要犹豫，在评论区留下您的宝贵意见。每一次互动都是我前进的动力，您的支持是我最大的鼓励。期待与您的交流，让我们共同成长，探索技术世界的无限可能！

标签：ps,arr,DataType,结点,算法,二叉树,child,数据结构
From： https://blog.csdn.net/hsy1603914691/article/details/143217772

相关文章

  • 02链表算法/代码随想录
    前几天忙比赛，算法停了三天，继续开刷，不能停！！二、链表2.1删除链表中的元素两种方案无哨头：要删除节点的前一个结点指向删除节点的指向节点。头节点需要单独定义有哨头：头节点不需要单独定义实战力扣203/***Definitionforsingly-linkedlist.*publicclassLis......
  • 【SSL-RL】自监督强化学习：Plan2Explore算法
            ......
  • C语言数据结构之二叉树（BINARY TREE）链式存贮的简单实现
    C语言数据结构之二叉树（BINARYTREE）链式存贮的简单实现树型数据结构在应用中非常多，效率也非常好，只是结构相对复杂，理解起来有点儿难度！！！定义数据结构typedefstruct_BTreeNodeBTreeNode;struct_BTreeNode{intval;BTreeNode*lchild,*rchild;};自定义结构体数......
  • C语言数据结构之哈希表（HASHTABLE）的实现
    C语言数据结构之哈希表（HASHTABLE）的实现哈希表的每个节点保存的数据格式为key:value，其中key为字符串，根据字符串内容采用不同方法（哈希函数）生成一个无符号整型哈希码，根据表的长度，采用取余法，将数据存入表单元，如果此表单元中已存在数据，则以此表单元为链表头，向链表追加数据，这......
  • pairwise算法之rank svm
    众所周知，point-wise/pair-wise/list-wise是机器学习领域中重要的几种建模方法。比如，最常见的分类算法使用了point-wise，即一条样本对应一个label(0/1)，根据多条正负样本，使用交叉熵（crossentropy）等方法构建损失函数，来训练模型。顾名思义，Pairwise方法是一种基于样本对比较的排......
  • 动态规划 01背包（算法）
    现有四个物品，小偷的背包容量为8，怎么可以偷得价值较多的物品如:物品编号：1   2   3   4 物品容量：2   3   4   5物品价值：3   4   5   8记f(k,w),当背包容量为w,可以偷k件物品，所能偷到的最大价值以f(4,8)为列，记录每......
  • 大模型算法面试题总结
    更多面试题总结，请移步至​https://i.afbcs.cn/naPbNY​1.什么是大型语言模型（LLMs）以及它们的工作原理是什么？大型语言模型（LLMs）是设计用来理解、处理和生成类似人类文本的高级人工智能系统。例子包括GPT（生成预训练变换器）、BERT（来自变换器的双向编码器表示）、Claude和Llama。这些......
  • 告别龟速加载：三种压缩算法让你的网站瞬间提速！
    三种压缩算法，让你的网站飞起来！！！2万字深度长文，让你一次看个爽！！！欢迎订阅专栏，永不收费，hacker精神，更快获得第一手优质博文！！！前言在当今快节奏的互联网世界，用户对网站加载速度的要求越来越高。一个加载缓慢的网站不仅会损害用户体验，还会影响搜索引擎排名，最终导致流量和转......
  • 【深度学习】从公式推导来深入理解误差反向传播算法2：《深度学习入门基于Python的理论
    《深度学习入门基于Python的理论与实现》中实现了2层全连接神经网络的代码对MNIST数据集的28x28像素0-9手写数字灰度图像进行分类，本文将重点对代码中的two_layer_net类的gradient函数中的误差反向传播的代码进行公式推导验证。验证小批量数据的交叉熵损失函数对第2层权重......
  • C++ 手撕--基本数据结构的简单实现
    C++面试手撕代码----基本数据结构的简单实现1.String数据结构的简单实现：#include<iostream>#include<cstring>//forstrcpystrlenmethodsusingnamespacestd;classString{private: char*data; size_tlength;public: String():data(nullptr),length(0)......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99