首页 > 其他分享 >解锁二叉树的魅力：链式实现详解

解锁二叉树的魅力：链式实现详解

时间：2024-10-18 12:50:11浏览次数：9  
标签：return 解锁 BTNode 二叉树 链式 NULL root 节点

前言

二叉树的简介及顺序实现

引言

在数据结构的浩瀚星空中，二叉树如同一颗璀璨的明珠，其优雅的结构和强大的功能使其成为计算机科学中不可或缺的工具。从数据库索引到编译器的语法树，二叉树以其独特的方式支撑着许多核心算法与数据处理。本文将深入探讨如何使用C语言实现二叉树的链式结构，并详细讲解各个部分的实现。

一、二叉树的结构

1.1结构

二叉树（binary tree） 是一种非线性数据结构，代表“祖先”与“后代”之间的派生关系，体现了“一分为二” 的分治逻辑。与链表类似，二叉树的基本单元是节点，每个节点包含值、左子节点引用和右子节点引用。 
//二叉树节点结构
typedef int DataType;
typedef struct BinaryTreeNode
{
	int data;//值域
	struct BinaryTreeNode* left;//指向当前节点左孩子
	struct BinaryTreeNode* right;//指向当前节点右孩子
}BTNode;
每个节点都有两个引用（指针），分别指向 左子节点（left‑child node） 和 右子节点（right‑child node） ，该节点被称为这两个子节点的 父节点（parent node） 。当给定一个二叉树的节点时，我们将该节点的左子节点及其以下节点形成的树称为该节点的 左子树（left subtree） ，同理可得 右子树（right subtree） 。

1.2链式实现的优势

选择链式实现二叉树有几个显著的优点：

  1. 动态大小：链式结构能够根据需要动态分配内存，避免了固定大小的限制，适合处理不确定数量的数据。
  2. 节省空间：链式结构只为实际存在的节点分配内存，减少了空间浪费，相比数组实现更加高效。
  3. 简化操作：插入和删除操作无需移动其他元素，操作更为高效，使得二叉树在频繁变动的数据环境中表现出色。

二、二叉树的基本操作

⼆叉树的创建⽅式⽐较复杂，为了更好的步⼊到⼆叉树内容中，我们先⼿动创建⼀棵链式⼆叉树： 
BTNode* buyNode(DataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->left=newnode->right = NULL;

}
BTNode* CreateTree()
{
	BTNode* n1 = buyNode(1);
	BTNode* n2 = buyNode(2);
	BTNode* n3 = buyNode(3);
	BTNode* n4 = buyNode(4);
	BTNode* n5 = buyNode(5);
	BTNode* n6 = buyNode(6);
	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n4->left = n5;
	n4->right = n6;
	return n1;
}

2.1前序遍历

前序遍历是一种深度优先遍历方式，按照“根节点 -> 左子树 -> 右子树”的顺序访问树中的节点。它是树结构中非常重要的一种遍历方式，常用于复制树结构和表达式树的解析等场景。

访问顺序

  1. 首先访问当前节点（根节点）。
  2. 然后递归访问左子树。
  3. 最后递归访问右子树。

应用场景

  • 生成树的序列化表示。
  • 复制树结构。
  • 在表达式树中用于构建前缀表达式。

递归实现：

//前序遍历
//访问优先级：根节点 -> 左子树 -> 右子树
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

在这个实现中，我们首先检查当前节点是否为空。如果不为空，我们打印当前节点的数据，然后递归地访问左子节点和右子节点。这种顺序确保了根节点总是最早被访问，对于许多应用场景非常有效。

2.2中序遍历

中序遍历是一种深度优先遍历方式，按照“左子树 -> 根节点 -> 右子树”的顺序访问树中的节点。它在树结构中扮演着重要的角色，常用于生成排序的节点序列以及表达式树的解析。

访问顺序

  1. 首先递归访问左子树。
  2. 然后访问当前节点（根节点）。
  3. 最后递归访问右子树。

应用场景

  • 生成有序的节点序列。
  • 在表达式树中用于构建中缀表达式。

递归实现：

//中序遍历
//访问优先级：左子树 -> 根节点 -> 右子树
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

在这个实现中，我们首先检查当前节点是否为空。如果不为空，我们递归地访问左子节点，接着打印当前节点的数据，最后递归地访问右子节点。这种顺序确保了我们在访问节点时能够得到有序的结果。

