首页 > 其他分享 >数据结构:实现链式结构二叉树（Tree） 手把手带你入门数据结构~

数据结构:实现链式结构二叉树（Tree） 手把手带你入门数据结构~

时间：2024-09-26 19:18:47浏览次数：3  
标签：结点 遍历 return Tree BTNode 二叉树 数据结构 root

文章目录

前言

在这里插入图片描述

`

一、链式结构二叉树的概念

链式结构二叉树是一种使用链表（或指针）来表示二叉树的数据结构。与数组表示的二叉树不同，链式结构能够动态地管理内存，适合存储动态变化的数据。下面是链式结构二叉树的基本概念：

1. 定义

  • 二叉树：每个节点最多有两个子节点（左子节点和右子节点）。
  • 链式结构：每个节点通过指针链接到其子节点。

2. 节点结构

一个二叉树的节点通常包含三个部分：

  • 数据域：存储节点的数据（如整数、字符等）。
  • 左指针：指向左子节点的指针。
  • 右指针：指向右子节点的指针。

在C语言中，可以用以下结构体定义一个二叉树节点：

typedef struct TreeNode {
    int data;                  // 数据域
    struct TreeNode* left;    // 左子节点指针
    struct TreeNode* right;   // 右子节点指针
} TreeNode;

3. 操作

常见的操作包括：

  • 插入：将新节点插入到树中，通常根据某种顺序（如二叉搜索树的性质）。
  • 删除：从树中删除一个节点，需考虑不同情况（如叶子节点、只有一个子节点的节点、两个子节点的节点）。
  • 遍历：遍历树的节点，包括前序遍历、中序遍历和后序遍历。

4. 优势与劣势

  • 优势：

    • 动态内存分配，适合变化频繁的数据。
    • 节省空间：不需要为树的每一层预留空间。

  • 劣势：

    • 访问速度慢于数组，因为需要遍历指针。
    • 存储结构复杂，维护指针可能引入错误。

这种结构在许多算法和数据处理问题中非常有用，比如二叉搜索树、平衡树（如 AVL 树和红黑树）等。

二、链式结构二叉树的实现

1. 树结构的定义

前面说到树的定义，首先这个链表的结点要储存自身的数据，接下来每一个节点都有两个指针。一个指向它的左孩子，另一个指向它的右孩子。

有了这两个指针，树才能连接起来。
在这里插入图片描述

//定义二叉树的链式结构
//二叉树结点的结构

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;         //左孩子
	struct BinaryTreeNode* right;        //右孩子
}BTNode;

2. 树的遍历

（1）前序遍历

//前序遍历
void PreOrder(BTNode* root);

什么是前序遍历呢?
我们来看这一张图
在这里插入图片描述

对于1这个结点，他是当前的根节点，他拥有左右两个孩子 2，3

在这里插入图片描述

对于这个2结点当根节点，他也有他的两个孩子----4，NULL.

对于前序遍历来说，就是按照 根----左----右的顺序进行遍历。
如下图所示：
在这里插入图片描述

对于每个根节点来说，它的遍历方法都是 根----左----右，我们有时候可能认为遍历到一个结点的左孩子或者右孩子就要回去，其实是不对的。因为它的孩子的遍历方式也是 根----左----右。

因此，前序遍历是递归实现的。

//前序遍历 ------根左右
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

在这里插入图片描述

我们结合代码，再从函数栈帧的角度看一下递归具体的实现
在这里插入图片描述

（2）中序遍历

//中序遍历------左根右
void InOrder(BTNode* root);

不同于中序遍历，中序遍历的顺序是 左----根----右。
在这里插入图片描述

对于每一个节点，先遍历它的左孩子，在遍历它自己，最后遍历它的右孩子

如下图所示:
在这里插入图片描述

故中序遍历的顺序是4–2–1–3.

//中序遍历------左根右
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

（3）后序遍历

//后序遍历------左右根
void PostOrder(BTNode* root);

区别于前两种遍历方式，后序遍历的顺序是左----右---根
在这里插入图片描述

对于每一个节点，先遍历它的左孩子，在遍历它的右孩子，最后遍历它自己。

如下图所示:
在这里插入图片描述
故后序遍历的顺序为 4–2–3–1.

//后序遍历------左右根
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

3. 二叉树结点个数

// ⼆叉树结点个数
// 一个结点的个数等于其左右子树结点个数之和加上它本身
int BinaryTreeSize(BTNode* root);

二叉树的结点个数等于什么呢?
我们很容易就能想到一种方法：
定义一个count来计数，我们呢可以使用中序遍历，每遍历到一个有效的结点，就让count++最后返回count。

这样的方法可不可行呢?

int BinaryTreesize(BTNode* root,int size)
{
  if(root == NULL)
  {
    return 0;
  }
  size++;
  BinaryTreesize(root->left,size);
  BinaryTreesize(root->right,size);
  return size;
}

这样看似解决了问题，但实际上是不行的。
归根结底的原因是形参的传递不能改变实参。
在这里插入图片描述
那我们就有疑问了，既然你形参的改变不影响实参，那我直接传地址啊？
这样可不可行呢?
在这里插入图片描述
看似传了地址就解决了这个问题，但我们如果连续打印两次树中结点个数的话，你会发现节点个数又多加了一次。
这是因为地址的内容被我们改变，下次再用size的初始值就不是0了，需要我们手动释放。因此这种方法也不好。

那我们该怎么做呢?
可以这样想， 一个结点的个数等于其左右子树结点个数之和加上它本身。
在这里插入图片描述
只要分别找到每一个结点左子树和右子树结点之和，就是我们的答案。
将大事化小，当root为NULL的时候结束，不正是递归的思想吗?

// ⼆叉树结点个数
// 一个结点的个数等于其左右子树结点个数之和加上它本身
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

4. 二叉树叶子结点个数

// ⼆叉树叶⼦结点个数
// 二叉树叶子结点的个数等于二叉树左右子树叶子结点的个数之和
int BinaryTreeLeafSize(BTNode* root);

叶子结点就是树每一个分支最下层的结点，它没有子结点。

类比上述的方法，我们可以将二叉树叶子结点的个数看成二叉树左右子树叶子结点的个数之和。
在这里插入图片描述

// ⼆叉树叶⼦结点个数
// 二叉树叶子结点的个数等于二叉树左右子树叶子结点的个数之和
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	
	if (root->left == NULL && root->right == NULL)   //判断为是叶子结点
	{
		return 1;
	}

	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

5. 二叉树第k层结点个数

// ⼆叉树第k层结点个数
// ⼆叉树第k层结点个数等于左右子树第K层的结点个数和
// 注意是K == 1
int BinaryTreeLevelKSize(BTNode* root, int k);

第K层的结点个数可以看成左子树第K层和右子树第K层的结点数之和。

在这里插入图片描述

// ⼆叉树第k层结点个数等于左右子树第K层的结点个数和
// 注意是K == 1
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}

	if (k == 1)
	{
		return 1;
	}

	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

6. 二叉树的深度/高度

// ⼆叉树的深度/⾼度
// 二叉树的深度要分别比较左右子树最深的那一个
// 每一个结点的深度都等于其左右子树中最深的那个
int BinaryTreeDepth(BTNode* root);

二叉树的深度就是二叉树所有完整分支最长的那一个结点的个数。

二叉树的深度就等于左子树和右子树中最长的那一个。每一个结点都可以看成由他的左子树和右子树的最长深度，最终反回到root == NULL；

在这里插入图片描述

// ⼆叉树的深度/⾼度
// 二叉树的深度要分别比较左右子树最深的那一个
// 每一个结点的深度都等于其左右子树中最深的那个
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	int leftDepth = BinaryTreeDepth(root->left);
	int rightDepth = BinaryTreeDepth(root->right);

	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;

7. 二叉树查找值为x的结点

// ⼆叉树查找值为x的结点
// 左根右的方式找
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

我们使用中序遍历的方法递归树就好，直接找到等于x的位置，返回当前结点，没找到就返回NULL;

在这里插入图片描述

// ⼆叉树查找值为x的结点
// 左根右的方式找
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}

	if (root->data == x)
	{
		return root;
	}

	BTNode* leftFind = BinaryTreeFind(root->left, x);
	if (leftFind)
	{
		return leftFind;
	}

	BTNode* rightFind = BinaryTreeFind(root->right, x);
	if (rightFind)
	{
		return rightFind;
	}

	return NULL;
}

8. 二叉树的销毁

// ⼆叉树销毁
// 以左右根的方式销毁
// 根被销毁了因此要传二级指针
void BinaryTreeDestroy(BTNode** root);

首先，销毁要使用后序遍历的方法，因为如果根结点先被销毁，就一定找不到他的左右孩子了。

接下来一定要用二级指针，因为最终的树的根结点被销毁，我们传过来的root要改变，如果只用一级指针的话形参的改变是无法影响到实参的，因此必须要传一级指针的地址。

在这里插入图片描述

// ⼆叉树销毁
// 以左右根的方式销毁
// 根被销毁了因此要传二级指针
void BinaryTreeDestroy(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}

	BinaryTreeDestroy(&((*root)->left));
	BinaryTreeDestroy(&((*root)->right));
	free(*root);
	*root = NULL;
}

三、层序遍历

1. 层序遍历的概念

除了先序遍历、中序遍历、后序遍历外，还可以对⼆叉树进⾏层序遍历。设⼆叉树的根结点所在层数为1，层序遍历就是从所在⼆叉树的根结点出发，⾸先访问第⼀层的树根结点，然后从左到右访问第2层上的结点，接着是第三层的结点，以此类推，⾃上⽽下，⾃左⾄右逐层访问树的结点的过程就是层序遍历。

实现层序遍历需要额外借助数据结构：队列

2. 层序遍历的实现

实现层序遍历首先我们要有一个队列。

如下图：
在这里插入图片描述

第一步： 将树根结点插入队列。
在这里插入图片描述
第二步： 取出队头元素，如果它的左右子树不为空就将其按顺序入队。

在这里插入图片描述
第三步： 继续出队头元素，将出队列元素的左右孩子如果不为空让其入队。
在这里插入图片描述
第四步： 继续重复上一步骤，出队头元素，将出队列元素的左右孩子如果不为空让其入队。

此时4这个结点没有左右孩子，因此不用入队

在这里插入图片描述
第五步：重复上述步骤直到队列为空。

这里我们就完成了层序遍历，遍历顺序为 1----2----3----4

在这里插入图片描述

具体的实现为：

// 层序遍历
// 层序遍历需要借助队列，根出队，左右子树放入其中，直到一个左右子树都为空
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	//先插入根结点
	QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		printf("%d ", front->data);
		QueuePop(&q);

		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}

	QueueDestroy(&q);
}

四、判断二叉树是否为完全二叉树

如何判断二叉树是否是完全二叉树呢?

这里J桑直接给出方法：
同样需要借助队列，不过这次就算是结点的左右孩子无论它是否为NULL,都将它插入队列，循环出队列头，直到跳出第一个循环时，如果队列中所有的元素都是NULL,那么树就是完全二叉树，如果有不为NULL的元素，那他就不是完全二叉树。

第一步： 将树根结点插入队列。
在这里插入图片描述
第二步： 队头元素出队，取其左右孩子入队
在这里插入图片描述
第三步： 重复上述步骤
在这里插入图片描述
在这里插入图片描述
此时循环结束，队列中有非空元素，因此该树不是完全二叉树

具体实现为：

//判断二叉树是否为完全二叉树
//---借助队列，不管他的孩子是不是空都放到队列中，满二叉树结束时一定队列里全为空
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			break;
		}
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	//队列不一定为空
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

总结

到这里我们链式结构的二叉树(BinaryTree)就实现完成啦~

下面是完成代码：(记得写Queue哦~)

//Heap.c
#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 BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

// ⼆叉树叶⼦结点个数
// 二叉树叶子结点的个数等于二叉树左右子树叶子结点的个数之和
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	
	if (root->left == NULL && root->right == NULL)   //判断为是叶子结点
	{
		return 1;
	}

	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

// ⼆叉树第k层结点个数
// ⼆叉树第k层结点个数等于左右子树第K层的结点个数和
// 注意是K == 1
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}

	if (k == 1)
	{
		return 1;
	}

	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

// ⼆叉树的深度/⾼度
// 二叉树的深度要分别比较左右子树最深的那一个
// 每一个结点的深度都等于其左右子树中最深的那个
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	int leftDepth = BinaryTreeDepth(root->left);
	int rightDepth = BinaryTreeDepth(root->right);

	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

// ⼆叉树查找值为x的结点
// 左根右的方式找
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}

	if (root->data == x)
	{
		return root;
	}

	BTNode* leftFind = BinaryTreeFind(root->left, x);
	if (leftFind)
	{
		return leftFind;
	}

	BTNode* rightFind = BinaryTreeFind(root->right, x);
	if (rightFind)
	{
		return rightFind;
	}

	return NULL;
}

// ⼆叉树销毁
// 以左右根的方式销毁
// 根被销毁了因此要传二级指针
void BinaryTreeDestroy(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}

	BinaryTreeDestroy(&((*root)->left));
	BinaryTreeDestroy(&((*root)->right));
	free(*root);
	*root = NULL;
}

// 层序遍历
// 层序遍历需要借助队列，根出队，左右子树放入其中，直到一个左右子树都为空
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	//先插入根结点
	QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		printf("%d ", front->data);
		QueuePop(&q);

		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}

	QueueDestroy(&q);
}

//判断二叉树是否为完全二叉树
//---借助队列，不管他的孩子是不是空都放到队列中，满二叉树结束时一定队列里全为空
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			break;
		}
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	//队列不一定为空
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

//Heap.h
#pragma once

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


//定义二叉树的链式结构
//二叉树结点的结构

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;         //左孩子
	struct BinaryTreeNode* right;        //右孩子
}BTNode;


//前序遍历
void PreOrder(BTNode* root);

//中序遍历
void InOrder(BTNode* root);

//后序遍历 
void PostOrder(BTNode* root);

// ⼆叉树结点个数
int BinaryTreeSize(BTNode* root);

// ⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(BTNode* root);

// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);

//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root);

// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

// ⼆叉树销毁
void BinaryTreeDestroy(BTNode** root);

//层序遍历
void LevelOrder(BTNode* root);

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

//测试样例
#include"Tree.h"

BTNode* buyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->left = newnode->right = NULL;

	return newnode;
}

void test01()
{
	BTNode* node1 = buyNode(1);
	BTNode* node2 = buyNode(2);
	BTNode* node3 = buyNode(3);
	BTNode* node4 = buyNode(4);
	//BTNode* node5 = buyNode(5);
	//BTNode* node6 = buyNode(6);

	node1->left = node2;
	node1->right = node3;
	node2->right = node4;
	//node2->right = node5;
	//node3->left = node6;


	//PreOrder(node1);
	//printf("\n");
	//InOrder(node1);
	//printf("\n");
	//PostOrder(node1);

	//int size = 0;
	//BinaryTreeSize(node1, &size);
	//printf("size : %d\n", size);
	size = 0;
	//BinaryTreeSize(node1, &size);
	//printf("size : %d\n", size);

	//printf("size:%d\n", BinaryTreeSize(node1));
	//printf("size:%d\n", BinaryTreeSize(node1));

	//printf("size:%d\n", BinaryTreeSize(node1));
	//printf("leaf size: %d\n", BinaryTreeLeafSize(node1));
	//printf("第K层size : %d\n", BinaryTreeLevelKSize(node1, 2));
	//printf("depth/height:%d\n", BinaryTreeDepth(node1));

	//BTNode* find =BinaryTreeFind(node1, 33);
	//printf("%s\n", find == NULL ? "未找到！" : "找到了！");

	//LevelOrder(node1);

	bool ret = BinaryTreeComplete(node1);
	printf("%s\n", ret == false ? "不是完全二叉树" : "是完全二叉树");

	BinaryTreeDestroy(&node1);
}

int main()
{
	test01();
	return 0;
}

谢谢大家~

真相永远只有一个！

在这里插入图片描述

标签：结点,遍历,return,Tree,BTNode,二叉树,数据结构,root
From： https://blog.csdn.net/Jdxxwu/article/details/142471486

相关文章

  • Windows 使用 tree 命令
    Windows使用tree命令基本语法tree[drive:][path][/F][/A]参数说明[drive:][path]：指定要显示树结构的驱动器和目录。如果未指定路径，则使用当前目录。/F：显示每个文件夹中的文件名。/A：使用ASCII字符而不是扩展字符来显示链接子目录的线条。示例显示当前目录的树结......
  • Map 数据结构
    Map是一种键值队的集合，和对象Object类似。两者的区别：一、Map和Object的区别键的类型：在Map中，键可以是任何类型（包括对象、函数、undefined、NaN等等）；而在Object中，键只能是字符串或者符号。有序性：在Map中，键值对是按照插入（添加）的顺序排列的；而Object不能保证顺序二、创建：创......
  • 算法与数据结构——快速排序
    快速排序快速排序（quicksort）是一种基于分治策略的排序算法，运行高效，应用广泛。快速排序的核心操作是“哨兵划分”，其目标是：：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。具体流程如下：选取数组最左端元素作为基准数，初始化......
  • JAVA 数据结构与算法 队列的介绍与应用
    一、队列队列是一个有序列表，可以用数组或者链表来实现遵循先入先出的原则。当我们将数据存入队列时称为”addQueue”，addQueue的处理需要有两个步骤:思路分析：将尾指针往后移:rear+1，当front==rear【空】若尾指针rear小于队列的最大下标maxSize-1，则将数据存入rear所......
  • 【数据结构.总集篇】第一章 链表
    文章目录1.链表1.1线性表1.2顺序表1.3单链表链表简介单链表的介绍线性表的链式存储头节点概念为何引入头结点单链表的基本操作创建一个单链表初始化头插法尾插法删除操作打印总代码1.4单链表循环1.5双链表双链表的定义双链表上的操作初始化插入操作头插法尾插法......
  • TreeMap实现一致性hash
    usingSystem.Security.Cryptography;usingSystem.Text;namespaceConsoleApp7{internalclassProgram{staticvoidMain(string[]args){varservers=newList<string>{......
  • 算法与数据结构——简单排序算法（选择、冒泡、插入）
    简单排序算法时间复杂度均为O(n2)选择排序选择排序（selectionsort）的工作原理非常简单：开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序的区间的末尾。算法流程设数组长度为n，选择排序的算法流程如下。初识状态下，所有元素未排序，即未排序（索引）区间为[1,n-1]。选取......
  • 树状数组（Binary Indexed Tree, BIT）
    树状数组（BinaryIndexedTree,BIT）树状数组（BinaryIndexedTree,BIT），也称为FenwickTree，是一种用于高效处理数组前缀和查询和单点更新的数据结构。它能够在(O(\logn))时间内完成单点更新和前缀和查询操作。基本概念前缀和：给定一个数组a，前缀和prefix_sum[i]表示a[0]+......
  • PAT甲级-1115 Counting Nodes in a Binary Search Tree
    题目 题目大意给定节点个数，以及每个节点的值，要求构造一棵二叉排序（搜索）树，并按照规定格式输出最后一层和倒数第二层的节点个数。思路二叉排序树的构造方法是递归，但思路类似于二分查找。逐个将n个节点插入到二叉排序树中，插入完成也就构造完成了。插入节点时，如果该节点值大于......
  • 数据结构——广义表
    广义表的概念    广义表（又称列表Lists）是n>=0个元素a0，a1，...，an-1的有限序列，其中每一个ai可以是原子，或者是一个广义表。广义表和线性表的区别：线性表的元素是单一的类型，而广义表的元素可以是不同类型，其元素也可以是一个广义表（子表）。广义表通常记作:LS=(a1，a2，...，an）   ......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99