首页 > 其他分享 >深入了解：二叉树（最详细，约10000字）

深入了解：二叉树（最详细，约10000字）

时间：2024-03-24 18:31:56浏览次数：35  
标签：pq 10000 二叉树 详细 return NULL root 节点

目录

1. 树概念及结构

1.1树概念

1.2树的表示

2. 二叉树概念及结构

2.1概念

2.2数据结构中的二叉树

2.3特殊的二叉树

2.4二叉树的存储结构

2.4.1顺序存储

2.4.2链式存储

2.5二叉树的性质

3. 二叉树顺序结构及概念

3.1二叉树的顺序结构

3.2堆的概念及结构

3.3堆的实现

4. 二叉树链式结构及实现

4.1二叉树链式结构的遍历

4.2二叉树的链式实现

1. 树概念及结构

1.1树概念

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

节点的度：一个节点含有的子树的个数称为该节点的度； 如二叉树的图：100节点的度为2
叶节点：度为0的节点称为叶节点； 如二叉树的图：2,7,3,25,1节点
非终端节点或分支节点：度不为0的节点； 如二叉树的图：100,19,36,17节点为分支节点
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如二叉树的图：100是19的父节点

（我解释为什么有的地方叫双亲节点：因为在实际世界中，父亲节点，有人会说它是男权，为了避免纠纷，就叫双亲节点，但是我们一定要注意双亲节点不是指两个节点，而是指一个。我们一般说父亲节点，会便于我们理解）
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如二叉树的图：19是100的孩子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：19、36是兄弟节点
树的度：一棵树中，最大的节点的度称为树的度； 如多叉树图：树的度为5
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
堂兄弟节点：深度相同，父亲不同。如二叉树的图，17的堂兄弟节点包括25,1（不包括3）
节点的祖先：从根到该节点所经分支上的所有节点；（包括父亲节点）
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如二叉树图：所有节点都是100的子孙
森林：由m棵互不相交的树的集合称为森林；

1.2树的表示

多叉树的表示：

typedef int DataType;
typedef struct TreeNode
{
     struct Node* firstChild1; //第一个孩子
     struct Node* pNextBrother; //兄弟节点
     DataType data; 
}TNode;

 

因为不知道节点的度是多少，这种结构巧妙的解决结构体定义几个指针的问题 。

让4这个节点的brother指针指向它的兄弟5节点，这样可以找到5节点，然后5节点的bother指针指向6节点....依次下去，可以把一层的节点都链接上

二叉树的表示：

typedef int BTDataType
typedef struct BinaryTreeNode
{
    BTDataType data;//存储数据
    struct BinaryTreeNode* left;//指向它的左孩子
    struct BinaryTreeNode* right;//指向它的右孩子
}BTNode;


2. 二叉树概念及结构


2.1概念

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
二叉树的特点：

  1. 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
  2. 二叉树的子树有左右之分，其子树的次序不能颠倒。

2.2数据结构中的二叉树

包括五种树形结构：1.空树   2.只有一个根节点   3.只有左树   4.只有右树   5.左右子树都存在


2.3特殊的二叉树

1.完全二叉树：除了最后一层之外的其他层都是满的，最后一层有数据的节点要从左到右连续的。当出现空节点之后，右边不能有其他右数据的节点。

2.满二叉树： 除了叶子节点，其他节点的度都为2，没有度为1的节点（每一层都是满的）


2.4二叉树的存储结构


2.4.1顺序存储（连续的）

用数组的形式来存储：

会产生以下特性：

leftchild=parent*2+1(左孩子=存储父亲节点的下标*2+1)； 

