跳到主要内容

完全二叉树

提示
  1. 定义：完全二叉树是一种特殊的二叉树，每个父节点或内部节点要么有两个子节点，要么没有子节点。
  2. 性质：在完全二叉树中，叶节点的数量是内部节点数量加一，总节点数是叶节点数量的两倍减一。
  3. 检查方法：可以通过检查树中每个节点的子节点存在情况来确定一棵树是否是完全二叉树，即如果一个节点有右子节点，则它必须有左子节点。

完全二叉树是一种特殊类型的二叉树，其中每个父节点/内部节点要么有两个子节点，要么没有子节点。

它也被称为正规二叉树。

完全二叉树

完全二叉树定理​

假设，i = 内部节点的数量
       n = 总节点数
       l = 叶节点的数量
      λ = 层级数

  1. 叶节点的数量是 i + 1。
  2. 总节点数是 2i + 1。
  3. 内部节点的数量是 (n – 1) / 2。
  4. 叶节点的数量是 (n + 1) / 2。
  5. 总节点数是 2l – 1。
  6. 内部节点的数量是 l – 1。
  7. 叶节点的数量最多是 2λ - 1。

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

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

Python Java C C++

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


# 创建节点
class Node:

    def __init__(self, item):
        self.item = item
        self.leftChild = None
        self.rightChild = None


# 检查完全二叉树
def isFullTree(root):

    # 树为空的情况
    if root is None:
        return True

    # 检查子节点是否存在
    if root.leftChild is None and root.rightChild is None:
        return True

    if root.leftChild is not None and root.rightChild is not None:
        return (isFullTree(root.leftChild) and isFullTree(root.rightChild))

    return False


root = Node(1)
root.rightChild = Node(3)
root.leftChild = Node(2)

root.leftChild.leftChild = Node(4)
root.leftChild.rightChild = Node(5)
root.leftChild.rightChild.leftChild = Node(6)
root.leftChild.rightChild.rightChild = Node(7)

if isFullTree(root):
    print("该树是完全二叉树")
else:
    print("该树不是完全二叉树")

// 在Java中检查二叉树是否为完全二叉树

class Node {
  int data;
  Node leftChild, rightChild;

  Node(int item) {
  data = item;
  leftChild = rightChild = null;
  }
}

class BinaryTree {
  Node root;

  // 检查完全二叉树
  boolean isFullBinaryTree(Node node) {

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

  // 检查子节点
  if (node.leftChild == null && node.rightChild == null)
    return true;

  if ((node.leftChild != null) && (node.rightChild != null))
    return (isFullBinaryTree(node.leftChild) && isFullBinaryTree(node.rightChild));

  return false;
  }

  public static void main(String args[]) {
    BinaryTree tree = new BinaryTree();
    tree.root = new Node(1);
    tree.root.leftChild = new Node(2);
    tree.root.rightChild = new Node(3);
    tree.root.leftChild.leftChild = new Node(4);
    tree.root.leftChild.rightChild = new Node(5);
    tree.root.rightChild.leftChild = new Node(6);
    tree.root.rightChild.rightChild = new Node(7);

    if (tree.isFullBinaryTree(tree.root))
      System.out.print("该树是完全二叉树");
    else
      System.out.print("该树不是完全二叉树");
  }
}

在C中检查二叉树是否为完全二叉树

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

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

// 创建新节点
struct Node *createNewNode(char k) {
  struct Node *node = (struct Node *)malloc(sizeof(struct Node));
  node->item = k;
  node->right = node->left = NULL;
  return node;
}

bool isFullBinaryTree(struct Node *root) {
  // 检查树是否为空
  if (root == NULL)
    return true;

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

  if ((root->left) && (root->right))
    return (isFullBinaryTree(root->left) && isFullBinaryTree(root->right));

  return false;
}

int main() {
  struct Node *root = NULL;
  root = createNewNode(1);
  root->left = createNewNode(2);
  root->right = createNewNode(3);

  root->left->left = createNewNode(4);
  root->left->right = createNewNode(5);
  root->left->right->left = createNewNode(6);
  root->left->right->right = createNewNode(7);

  if (isFullBinaryTree(root))
    printf("该树是完全二叉树\n");
  else
    printf("该树不是完全二叉树\n");
}

在C++中检查二叉树是否为完全二叉树

#include <iostream>
using namespace std;

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

// 创建新节点
struct Node *newNode(char k) {
  struct Node *node = (struct Node *)malloc(sizeof(struct Node));
  node->key = k;
  node->right = node->left = NULL;
  return node;
}

bool isFullBinaryTree(struct Node *root) {

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

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

  if ((root->left) && (root->right))
    return (isFullBinaryTree(root->left) && isFullBinaryTree(root->right));

  return false;
}

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->left->right->left = newNode(6);
  root->left->right->right = newNode(7);

  if (isFullBinaryTree(root))
    cout << "该树是完全二叉树\n";
  else
    cout << "该树不是完全二叉树\n";
}
最后于 更新