数据结构之判断完全二叉树详解与示例（C，C++）_业界新闻

发布时间:2024-07-28 22:04

阅读量:0

文章目录

完全二叉树是一种特殊的二叉树，它满足以下两个条件：

每一层（除了最后一层）都被严格地填充了节点。
最后一层的节点都尽可能地靠左对齐。
本文将详细介绍如何判断一个二叉树是否为完全二叉树，并提供C和C++的实现示例。

一、判断完全二叉树的思路

我们可以通过层序遍历（广度优先搜索）的方式来判断一个二叉树是否为完全二叉树。在层序遍历过程中，我们遵循以下步骤：

如果当前节点有左子树和右子树，则将它们分别加入队列。
如果当前节点只有左子树，没有右子树，则将左子树加入队列，并在之后的遍历中，所有节点都必须是叶子节点。
如果当前节点没有子树，则该节点之后的所有节点都必须是叶子节点。
如果在遍历过程中，出现了不符合上述条件的节点，那么该二叉树就不是完全二叉树。

二、C语言实现

以下是C语言的实现示例：

#include <stdio.h> #include <stdlib.h>  // 定义二叉树节点结构体 typedef struct TreeNode {     int val;     struct TreeNode *left;     struct TreeNode *right; } TreeNode;  // 判断二叉树是否为完全二叉树 int isCompleteBinaryTree(TreeNode *root) {     if (root == NULL) return 1; // 空树也是完全二叉树      // 初始化队列     TreeNode *queue[10000];     int front = 0, rear = 0;     queue[rear++] = root;      // 开始层序遍历     while (front < rear) {         TreeNode *cur = queue[front++];          // 如果遇到空节点，判断后续节点是否都是空节点         if (cur == NULL) {             while (front < rear) {                 if (queue[front] != NULL) return 0;                 front++;             }         } else {             // 将左右子树加入队列             queue[rear++] = cur->left;             queue[rear++] = cur->right;         }     }      return 1; // 遍历完成，没有发现不符合条件的节点，是完全二叉树 }  // 创建节点 TreeNode* createNode(int val) {     TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));     node->val = val;     node->left = NULL;     node->right = NULL;     return node; }  int main() {     // 创建一个示例二叉树     TreeNode *root = createNode(1);     root->left = createNode(2);     root->right = createNode(3);     root->left->left = createNode(4);     root->left->right = createNode(5);      // 判断是否为完全二叉树     if (isCompleteBinaryTree(root)) {         printf("该二叉树是完全二叉树。\n");     } else {         printf("该二叉树不是完全二叉树。\n");     }      return 0; }

三、C++语言实现

以下是C++的实现示例：

#include <iostream> #include <queue>  using namespace std;  // 定义二叉树节点结构体 struct TreeNode {     int val;     TreeNode *left;     TreeNode *right;     TreeNode(int x) : val(x), left(NULL), right(NULL) {} };  // 判断二叉树是否为完全二叉树 bool isCompleteBinaryTree(TreeNode* root) {     if (root == nullptr) return true;      queue<TreeNode*> q;     q.push(root);      bool mustBeLeaf = false; // 标记是否到了必须为叶子的阶段      while (!q.empty()) {         TreeNode* node = q.front();         q.pop();          if (mustBeLeaf) {             if (node != nullptr) return false; // 如果到了必须为叶子的阶段，还有非叶子节点，则不是完全二叉树         } else {             if (node == nullptr) {                 mustBeLeaf = true; // 遇到空节点，后续节点必须都是叶子节点             } else {                 q.push(node->left);                 q.push(node->right);             }         }     }      return true; // 遍历完成，没有发现不符合条件的节点，是完全二叉树 }  int main() {     // 创建一个示例二叉树     TreeNode *root = new TreeNode(1);     root->left = new TreeNode(2);     root->right = new TreeNode(3);     root->left->left = new TreeNode(4);      root->left->right = new TreeNode(5);      // 判断是否为完全二叉树     if (isCompleteBinaryTree(root)) {         cout << "该二叉树是完全二叉树。" << endl;     } else {         cout << "该二叉树不是完全二叉树。" << endl;     }      return 0; }