跳到主要内容

完美二叉树

提示
  1. 完美二叉树定义：完美二叉树是每个内部节点都恰好有两个子节点，且所有叶节点都位于相同层级的二叉树。
  2. 节点表示：在完美二叉树中，每个节点包含一个数据项和两个子节点的引用（左和右），并且最后一个节点指向 NULL。
  3. 完美二叉树特性：高度为 h 的完美二叉树有 2h + 1 - 1 个节点，2h 个叶子节点，并且节点的平均深度为 Θ(ln(n))。

完美二叉树是一种二叉树类型，其中每个内部节点恰好有两个子节点，所有叶节点位于相同的层级。

完美二叉树

所有内部节点的度数为2。

递归地，完美二叉树可以定义为：

  1. 如果单个节点没有子节点，它是高度为 h = 0 的完美二叉树，
  2. 如果一个节点具有 h > 0，如果它的两个子树都是高度为 h - 1 且不重叠的，那么它就是一个完美二叉树。

完美二叉树（递归表示）

Python、Java 和 C/C++ 示例​

以下代码用于检查树是否是完美二叉树。

Python Java C C++

# 在Python中检查二叉树是否是完美二叉树


class newNode:
    def __init__(self, k):
        self.key = k
        self.right = self.left = None


# 计算深度
def calculateDepth(node):
    d = 0
    while (node is not None):
        d += 1
        node = node.left
    return d


# 检查树是否为完美二叉树
def is_perfect(root, d, level=0):

    # 检查树是否为空
    if (root is None):
        return True

    # 检查树的存在
    if (root.left is None and root.right is None):
        return (d == level + 1)

    if (root.left is None or root.right is None):
        return False

    return (is_perfect(root.left, d, level + 1) and
            is_perfect(root.right, d, level + 1))


root = None
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.left.left = newNode(4)
root.left.right = newNode(5)

if (is_perfect(root, calculateDepth(root))):
    print("该树是完美二叉树")
else:
    print("该树不是完美二叉树")
// 在Java中检查二叉树是否是完美二叉树

class PerfectBinaryTree {

  static class Node {
    int key;
    Node left, right;
  }

  // 计算深度
  static int depth(Node node) {
    int d = 0;
    while (node != null) {
      d++;
      node = node.left;
    }
    return d;
  }

  // 检查树是否为完美二叉树
  static boolean is_perfect(Node root, int d, int level) {

    // 检查树是否为空
    if (root == null)
      return true;

    // 检查叶节点
    if (root.left == null && root.right == null)
      return (d == level + 1);

    if (root.left == null || root.right == null)
      return false;

    return is_perfect(root.left, d, level + 1) && is_perfect(root.right, d, level + 1);
  }

  // 包装函数
  static boolean is_Perfect(Node root) {
    int d = depth(root);
    return is_perfect(root, d, 0);
  }

  // 创建一个新节点
  static Node newNode(int k) {
    Node node = new Node();
    node.key = k;
    node.right = null;
    node.left = null;
    return node;
  }

  public static void main(String args[]) {
    Node root = null;
    root = newNode(1);
    root.left = newNode(2);
    root.right = newNode(3);
    root.left.left = newNode(4);
    root.left.right = newNode(5);

    if (is_Perfect(root) == true)
      System.out.println("该树是完美二叉树");
    else
      System.out.println("该树不是完美二叉树");
  }
}
// 在C语言中检查二叉树是否为完美二叉树

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

struct node {
  int data;
  struct node *left;
  struct node *right;
};

// 创建一个新节点
struct node *newnode(int data) {
  struct node *node = (struct node *)malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;

  return (node);
}

// 计算深度
int depth(struct node *node) {
  int d = 0;
  while (node != NULL) {
    d++;
    node = node->left;
  }
  return d;
}

// 检查树是否为完美二叉树
bool is_perfect(struct node *root, int d, int level) {
    // 检查树是否为空
  if (root == NULL)
    return true;

  // 检查是否有子节点
  if (root->left == NULL && root->right == NULL)
    return (d == level + 1);

  if (root->left == NULL || root->right == NULL)
    return false;

  return is_perfect(root->left, d, level + 1) &&
       is_perfect(root->right, d, level + 1);
}

// 包装函数
bool is_Perfect(struct node *root) {
  int d = depth(root);
  return is_perfect(root, d, 0);
}

int main() {
  struct node *root = NULL;
  root = newnode(1);
  root->left = newnode(2);
  root->right = newnode(3);
  root->left->left = newnode(4);
  root->left->right = newnode(5);
  root->right->left = newnode(6);

  if (is_Perfect(root))
    printf("该树是完美二叉树\n");
  else
    printf("该树不是完美二叉树\n");
}
// 在C++中检查二叉树是否为完美二叉树

#include <iostream>
using namespace std;

struct Node {
  int key;
  struct Node *left, *right;
};

int depth(Node *node) {
  int d = 0;
  while (node != NULL) {
    d++;
    node = node->left;
  }
  return d;
}

bool isPerfectR(struct Node *root, int d, int level = 0) {
  if (root == NULL)
    return true;

  if (root->left == NULL && root->right == NULL)
    return (d == level + 1);

  if (root->left == NULL || root->right == NULL)
    return false;

  return isPerfectR(root->left, d, level + 1) &&
       isPerfectR(root->right, d, level + 1);
}

bool isPerfect(Node *root) {
  int d = depth(root);
  return isPerfectR(root, d);
}

struct Node *newNode(int k) {
  struct Node *node = new Node;
  node->key = k;
  node->right = node->left = NULL;
  return node;
}

int main() {
  struct Node *root = NULL;
  root = newNode(1);
  root->left = newNode(2);
  root->right = newNode(3);
  root->left->left = newNode(4);
  root->left->right = newNode(5);
  root->right->left = newNode(6);

  if (isPerfect(root))
    cout << "该树是完美二叉树\n";
  else
    cout << "该树不是完美二叉树\n";
}

以上是检查二叉树是否为完美二叉树的C和C++示例。

完美二叉树定理​

  1. 高度为 h 的完美二叉树具有 2h + 1 - 1 个节点。
  2. 具有 n 个节点的完美二叉树的高度为 log(n + 1) - 1 = Θ(ln(n))。
  3. 高度为 h 的完美二叉树具有 2h 个叶子节点。
  4. 完美二叉树中节点的平均深度为 Θ(ln(n))。
最后于 更新