2.3后序遍历

后序遍历是一种深度优先遍历方式，按照“左子树 -> 右子树 -> 根节点”的顺序访问树中的节点。这种遍历方式在某些情况下非常有用，尤其是在需要先处理子节点再处理父节点的场景中。

访问顺序

  1. 首先递归访问左子树。
  2. 然后递归访问右子树。
  3. 最后访问当前节点（根节点）。

应用场景

  • 计算树的高度或大小。
  • 删除树结构时，确保先删除子节点。
  • 在表达式树中用于构建后缀表达式。

递归实现：

//后序遍历
//访问优先级：左子树 -> 右子树 -> 根节点
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

在这个实现中，我们首先检查当前节点是否为空。如果不为空，我们递归地访问左子节点，然后递归地访问右子节点，最后打印当前节点的数据。这种顺序确保了我们在访问节点时能够正确处理所有子节点之后再处理父节点，适用于需要反向处理的场景。

2.4层序遍历

层序遍历是一种广度优先遍历方式，按照“从上到下、从左到右”的顺序访问树中的节点。它在需要逐层处理节点的场景中非常有用，例如按层打印树或计算树的深度。

步骤如下：
1.初始化一个队列，将根节点入队。
2.当队列不为空，重复以下操作：

  • 从队列中出队一个节点并访问（打印或记录）。
  • 将该节点的左子节点和右子节点（如果存在）入队。

 代码实现：

//层序遍历 借助数据结构--队列
void LevelOrder(BTNode* root)
{
	QU q;//创建一个队列
	QueueInit(&q);
	QueuePush(&q, root);//根节点入队，成为队头
	while (!QueueEmpty(&q))//队列不为空
	{
		//取队头，打印
		BTNode*Qhead=QueueFront(&q);
		printf("%d ", Qhead->data);
		QueuePop(&q);//队头出队
		//队头节点左孩子入队
		if (Qhead->left)
		{
			QueuePush(&q, Qhead->left);
		}
		//队头节点右孩子入队
		if (Qhead->right)
		{
			QueuePush(&q, Qhead->right);
		}
	}
	QueueInit(&q);
	QueueDestroy(&q);
}

2.5求二叉树节点个数

步骤如下：

1.如果当前节点为空，返回0（没有节点）。

2.如果当前节点不为空，返回1（当前节点）加上左子树和右子树的节点个数。

 代码实现：

int BTSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 	BTSize(root->left) + BTSize(root->right) + 1;
}

2.6求二叉树叶子节点数

  • 叶子节点：没有子节点的节点。
  • 非叶子节点：至少有一个子节点的节点。

步骤如下：

1.如果当前节点为空，返回0（没有叶子节点）。

2.如果当前节点是叶子节点（左右子节点均为空），返回1。

3.如果当前节点不是叶子节点，递归计算左子树和右子树的叶子节点个数，并将结果相加。

 代码实现：

//⼆叉树叶子结点个数 叶子节点：度为0的节点
int BTLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BTLeafSize(root->left) + BTLeafSize(root->right);
}

2.7求⼆叉树第k层结点个数 

步骤如下：

1.如果当前节点为空，返回0。

2.如果当前层数等于k，返回1。

3.如果当前层数小于k，递归计算左子树和右子树第k层的节点个数。

代码实现：

//⼆叉树第k层结点个数 
int BTLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BTLevelKSize(root->left, k - 1) + BTLevelKSize(root->right, k - 1);
}

2.8求⼆叉树的高度

步骤如下：

1.如果当前节点为空，返回0（树的高度为0）。

2.递归计算左子树和右子树的高度。

3.返回左子树和右子树高度中的较大值，加1（表示当前节点的高度）。

代码实现：

//⼆叉树的深度/高度
int BTDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//返回左右子树最深的那个
	return BTDepth(root->left) > BTDepth(root->right) ? BTDepth(root->left) + 1 : BTDepth(root->right) + 1;
}

2.9二叉树查值

步骤如下：

1.如果当前节点为空，返回 NULL（未找到）。

2.如果当前节点的值等于 x，返回当前节点。

3.如果当前节点的值不等于 x，递归查找左子树和右子树。

4.如果在左子树中找到，返回该节点；否则，继续在右子树中查找。

代码实现：