rightchild=leftchild+1=parent*2+2;(右孩子=存储父亲节点的下标*2+2）

parent=（child+1）/2     （ 不管左右孩子，都是这一条公式，你可以自己看看存储在数组中的下标，右孩子都是存储偶数的下标，左孩子都是存储在奇数的下标。+1再/2不会改变整数的部分。）


2.4.2链式存储（不连续的）

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。

一般分为二叉链和三叉链：

 二叉链：两个指针，指向它的左右孩子。

三叉链：不仅有两个指针指向它的孩子，还多一个指针，用来指向它的父亲节点。

   // 二叉链
   struct BinaryTreeNode
   {
    struct BinTreeNode* Left; // 指向当前节点左孩子
    struct BinTreeNode* Right; // 指向当前节点右孩子
    BTDataType data; // 当前节点存储的值
   }
   // 三叉链
   struct BinaryTreeNode
   {
    struct BinTreeNode* Parent; // 指向当前节点的双亲
    struct BinTreeNode* Left; // 指向当前节点左孩子
    struct BinTreeNode* Right; // 指向当前节点右孩子
    BTDataType data; // 当前节点存储的值
   }；


2.5二叉树的性质

 2.5.1  性质一：

度为0的节点个数一定比度为2的节点个数多1（在一些选择题会用到） 

如题：

 设Ni表示度为i的节点个数，则节点总数 N = N0 + N1 + N2

节点个数于节点边的关系： N个节点的树有N-1个边

边与度的关系：N - 1 = N1 + 2 * N2

故：N0 + N1 + N2 - 1 = N1 + 2 * N2

因此，得：N0 = N2 + 1

回到原题，N0 = 3，N1 = 8，可得N2 = 2。

因此答案是 3 + 8 + 2 = 13。

 2.5.2  性质二：

若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log2(N+1) (解析： 是log以2 为底，n+1为对数)

2.5.3  性质三：

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

2.5.4  性质四：

若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 ：n=（2^h ）-1个

2.5.5   性质五：

 对任何一棵二叉树, 如果度为0其叶结点个数为 , 度为2的分支结点个数为 ,则有 n0＝ n2＋1（注：n0=n2+1的意思就是在所有二叉树中，度为0的节点个数永远比度为2的节点个数多一个。）


3. 二叉树顺序结构及概念


3.1二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。 （同名字，但是性质完全不同）


3.2堆的概念，结构，实现

里面包括堆的概念和用堆来实现的排序。 

http://t.csdnimg.cn/n0qur



4. 二叉树链式结构

对于二叉树这个章节，我们不学二叉树的增删查改 （因为二叉树不是用来单纯的存储数据，而是用来查找的）

我们需要学二叉树的查找相关的知识

我们要学二叉树的前序遍历，中序遍历，后序遍历，层序遍历，个数，高度，第k层的节点个数，查找x所在节点的指针，查找二叉树中有没有x，二叉树的销毁，判断二叉树是否是完全二叉树。

1.前序遍历： 先遍历根节点，再左节点，最后右节点

2.中序遍历 ：先遍历左节点，再根节点，最后右节点

3.后序遍历： 先遍历左节点，再右节点，最后根节点

遍历：我们需要用到递归，先去到最深层，然后遍历，return到上一层，重复下去。

A->B->D->H->NULL->NULL->D->I->NULL->NULL->D->B->E->J->NULL->NULL->C->F->K->NULL->NULL->G->NULL->NULL, 然后回到第一层出去。

中序，后序同理。

我们需要想象出NULL节点，才能便于理解。

if(root==NULL)
{
        return;

}//递归的返回条件

在这里我只找到了后序遍历的动态图。

前中后序都大同小异。 

三种遍历的代码：

//前序遍历
void PreOrder(BT* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;//在viod类型的函数，进行递归，想要返回上一层，可以用  return; 用来终止函数的执行
	}
	printf("%d ", root->val);
	PreOrder(root->left);
	PreOrder(root->right);
}

//中序遍历
void InOrder(BT* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}

//后序遍历
void PostOrder(BT* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}

查找二叉树的节点个数：

递归左边，返回左边的个数，+递归右边，返回右边的个数+1（1表示当前节点）

int TreeSize(BT* root)
{
	if (root == NULL)
	{
		return 0;//如果是NULL，返回0，递归的返回条件
	}
	return TreeSize(root->left) + TreeSize(root->right) + 1;
}

二叉树的高度：

int TreeHight(BT* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftsize = TreeHight(root->left);
	int rightsize = TreeHight(root->right);
	return leftsize > rightsize ? leftsize + 1 : rightsize + 1;
}

 第k层的节点个数:

 遍历的过程k--，当k==1时说明到达那一层，如果有节点就返回1，如果出现NULL，就返回0了。

int TreeKsize(BT* root,int k)
{
	assert(k > 0); 
	if (root == NULL)	return 0;
	if (k == 1)	return 1;
	int tleft = TreeKsize(root->left, k - 1);
	int tright = TreeKsize(root->right, k - 1);
	return tleft+tright;
}

