跳到主要内容

完备二叉树

提示
  1. 基本定义：完全二叉树是一种二叉树，其中除了最后一层外，所有层都完全填满，并且最后一层的节点从左侧开始填充。
  2. 特征区别：与满二叉树相比，完全二叉树的所有叶子节点必须倾向于左侧，且最后一个叶子节点可能没有右兄弟，即不必是满二叉树。
  3. 结构特性：在完全二叉树中，任意节点的左子节点索引为 2i+1，右子节点索引为 2i+2，而任意节点的父节点索引为 (i-1)/2（其中 i 为该节点的索引）。

完全二叉树是一种二叉树，其所有层都完全填满，除了可能最底层，这一层从左侧开始填充。

完全二叉树就像满二叉树，但有两个主要区别：

  1. 所有叶子节点必须倾向于左侧。
  2. 最后一个叶子节点可能没有右兄弟节点，即完全二叉树不必是满二叉树。

完全二叉树

满二叉树与完全二叉树的对比​

满二叉树与完全二叉树的比较

满二叉树与完全二叉树的比较

满二叉树与完全二叉树的比较

满二叉树与完全二叉树的比较

如何创建完全二叉树？​

  1. 选择列表的第一个元素作为根节点。（第一层的元素数量：1） 创建完全二叉树

  2. 将第二个元素作为根节点的左子节点，将第三个元素作为右子节点。（第二层的元素数量：2） 创建完全二叉树

  3. 将接下来的两个元素作为第二层左节点的子节点。然后，将再接下来的两个元素作为第二层右节点的子节点（第三层的元素数量：4）。

  4. 重复此过程，直到达到最后一个元素。 创建完全二叉树

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

Python Java C C++

# 用 C 检查一个二叉树是否为完全二叉树

class Node:

    def __init__(self, item):
        self.item = item
        self.left = None
        self.right = None

# 计算节点数
def count_nodes(root):
    if root is None:
        return 0
    return (1 + count_nodes(root.left) + count_nodes(root.right))

# 检查树是否为完全二叉树
def is_complete(root, index, numberNodes):

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

    if index >= numberNodes:
        return False

    return (is_complete(root.left, 2 * index + 1, numberNodes)
            and is_complete(root.right, 2 * index + 2, numberNodes))

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)

node_count = count_nodes(root)
index = 0

if is_complete(root, index, node_count):
    print("该树是一个完全二叉树")
else:
    print("该树不是一个完全二叉树")

// 用 Java 检查一个二叉树是否为完全二叉树

// 创建节点
class Node {
  int data;
  Node left, right;

  Node(int item) {
    data = item;
    left = right = null;
  }
}

class BinaryTree {
  Node root;

  // 计算节点数
  int countNumNodes(Node root) {
    if (root == null)
      return (0);
    return (1 + countNumNodes(root.left) + countNumNodes(root.right));
  }

  // 检查是否为完全二叉树
  boolean checkComplete(Node root, int index, int numberNodes) {

    // 检查树是否为空
    if

 (root == null)
      return true;

    if (index >= numberNodes)
      return false;

    return (checkComplete(root.left, 2 * index + 1, numberNodes)
        && checkComplete(root.right, 2 * index + 2, numberNodes));
  }

  public static void main(String args[]) {
    BinaryTree tree = new BinaryTree();

    tree.root = new Node(1);
    tree.root.left = new Node(2);
    tree.root.right = new Node(3);
    tree.root.left.right = new Node(5);
    tree.root.left.left = new Node(4);
    tree.root.right.left = new Node(6);

    int node_count = tree.countNumNodes(tree.root);
    int index = 0;

    if (tree.checkComplete(tree.root, index, node_count))
      System.out.println("该树是一个完全二叉树");
    else
      System.out.println("该树不是一个完全二叉树");
  }
}
// 在 C 语言中检查二叉树是否为完全二叉树

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

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;
}

// 计算节点数量
int countNumNodes(struct Node *root) {
  if (root == NULL)
    return (0);
  return (1 + countNumNodes(root->left) + countNumNodes(root->right));
}

// 检查树是否为完全二叉树
bool checkComplete(struct Node *root, int index, int numberNodes) {
  // 检查树是否完全
  if (root == NULL)
    return true;

  if (index >= numberNodes)
    return false;

  return (checkComplete(root->left, 2 * index + 1, numberNodes) && checkComplete(root->right, 2 * index + 2, numberNodes));
}

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);

  int node_count = countNumNodes(root);
  int index = 0;

  if (checkComplete(root, index, node_count))
    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;
}

// 计算节点数量
int countNumNodes(struct Node *root) {
  if (root == NULL)
    return (0);
  return (1 + countNumNodes(root->left) + countNumNodes(root->right));
}

// 检查树是否为完全二叉树
bool checkComplete(struct Node *root, int index, int numberNodes) {

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

  if (index >= numberNodes)
    return false;

  return (checkComplete(root->left, 2 * index + 1, numberNodes) && checkComplete(root->right, 2 * index + 2, numberNodes));
}

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);

  int node_count = countNumNodes(root);
  int index = 0;

  if (checkComplete(root, index, node_count))
    cout << "该树是完全二叉树\n";
  else
    cout << "该树不是完全二叉树\n";
}

数组索引与树元素的关系​

完全二叉树有一个有趣的特性，我们可以用它来找到任何节点的子节点和父节点。

如果数组中任意元素的索引为 i，那么索引 2i+1 处的元素将成为左子节点，索引 2i+2 处的元素将成为右子节点。此外，索引为 i 的任何元素的父节点由 (i-1)/2 的下限给出。

让我们来验证一下，

1 （索引 0）的左子节点
= (2*0+1) 索引处的元素
= 1 索引处的元素
= 12

1 的右子节点
= (2*0+2) 索引处的元素
= 2 索引处的元素
= 9

同样地，
12 （索引 1）的左子节点
= (2*1+1) 索引处的元素
= 3 索引处的元素
= 5

12 的右子节点
= (2*1+2) 索引处的元素
= 4 索引处的元素
= 6

让我们还来确认查找任何节点的父节点的规则是否成立

9 （位置 2）的父节点
= (2-1)/2
= ½
= 0.5
约为 0 索引
= 1

12 （位置 1）的父节点
= (1-1)/2
= 0 索引
= 1

理解数组索引到树位置的这种映射对于理解堆数据结构的工作方式以及它如何被用于实现堆排序至关重要。

完全二叉树的应用​

最后于 更新