//⼆叉树查找值为x的结点 
BTNode* BTFind(BTNode* root, DataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* leftFind=BTFind(root->left, x);//左子树中找
	if (leftFind)
	{
		return leftFind;//左子树找到了，返回
	}
	BTNode* rightFind=BTFind(root->right, x);//右子树中找
	if (rightFind)
	{
		return rightFind;//右子树找到了，返回
	}
	return NULL;
}

2.9判断完全二叉树

方法概述

  1. 队列初始化：使用队列来进行层序遍历。
  2. 遍历过程：
    • 将根节点入队，开始遍历。
    • 从队列中出队节点，检查其是否为空。
    • 对于每个非空节点，将其左右孩子入队。
    • 一旦遇到空节点，标记后续节点必须都是空节点。
  3. 最终验证：继续遍历队列，确保所有后续节点均为空。

代码如下：

//判断二叉树是否为完全二叉树--借助队列
bool BTComplete(BTNode* root)
{
	QU q;//创建一个队列
	QueueInit(&q);
	QueuePush(&q, root);//根节点入队，成为队头
	while (!QueueEmpty(&q))//队列不为空
	{
		//取队头出队
		BTNode* Qhead = QueueFront(&q);
		QueuePop(&q);
		if (Qhead == NULL)
		{
			break;
		}
		//左右孩子都入队
		QueuePush(&q, Qhead->left);
		QueuePush(&q, Qhead->right);
	}
	//空节点入对头是跳出循环，此时队列不一定为空
	while (!QueueEmpty(&q))//队列不为空
	{
		//取队头，出队
		BTNode* Qhead = QueueFront(&q);
		QueuePop(&q);
		if (Qhead != NULL)
		{
			return false;//此时取到非空节点说明不是完全二叉树
		}
	}
	QueueDestroy(&q);
	return true;//是完全二叉树
}

2.10二叉树销毁

代码实现:

//⼆叉树销毁 
//后序遍历销毁：先销毁左子树，再右子树，最后根节点
void BTDestroy(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BTDestory(&((*root)->left));
	BTDestory(&((*root)->right));
	free(*root);
	*root = NULL;
}
//层序遍历 借助数据结构--队列
void LevelOrder(BTNode* root)
{
	QU q;//创建一个队列
	QueueInit(&q);
	QueuePush(&q, root);//根节点入队，成为队头
	while (!QueueEmpty(&q))//队列不为空
	{
		//取队头，打印
		BTNode*Qhead=QueueFront(&q);
		printf("%d ", Qhead->data);
		QueuePop(&q);//队头出队
		//队头节点左孩子入队
		if (Qhead->left)
		{
			QueuePush(&q, Qhead->left);
		}
		//队头节点右孩子入队
		if (Qhead->right)
		{
			QueuePush(&q, Qhead->right);
		}
	}
	QueueInit(&q);
	QueueDestroy(&q);
}

三、完整代码

Queue.h

队列的声明

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//typedef int DataType;
typedef struct BinaryTreeNode* QDataType;
//定义节点结构体
typedef struct Node
{
	QDataType data;//数据域
	struct Node* next;//指针域
}Node;
//定义队列结构体
typedef struct Queue
{
	Node* phead;//队头
	Node* ptail;//队尾
	int size;//队列长度
}QU;
//初始化队列 
void QueueInit(QU* p);
//入队列，队尾
void QueuePush(QU* p, QDataType x);
//队列判空 
bool QueueEmpty(QU* p);
//出队列，队头 
void QueuePop(QU* p);
//取队头数据 
QDataType QueueFront(QU* p);
//取队尾数据 
QDataType QueueBack(QU* p);
//队列长度
int QueueSize(QU* p);
//销毁队列 
void QueueDestroy(QU* p);

Queue.c 

队列的定义

#define _CRT_SECURE_NO_WARNINGS
#include"Queue.h"
// 初始化队列
void QueueInit(QU* p)
{
	assert(p);
	p->phead = p->ptail = NULL; // 头尾指针初始化为 NULL
	p->size = 0; // 队列大小初始化为 0
}

// 创建新节点
Node* CreateNode(QDataType x)
{
	Node* newnode = (Node*)malloc(sizeof(Node));
	if (newnode == NULL) {
		perror("malloc fail");
		exit(1); // 分配失败，退出程序
	}
	newnode->data = x; // 设置节点数据
	newnode->next = NULL; // 初始化后继指针为 NULL
	return newnode; // 返回新节点
}