查找x所在的位置，并且返回节点的地址 ：

因为返回的时候是返回到上一层，所以需要用变量保存指针，判断返回出来的是否为空，如果不为空，就会一直回到上一层。直到出去。

//查找x所在节点的指针
BT* TreeNodeFind(BT* root, int x)
{
	if (root == NULL)	return NULL;
	if (root->val == x)
	{
		return root;
	}
	BT* ret1=TreeNodeFind(root->left, x);
	if (ret1)
	{
		return ret1;
	}
	BT* ret2=TreeNodeFind(root->right, x);
	if (ret2)
	{
		return ret2;
	}
	return NULL;
}

查找二叉树中有没有x：

 如果找到了就返回true，然后因为是或||，一个为真就返回true

//查找二叉树中有没有x
bool TreeSearch(BT* root, int x)
{
    if(root==NULL) return fasle;
    if(root->val==x) return true;
    return TreeSearch(root->left,x)||TreeSearch(root->right,x);
}

 判断二叉树是否是完全二叉树：

插入到队列中，完全二叉树的特性是：前面都是有数据的节点，后面都是NULL。

不满足的话就不是完全二叉树。

所以写代码的时候可以利用这一点特性，把数据存储到队列中，利用层序遍历来判断。

bool BinaryTreeComplete(BT* root)
{
    // 层序遍历
	QueueNode pq;
	QueueInit(&pq);
	if (root)//不是空树的时候
	{
		QueuePush(&pq, root);//插入当前节点的值到队列中
	}
	while (!QueueEmpty(&pq))
	{
		BT* tmp = QueueFront(&pq);
		QueuePop(&pq);
		if(tmp == NULL)	break;//一层一层的出和进，所以不可能遇到空的时候，非空还没有进
		QueuePush(&pq, tmp->left);
		QueuePush(&pq, tmp->right);
	}
	while (!QueueEmpty(&pq))
	{
		if (QueueFront(&pq) == NULL)
		{
			QueuePop(&pq);
		}
		if (QueueFront(&pq))
		{
			QueueDestry(&pq);
			return false;
		}
	}
	return true;
	QueueDestry(&pq);
}

二叉树链式结构全部的代码：

Binary_tree.h(二叉树的头文件)


#include<stdlib.h>
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<math.h>
typedef struct Binary_tree
{
	struct Binary_tree* left;
	struct Binary_tree* right;
	int val;
}BT;

BT* BTCreate(int val);

//前序，中序，后序，个数，高度，第k层的节点个数
void PreOrder(BT* root);
void InOrder(BT* root);
void PostOrder(BT* root);
int TreeSize(BT* root);
int TreeHight(BT* root);
int TreeKsize(BT* root,int k);

//查找x所在节点的指针
BT* TreeNodeFind(BT* root, int x);

//查找二叉树中有没有x
bool TreeSearch(BT* root, int x);

//二叉树的销毁
void BTDestory(BT* root);

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BT* root);

// 层序遍历
void BinaryTreeLevelOrder(BT* root);

 Binary_tree.c（二叉树的源文件）

#define _CRT_SECURE_NO_WARNINGS 1
#include"Binary_tree.h"
#include"Queue.h"
BT* BTCreate(int val)
{
	BT* NewNode = (BT*)malloc(sizeof(BT));
	if (NewNode == NULL)
	{
		perror("malloc error");
		exit(-1);
	}
	NewNode->left = NULL;
	NewNode->right = NULL;
	NewNode->val = val;
	return NewNode;
}
 
void PreOrder(BT* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;                          //在viod类型的函数，进行递归，想要返回上一层，可以用  return; 用来终止函数的执行
	}
	printf("%d ", root->val);
	PreOrder(root->left);
	PreOrder(root->right);
}
void InOrder(BT* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}
void PostOrder(BT* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}
int TreeSize(BT* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return TreeSize(root->left) + TreeSize(root->right) + 1;
}
int TreeHight(BT* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftsize = TreeHight(root->left);
	int rightsize = TreeHight(root->right);
	return leftsize > rightsize ? leftsize + 1 : rightsize + 1;
}
 
