当前位置：首页 > article >正文

完全二叉树的基本操作（顺序存储）

article 2025/2/23 1:02:49

#include<iostream>
#include<math.h>
using namespace std;

#define MaxSize 100
struct TreeNode {
	int value;
	bool isEmpty;//判断该节点是否为空
}t[MaxSize];

/**
*定义一个长度位MaxSize的数组，按照从上到下，
*从左到右的方式依次存储完全二叉树的各个节点
*/
//TreeNode t[MaxSize];

//初始化二叉树：注意从数组下标来进行存储
void InitTreeNode(TreeNode * t) {
	for (int i = 0; i < MaxSize; i++) {
		t[i].isEmpty = true;
	}
}           

/*
i的左孩子——2i
i的右孩子——2i+1
i的父节点——【i/2】
i所在的层次——log2的（n+1）向上取整  或者  log2的n（向下取整）
*/

//寻找i的左节点的数据
bool FindLeft(TreeNode* t, int size, int &value) {
	if (size * 2 > 100 - 1||t[size*2].isEmpty==true) {
		return false;
	}
	value = t[size*2].value;
	return true;
}

//寻找i的右节点的数据
bool FindRight(TreeNode* t, int size, int& value) {
	if (size * 2 +1> 100 - 1 || t[size*2+1].isEmpty == true) {
		return false;
	}
	value = t[size*2+1].value;
	return true;
}

//寻找i的父节点的数据
bool FindFather(TreeNode* t, int size, int& value) {
	if ( t[size /2].isEmpty == true) {
		return false;
	}
	value = t[size/2].value;
	return true;
}

//寻找i的层次
double FindHigh(TreeNode* t, int size) {
	//i所在的层次——log2的（n+1）向上取整
	double a = 2;
	double b = size + 1;
	double result = log(b) / log(a);
	//进行向上取整
	result = ceil(result);
	return result;
}

int main() {
	return 0;
}

一、整体功能概述

这段 C++ 代码主要实现了与完全二叉树相关的一些基本操作，包括二叉树节点结构体的定义、二叉树的初始化以及对完全二叉树中节点的左孩子、右孩子、父节点数据的查找，还有对节点所在层次的计算等功能。

二、代码结构分析

1. 头文件和命名空间

#include<iostream>
#include<math.h>
using namespace std;

包含了 <iostream> 头文件用于输入输出操作，<math.h> 头文件用于数学运算（如对数运算用于计算节点层次）。使用了 using namespace std;，这种方式虽然方便但在大型项目中可能会导致命名冲突，更推荐按需使用 std:: 限定符。

2. 二叉树节点结构体定义

#define MaxSize 100
struct TreeNode {
    int value;
    bool isEmpty;
}t[MaxSize];

通过宏定义 MaxSize 确定了二叉树节点数组的最大容量为 100。定义了 TreeNode 结构体，包含一个整型的 value 字段用于存储节点的值，以及一个布尔型的 isEmpty 字段用于判断该节点是否为空。同时声明了一个名为 t 的 TreeNode 类型数组，用于存储完全二叉树的各个节点。

3. 二叉树初始化函数

//初始化二叉树：注意从数组下标来进行存储
void InitTreeNode(TreeNode * t) {
    for (int i = 0; i < MaxSize; i++) {
        t[i].isEmpty = true;
    }
}

该函数接受一个指向 TreeNode 数组的指针 t，通过循环将数组中每个节点的 isEmpty 字段设置为 true，表示初始时所有节点都为空，为后续插入节点等操作做好准备。

4. 查找节点相关函数

查找左节点数据函数

//寻找i的左节点的数据
bool FindLeft(TreeNode* t, int size, int &value) {
    if (size * 2 > 100 - 1 || t[size * 2].isEmpty == true) {
        return false;
    }
    value = t[size * 2].value;
    return true;
}

此函数用于查找完全二叉树中指定节点（由 size 索引确定）的左孩子节点的数据。首先判断左孩子节点的索引是否超出范围（通过 size * 2 > 100 - 1 判断）或者左孩子节点是否为空（通过 t[size * 2].isEmpty == true 判断），如果满足其中一个条件则返回 false。否则，将左孩子节点的值赋给传入的引用参数 value，并返回 true。

查找右节点数据函数

//寻找i的右节点的数据
bool FindRight(TreeNode* t, int size, int &value) {
    if (size * 2 + 1 > 100 - 1 || t[size * 2 + 1].isEmpty == true) {
    return false;
    }
    value = t[size * 2 + 1].value;
    return true;
}

与查找左节点数据函数类似，用于查找指定节点的右孩子节点的数据。先进行索引范围和节点是否为空的判断，满足条件则返回 false，否则赋值并返回 true。

查找父节点数据函数

//寻找i的父节点的数据
bool FindFather(TreeNode* t, intsize, int &value) {
    if (t[size / 2].isEmpty == true) {
        return false;
    }
    value = t[size / 2].value;
    return true;
}

该函数用于查找指定节点的父节点的数据。判断父节点是否为空（通过 t[size / 2].isEmpty == true 判断），为空则返回 false，否则赋值并返回 true。

5. 计算节点层次函数

//寻找i的层次
double FindHigh(TreeNode* t, int size) {
    //i所在的层次——log2的（n+1）向上取整
    double a = 2;
    double b = size + 1;
    double result = log(b) / log(a);
    //进行向上取整
    result = ceil(result);
    return result;
}