// 入队操作（从队尾插入）
void QueuePush(QU* p, QDataType x)
{
	assert(p);
	Node* newnode = CreateNode(x);
	if (p->phead == NULL) // 队列为空时
	{
		p->phead = p->ptail = newnode; // 头尾指针都指向新节点
	}
	else // 队列不为空时
	{
		p->ptail->next = newnode; // 尾节点的 next 指向新节点
		p->ptail = newnode; // 更新尾指针为新节点
	}
	++p->size; // 队列大小加 1
}

// 判断队列是否为空
bool QueueEmpty(QU* p)
{
	assert(p);
	return p->phead == NULL; // 头指针为 NULL 表示队列为空
}

// 出队操作（从队头删除）
void QueuePop(QU* p)
{
	assert(p);
	assert(!QueueEmpty(p)); // 确保队列不为空
	if (p->phead == p->ptail) // 只有一个元素时
	{
		free(p->phead); // 释放头节点
		p->phead = p->ptail = NULL; // 更新头尾指针为 NULL
	}
	else
	{
		Node* del = p->phead; // 保存要删除的节点
		p->phead = p->phead->next; // 更新头指针为下一个节点
		free(del); // 释放删除的节点
	}
	--p->size; // 队列大小减 1
}

// 获取队头数据
QDataType QueueFront(QU* p)
{
	assert(p);
	assert(!QueueEmpty(p)); // 确保队列不为空
	return p->phead->data; // 返回头节点的数据
}

// 获取队尾数据
QDataType QueueBack(QU* p)
{
	assert(p);
	assert(!QueueEmpty(p)); // 确保队列不为空
	return p->ptail->data; // 返回尾节点的数据
}

// 获取队列长度
int QueueSize(QU* p)
{
	assert(p);
	return p->size; // 返回队列的大小
}