int TreeKsize(BT* root,int k)
{
	assert(k > 0); 
	if (root == NULL)	return 0;
	if (k == 1)	return 1;
	int tleft = TreeKsize(root->left, k - 1);
	int tright = TreeKsize(root->right, k - 1);
	return tleft+tright;
}
 
//查找x所在节点的指针
BT* TreeNodeFind(BT* root, int x)
{
	if (root == NULL)	return NULL;
	if (root->val == x)
	{
		return root;
	}
	BT* ret1=TreeNodeFind(root->left, x);
	if (ret1)
	{
		return ret1;
	}
	BT* ret2=TreeNodeFind(root->right, x);
	if (ret2)
	{
		return ret2;
	}
	return NULL;
}
 
//查找节点在不在
bool TreeSearch(BT* root, int x)
{
	if (root == NULL) return false;
	if (root->val == x) return true;
	return  TreeSearch(root->left, x) || TreeSearch(root->right, x);
}
 
void BTDestory(BT* root)
{
	if (root == NULL)
	{
		return;
	}
	BTDestory(root->left);
	BTDestory(root->right);
	free(root);
}
 
// 判断二叉树是否是完全二叉树（包括满二叉树+完全二叉树）
//完全二叉树特征：非空 空
//普通的二叉树：非空 空 非空...
bool BinaryTreeComplete(BT* root)
{
	// 层序遍历
	QueueNode pq;
	QueueInit(&pq);
	if (root)//不是空树的时候
	{
		QueuePush(&pq, root);//插入当前节点的值到队列中
	}
	while (!QueueEmpty(&pq))
	{
		BT* tmp = QueueFront(&pq);
		QueuePop(&pq);
		if(tmp == NULL)	break;//一层一层的出和进，所以不可能遇到空的时候，非空还没有进
		QueuePush(&pq, tmp->left);
		QueuePush(&pq, tmp->right);
	}
	while (!QueueEmpty(&pq))
	{
		if (QueueFront(&pq) == NULL)
		{
			QueuePop(&pq);
		}
		if (QueueFront(&pq))
		{
			QueueDestry(&pq);
			return false;
		}
	}
	return true;
	QueueDestry(&pq);
}
 
// 层序遍历
void BinaryTreeLevelOrder(BT* root)//循环
{
	QueueNode pq;
	QueueInit(&pq);
	if (root)
	{
		QueuePush(&pq, root);//插入当前节点的值到队列中
	}
	while (!QueueEmpty(&pq))
	{
		BT* tmp = QueueFront(&pq);
		QueuePop(&pq);
		printf("%d ",tmp->val);
		if (tmp->left != NULL)
		{
			QueuePush(&pq, tmp->left);
		}
		if (tmp->right != NULL)
		{
			QueuePush(&pq, tmp->right);
		}
	}
	printf("\n");
	QueueDestry(&pq);
 
}

 队列的头文件：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef struct Binary_tree* QDataType;//节点的指针
typedef struct QueueNode
{
	QDataType data;
	struct Queue* next;
}QueueNode;

typedef struct Queue
{
	QueueNode* head;
	QueueNode* tial;
}Queue;

//初始化和销毁
void QueueInit(Queue* pq);
void QueueDestry(Queue* pq);

//插入
void QueuePush(Queue* pq,QDataType x);

//删除
void QueuePop(Queue* pq);

//读取队头的数据
QDataType QueueFront(Queue* pq);

//读取队尾的数据
QDataType QueueBreak(Queue* pq);

//读取队列的数据个数
int QueueSize(Queue* pq);

//判断队列是否为空
bool QueueEmpty(Queue* pq);

队列的源文件： 

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
//初始化和销毁
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tial = NULL;
}
void QueueDestry(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tial = NULL;
}

//插入
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* tmp=(QueueNode*)malloc(sizeof(QueueNode));
	if (tmp == NULL)
	{
		perror("malloc error");
		exit(-1);
	}
	tmp->data = x;
	tmp->next = NULL;
	if (pq->head == NULL)
	{
		pq->head = pq->tial = tmp;
	}
	else
	{
		pq->tial->next = tmp;
		pq->tial = tmp;
	}
}

//删除
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	if (pq->head == pq->tial)
	{
		pq->head = pq->tial = NULL;
	}
	else
	{
		QueueNode* tmp = pq->head->next;
		free(pq->head);
		pq->head = tmp;
	}
}

//读取队头的数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}

