C++实现完全二叉树 |21xrx.com

C++实现完全二叉树

2023-07-12 02:51:46 深夜i 74 0

C++ 完全二叉树实现

完全二叉树是指在二叉树中，除了最后一层之外，其他层的节点都是满的，最后一层的节点都靠左排列。在计算机科学中，二叉树是一种重要的数据结构，它可以用于实现搜索、排序、编译器、文件系统等多种应用。本文将介绍如何使用C++语言实现完全二叉树。

在C++中，可以使用结构体定义节点类型，该节点包含左右孩子指针和节点值。如下所示：

struct Node 
{ 
  int value; 
  Node* left; 
  Node* right; 
};

在构建完全二叉树之前，需要确定二叉树的深度以及每层需要的节点数。对于深度为d的完全二叉树，若其高度为h，则其节点数为2^h-1。如果我们将最后一层节点从左到右编号为1,2,…k，则第i个节点的左儿子为2*i，右儿子为2*i+1。利用这个特性，我们就可以根据节点编号计算出左右儿子的编号，简化代码实现。

构造完全二叉树的步骤如下：

1. 根据给定的节点数，计算出完全二叉树的深度和每层需要的节点数。

2. 从第二层开始往下遍历，依次创建节点并赋值，根据节点编号计算出左右儿子的编号，连接左右儿子指针。

3. 返回根节点指针。

下面是用 C++ 实现完全二叉树的代码示例：

#include <iostream> 
#include <queue> 
using namespace std; 
//定义节点结构体 
struct Node 
{ 
  int value; 
  Node* left; 
  Node* right; 
}; 
//递归构造完全二叉树 
Node* ConstructCBT(int* vals, int idx, int n) 
{ 
  if (idx >= n) 
   
    return NULL; 
   
  else 
  { 
    Node* newNode = new Node(); 
    newNode->value = vals[idx]; 
    newNode->left = ConstructCBT(vals, 2 * idx + 1, n); 
    newNode->right = ConstructCBT(vals, 2 * idx + 2, n); 
    return newNode; 
  } 
} 
//层序遍历输出节点值 
void LevelOrderTraversal(Node* root) 
{ 
  queue<Node*> q; 
  q.push(root); 
  while (!q.empty()) 
  { 
    Node* node = q.front(); 
    cout << node->value << " "; 
    q.pop(); 
    if (node->left != NULL) 
    { 
      q.push(node->left); 
    } 
    if (node->right != NULL) 
    { 
      q.push(node->right); 
    } 
  } 
} 
int main() 
{ 
  int n; //输入节点数 
  cin >> n; 
  int* vals = new int[n]; //输入节点值 
  for (int i = 0; i < n; i++) 
  { 
    cin >> vals[i]; 
  } 
  Node* root = ConstructCBT(vals, 0, n); //构造完全二叉树 
  LevelOrderTraversal(root); //层序遍历 
  cout << endl; 
  delete[] vals; 
  return 0; 
}

通过以上代码，输入一组节点值，即可构建出一棵完全二叉树，并实现基本的遍历输出。

综上所述，使用C++语言实现完全二叉树非常方便，代码简洁而高效，适用于各种计算机科学问题的解决。

上一篇: idea打包java可执行jar包

下一篇: C++线程同步技巧

评论区

相似文章