// 销毁队列
void QueueDestroy(QU* p)
{
	assert(p);
	Node* pcur = p->phead;
	while (pcur) // 遍历所有节点并释放内存
	{
		Node* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	p->phead = p->ptail = NULL; // 头尾指针置为 NULL
	p->size = 0; // 队列大小置为 0
}

Tree.h

二叉树的声明

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
//定义二叉树链式结构
//二叉树节点结构
typedef int DataType;
typedef struct BinaryTreeNode
{
	int data;//值域
	struct BinaryTreeNode* left;//指向当前节点左孩子
	struct BinaryTreeNode* right;//指向当前节点右孩子
}BTNode;
//前序遍历--根左右
void PreOrder(BTNode* root);
//中序遍历--左根右
void InOrder(BTNode* root);
//二叉树结点个数 
int BTSize(BTNode* root); 
//二叉树叶子结点个数 
int BTLeafSize(BTNode* root);
//二叉树第k层结点个数 
int BTLevelKSize(BTNode* root, int k); 
//二叉树的深度/高度
int BTDepth(BTNode* root); 
//二叉树查找值为x的结点 
BTNode* BTFind(BTNode* root, DataType x); 
//二叉树销毁 
void BTDestroy(BTNode** root);
//层序遍历--借助队列
void LevelOrder(BTNode* root);
//判断二叉树是否为完全二叉树--借助队列
bool BTComplete(BTNode* root);

Tree.c

二叉树的实现

#define _CRT_SECURE_NO_WARNINGS
#include"Tree.h"
#include"Queue.h"
//前序遍历
//访问优先级：根节点 -> 左子树 -> 右子树
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}
//中序遍历
//访问优先级：左子树 -> 根节点 -> 右子树
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}
//后序遍历
//访问优先级：左子树 -> 右子树 -> 根节点
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}
//⼆叉树结点个数 
int BTSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 	BTSize(root->left) + BTSize(root->right) + 1;
}
//⼆叉树叶子结点个数 叶子节点：度为0的节点
int BTLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BTLeafSize(root->left) + BTLeafSize(root->right);
}
//⼆叉树第k层结点个数 
int BTLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BTLevelKSize(root->left, k - 1) + BTLevelKSize(root->right, k - 1);
}
//⼆叉树的深度/高度
int BTDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//返回左右子树最深的那个
	return BTDepth(root->left) > BTDepth(root->right) ? BTDepth(root->left) + 1 : BTDepth(root->right) + 1;
}
//⼆叉树查找值为x的结点 
BTNode* BTFind(BTNode* root, DataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* leftFind=BTFind(root->left, x);//左子树中找
	if (leftFind)
	{
		return leftFind;//左子树找到了，返回
	}
	BTNode* rightFind=BTFind(root->right, x);//右子树中找
	if (rightFind)
	{
		return rightFind;//右子树找到了，返回
	}
	return NULL;
}
//⼆叉树销毁 
//后序遍历销毁：先销毁左子树，再右子树，最后根节点
void BTDestroy(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BTDestroy(&((*root)->left));
	BTDestroy(&((*root)->right));
	free(*root);
	*root = NULL;
}
//层序遍历 借助数据结构--队列
void LevelOrder(BTNode* root)
{
	QU q;//创建一个队列
	QueueInit(&q);
	QueuePush(&q, root);//根节点入队，成为队头
	while (!QueueEmpty(&q))//队列不为空
	{
		//取队头，打印
		BTNode*Qhead=QueueFront(&q);
		printf("%d ", Qhead->data);
		QueuePop(&q);//队头出队
		//队头节点左孩子入队
		if (Qhead->left)
		{
			QueuePush(&q, Qhead->left);
		}
		//队头节点右孩子入队
		if (Qhead->right)
		{
			QueuePush(&q, Qhead->right);
		}
	}
	QueueInit(&q);
	QueueDestroy(&q);
}
//判断二叉树是否为完全二叉树--借助队列
bool BTComplete(BTNode* root)
{
	QU q;//创建一个队列
	QueueInit(&q);
	QueuePush(&q, root);//根节点入队，成为队头
	while (!QueueEmpty(&q))//队列不为空
	{
		//取队头出队
		BTNode* Qhead = QueueFront(&q);
		QueuePop(&q);
		if (Qhead == NULL)
		{
			break;
		}
		//左右孩子都入队
		QueuePush(&q, Qhead->left);
		QueuePush(&q, Qhead->right);
	}
	//空节点入对头是跳出循环，此时队列不一定为空
	while (!QueueEmpty(&q))//队列不为空
	{
		//取队头，出队
		BTNode* Qhead = QueueFront(&q);
		QueuePop(&q);
		if (Qhead != NULL)
		{
			return false;//此时取到非空节点说明不是完全二叉树
		}
	}
	QueueDestroy(&q);
	return true;//是完全二叉树
}

main.c

测试

#define _CRT_SECURE_NO_WARNINGS
#include"Tree.h"
BTNode* buyNode(DataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->left=newnode->right = NULL;

}
BTNode* CreateTree()
{
	BTNode* n1 = buyNode(1);
	BTNode* n2 = buyNode(2);
	BTNode* n3 = buyNode(3);
	BTNode* n4 = buyNode(4);
	BTNode* n5 = buyNode(5);
	BTNode* n6 = buyNode(6);
	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n4->left = n5;
	n4->right = n6;
	return n1;
}
void Test()
{
	BTNode* n1 = CreateTree();
	printf("\n前序遍历：");
	PreOrder(n1);
	printf("\n中序遍历：");
	InOrder(n1);
	printf("\n后续遍历：");
	PostOrder(n1);
	//打印节点数
	printf("\nsize=%d\n", BTSize(n1));
	//打印叶子节点个数
	printf("left_size=%d\n", BTLeafSize(n1));
	int k = 2;
	printf("第%d层节点个数：%d\n", k,BTLevelKSize(n1,k));
	printf("Depth:%d\n", BTDepth(n1));
	//查找数字4
	BTNode* find = BTFind(n1, 4);
	printf("%s\n", find == NULL ? "未找到" : "找到了！");
	printf("\n层序遍历：");
	LevelOrder(n1);
	bool ret= BTComplete(n1);
	printf("\n%s\n",ret==false ?"不是完全二叉树" : "是完全二叉树！");
	BTDestroy(&n1);
}
int main()
{
	Test();
	return 0;
}

结果如下：

四、总结