//读取队尾的数据
QDataType QueueBreak(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->tial->data;
}

//读取队列的数据个数
int QueueSize(Queue* pq)
{
	assert(pq);
	int count = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		cur = cur->next;
		count++;
	}
	return count;
}

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

标签：pq,10000,二叉树,详细,return,NULL,root,节点
From： https://blog.csdn.net/2301_80215560/article/details/136888307

相关文章

  • 软件项目开发运用的全套文档模板（规格说明书、详细设计、测试计划、验收报告）
       前言：在软件开发过程中，文档资料是非常关键的一部分，它们帮助团队成员理解项目需求、设计、实施、测试、验收等各个环节，确保项目的顺利进行。以下是针对您提到的各个阶段的文档资料概述：所有资料获取：点击获取开发阶段需求规格说明书：详细描述了软件系统的功能需求、非......
  • 模拟汽车驾驶的程序（详细注释版）
    使用Unity制作3D驾驶游戏Unity2024 专业游戏设计下载地址网址地址：https://download.csdn.net/download/Samuel2014/89023382在UnityHDRP中创建完整的驾驶游戏定制不同类型的汽车将人工智能汽车和人工智能航路点系统添加到您的赛道添加汽车陈列室菜单以解锁和购买新......
  • 基于SpringBoot+Vue的付费自习室管理系统的详细设计和实现(源码+lw+部署文档+讲解等)
    文章目录前言项目运行截图技术框架后端采用SpringBoot框架前端框架Vue可行性分析系统测试系统测试的目的系统功能测试数据库表设计代码参考数据库脚本为什么选择我？获取源码前言......
  • 基于SpringBoot+Vue的单位考勤系统的详细设计和实现(源码+lw+部署文档+讲解等)
    文章目录前言项目运行截图技术框架后端采用SpringBoot框架前端框架Vue可行性分析系统测试系统测试的目的系统功能测试数据库表设计代码参考数据库脚本为什么选择我？获取源码前言......
  • Java 枚举（超详细讲解）
    Java语言的强大之处在于它提供了多种多样的类库，从而大大提高了程序的编程效率和质量。一、枚举事先考虑到某一变量可能的取值，尽可能用自然语言忠表意清楚的单词来表示它的每一个值，用这中思路定义的类型被称为枚举类型。枚举事由一组固定的常量组成的类型。在Java中每个枚......
  • C语言for循环详细讲解
    引言：在上一篇博客中，我们介绍了关于C语言的一种循环，while循环，并介绍了其中的关键字及其例题，在本片帖子，我们将引入一种新的循环方式，名为for循环，那么它与while循环又有哪些相似之处和不同之处呢？让我们一起来探索一下。一.for循环的基本架构for循环时三种循环中使用最多的for循......
  • 数据结构(五)——二叉树的遍历和线索二叉树
    5.3.二叉树的遍历和线索二叉树5.3.1_1二叉树的先中后序遍历遍历：按照某种次序把所有结点都访问一遍二叉树的递归特性：        ①要么是个空二叉树        ②要么就是由“根节点+左子树+右子树”组成的二叉树先序遍历：根左右（NLR）中序遍历：左根右（LNR）后序遍......
  • 中国电子学会（CEIT）2021年03月真题C语言软件编程等级考试三级（含详细解析答案）
    中国电子学会（CEIT）考评中心历届真题（含解析答案）C语言软件编程等级考试三级2021年03月编程题五道 总分:100分一、找和为K的两个元素（20分）在一个长度为n(n<1000)的整数序列中，判断是否存在某两个元素之和为k。时间限制:1000ms内存限制:65536kb输入第一行输入......
  • leedcode-二叉树的所有路径
    迭代法-深度优先搜索classSolution:defbinaryTreePaths(self,root:Optional[TreeNode])->List[str]:ifnotroot:return[]#如果根节点为空，直接返回空列表stack=[(root,str(root.val))]#初始化栈，栈中存储的是节点......
  • java多线程（超详细讲解）下篇
    本章继续讲多线程目录一、线程同步1、为什么需要线程同步二、如何实现线程同步1、同步代码块2、同步方法3、线程同步特征三、线程安全的类型1、ArrayList是常用的集合类型，它是否线程安全的呢？2、对比Hashtable和HashMap1、是否线程安全2、效率比较3、对比StringBuffe......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99