自学内容网 自学内容网
自学内容网 > 正文

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

🕗 发布于 2024-11-26 07:41 数据结构  算法  
#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;
}
  • 此函数用于计算完全二叉树中指定节点（由 size 索引确定）所在的层次。根据公式先通过对数运算计算出一个初步结果（以 2 为底的对数，通过换底公式 log(b) / log(a) 实现），然后使用 ceil() 函数对结果进行向上取整，最后返回该节点所在的层次值。

原文地址：https://blog.csdn.net/nofaluse/article/details/143992050

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024