在这篇文章中，我们深入探讨了二叉树的链式结构及其在C语言中的实现。我们首先了解了二叉树的基本结构及其动态大小的优势，然后介绍了多种遍历方式，包括前序、中序、后序和层序遍历，以及相关的节点统计函数。接着，文章详细阐述了如何判断二叉树是否为完全二叉树，并提供了二叉树的销毁函数。最后，通过实例测试了这些操作，展示了二叉树在数据处理中的重要性和灵活性，为读者提供了全面的理解和实用的代码实现。 

标签：return,解锁,BTNode,二叉树,链式,NULL,root,节点
From： https://blog.csdn.net/2302_81410974/article/details/142862359

相关文章

  • 111. 二叉树的最小深度【二叉树】
    文章目录111.二叉树的最小深度解题思路111.二叉树的最小深度111.二叉树的最小深度给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明：叶子节点是指没有子节点的节点。示例1：输入：root=[3,9,20,null,null,15,7]......
  • 二叉树的中序遍历
    给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。示例1：输入：root=[1,null,2,3]输出：[1,3,2]示例2：输入：root=[]输出：[]示例3：输入：root=[1]输出：[1]提示：树中节点数目在范围 [0,100] 内-100<=Node.val<=100进阶: 递归算法很简单，你可以通......
  • 109. 有序链表转换二叉搜索树【二叉树】
    文章目录109.有序链表转换二叉搜索树解题思路Go代码109.有序链表转换二叉搜索树109.有序链表转换二叉搜索树给定一个单链表的头节点head，其中的元素按升序排序，将其转换为平衡二叉搜索树。平衡二叉树是指该树所有节点的左右子树的深度相差不超过1。示例......
  • 七、二叉树之链式结构(递归）
    一、前序：前面章节所说二叉树的结构其实是递归的，为什么这样说呢？根节点有左右子树，根节点的左右孩子又有左右子树，以此类推，直到叶子节点，它的左右子树为NULL，开始返回。所以，我们把它分成一个又一个的子树来分析。因此，它的结构是递归的。因为一开始接触二叉树，还不是熟悉，我们先来手动......
  • Java数据结构二叉树面试题精华(画图详解)
    前言：    针对二叉树，因为涉及到递归，需要跟多的练习强化递归的思想，其中也包括需要画图理解一些想不通的问题来提升自己！    一下面这些题为例，一起来提升自己的逻辑思维能力！(可能其中一些题已经写过，但是希望能再写一遍有助于提高代码能力)相同的树：      ......
  • 手撸二叉树——AVL平衡二叉树
    还记得上一篇中我们遗留的问题吗？我们再简要回顾一下，现在有一颗空的二叉查找树，我们分别插入1，2，3，4，5，五个节点，那么得到的树是什么样子呢？这个不难想象，二叉树如下：树的高度是4，并且数据结构上和链表没有区别，查找性能也和链表一致。如果我们将树的结构改变一下呢？比如改成下面的树结构，那......
  • 树、森林与二叉树的转换
    一、引言与问题引出        在计算机科学的数据结构领域中，树、森林与二叉树之间的转换具有重要意义。在实际研究过程中，我们常常会发现树的结构过于复杂，而二叉树相对简单。例如，普通的树形结构使用程序语言描述起来相对复杂，而二叉树则相对容易。一颗普通的树可以通过孩......
  • 【Echarts 实战指南】解锁动态历史曲线之谜
    在工作中，大家是否曾遇到过这样一种需求呢？需获取设备最近10分钟的历史数据。设备实时数据每2秒推送一次，且要把历史数据曲线变成动态变化的状态。倘若设备最近10分钟的历史数据为20个点，那么现在每2秒就要将最前面的点删除，同时推送最新的数据。一旦数据发生变化，便加......
  • 05 线性结构——队列（特性、入队与出队、顺序队列和链式队列、顺序队列的“假溢出”问
    目录1队列的基本概念1.1定义1.2队列的组成部分1.3空队列1.4操作流程 1.4.1添加元素（入队）1.4.2删除元素（出队）2队列的存储结构2.1顺序队列2.2链式队列3 顺序队列中的“假溢出”问题及解决方案3.1问题描述3.2解决方案方法1：元素左移法方法2：循环队列4......
  • 代码随想录|二叉树part 03
    求普通二叉树的节点数量要点：将子节点的个数记录到父节点，使用后序遍历classSolution{public:intmaxDepth(TreeNode*root){if(root==NULL)return0;intleft1=maxDepth(root->left);intright1=maxDepth(root->right);intnum=......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99