原文： https://www.programiz.com/dsa/perfect-binary-tree

在本教程中，您将学习完美二叉树。 此外，您还将找到一些用于检查 C，C++ ，Java 和 Python 中完美二叉树的示例。

完美二叉树是一种二叉树，其中每个内部节点恰好有两个子节点，而所有叶节点都处于同一级别。

完美二叉树 - 图1

完美二叉树

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

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

  1. 如果单个节点没有子节点，则它是高度为h = 0的完美二叉树，
  2. 如果节点具有h > 0，则如果其两个子树的高度均为h - 1并且不重叠，则它是理想的二叉树。

完美二叉树 - 图2

完美二叉树（递归表示）

Python，Java 和 C/C++ 示例

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

  1. # Checking if a binary tree is a perfect binary tree in Python
  3. class newNode:
  4.     def __init__(self, k):
  5.         self.key = k
  6.         self.right = self.left = None
  8. # Calculate the depth
  9. def calculateDepth(node):
  10.     d = 0
  11.     while (node is not None):
  12.         d += 1
  13.         node = node.left
  14.     return d
  16. # Check if the tree is perfect binary tree
  17. def is_perfect(root, d, level=0):
  19.     # Check if the tree is empty
  20.     if (root is None):
  21.         return True
  23.     # Check the presence of trees
  24.     if (root.left is None and root.right is None):
  25.         return (d == level + 1)
  27.     if (root.left is None or root.right is None):
  28.         return False
  30.     return (is_perfect(root.left, d, level + 1) and
  31.             is_perfect(root.right, d, level + 1))
  33. root = None
  34. root = newNode(1)
  35. root.left = newNode(2)
  36. root.right = newNode(3)
  37. root.left.left = newNode(4)
  38. root.left.right = newNode(5)
  40. if (is_perfect(root, calculateDepth(root))):
  41.     print("The tree is a perfect binary tree")
  42. else:
  43.     print("The tree is not a perfect binary tree")
  1. // Checking if a binary tree is a perfect binary tree in Java
  3. class PerfectBinaryTree {
  5.   static class Node {
  6.     int key;
  7.     Node left, right;
  8.   }
  10.   // Calculate the depth
  11.   static int depth(Node node) {
  12.     int d = 0;
  13.     while (node != null) {
  14.       d++;
  15.       node = node.left;
  16.     }
  17.     return d;
  18.   }
  20.   // Check if the tree is perfect binary tree
  21.   static boolean is_perfect(Node root, int d, int level) {
  23.     // Check if the tree is empty
  24.     if (root == null)
  25.       return true;
  27.     // If for children
  28.     if (root.left == null && root.right == null)
  29.       return (d == level + 1);
  31.     if (root.left == null || root.right == null)
  32.       return false;
  34.     return is_perfect(root.left, d, level + 1) && is_perfect(root.right, d, level + 1);
  35.   }
  37.   // Wrapper function
  38.   static boolean is_Perfect(Node root) {
  39.     int d = depth(root);
  40.     return is_perfect(root, d, 0);
  41.   }
  43.   // Create a new node
  44.   static Node newNode(int k) {
  45.     Node node = new Node();
  46.     node.key = k;
  47.     node.right = null;
  48.     node.left = null;
  49.     return node;
  50.   }
  52.   public static void main(String args[]) {
  53.     Node root = null;
  54.     root = newNode(1);
  55.     root.left = newNode(2);
  56.     root.right = newNode(3);
  57.     root.left.left = newNode(4);
  58.     root.left.right = newNode(5);
  60.     if (is_Perfect(root) == true)
  61.       System.out.println("The tree is a perfect binary tree");
  62.     else
  63.       System.out.println("The tree is not a perfect binary tree");
  64.   }
  65. }
  1. // Checking if a binary tree is a perfect binary tree in C
  3. #include <stdbool.h>
  4. #include <stdio.h>
  5. #include <stdlib.h>
  7. struct node {
  8.   int data;
  9.   struct node *left;
  10.   struct node *right;
  11. };
  13. // Creating a new node
  14. struct node *newnode(int data) {
  15.   struct node *node = (struct node *)malloc(sizeof(struct node));
  16.   node->data = data;
  17.   node->left = NULL;
  18.   node->right = NULL;
  20.   return (node);
  21. }
  23. // Calculate the depth
  24. int depth(struct node *node) {
  25.   int d = 0;
  26.   while (node != NULL) {
  27.     d++;
  28.     node = node->left;
  29.   }
  30.   return d;
  31. }
  33. // Check if the tree is perfect
  34. bool is_perfect(struct node *root, int d, int level) {
  35.     // Check if the tree is empty
  36.   if (root == NULL)
  37.     return true;
  39.   // Check the presence of children
  40.   if (root->left == NULL && root->right == NULL)
  41.     return (d == level + 1);
  43.   if (root->left == NULL || root->right == NULL)
  44.     return false;
  46.   return is_perfect(root->left, d, level + 1) &&
  47.        is_perfect(root->right, d, level + 1);
  48. }
  50. // Wrapper function
  51. bool is_Perfect(struct node *root) {
  52.   int d = depth(root);
  53.   return is_perfect(root, d, 0);
  54. }
  56. int main() {
  57.   struct node *root = NULL;
  58.   root = newnode(1);
  59.   root->left = newnode(2);
  60.   root->right = newnode(3);
  61.   root->left->left = newnode(4);
  62.   root->left->right = newnode(5);
  63.   root->right->left = newnode(6);
  65.   if (is_Perfect(root))
  66.     printf("The tree is a perfect binary tree\n");
  67.   else
  68.     printf("The tree is not a perfect binary tree\n");
  69. }
  1. // Checking if a binary tree is a full binary tree in C++
  3. #include <iostream>
  4. using namespace std;
  6. struct Node {
  7.   int key;
  8.   struct Node *left, *right;
  9. };
  11. // New node creation
  12. struct Node *newNode(char k) {
  13.   struct Node *node = (struct Node *)malloc(sizeof(struct Node));
  14.   node->key = k;
  15.   node->right = node->left = NULL;
  16.   return node;
  17. }
  19. bool isFullBinaryTree(struct Node *root) {
  20.     // Checking for emptiness
  21.   if (root == NULL)
  22.     return true;
  24.   // Checking for the presence of children
  25.   if (root->left == NULL && root->right == NULL)
  26.     return true;
  28.   if ((root->left) && (root->right))
  29.     return (isFullBinaryTree(root->left) && isFullBinaryTree(root->right));
  31.   return false;
  32. }
  34. int main() {
  35.   struct Node *root = NULL;
  36.   root = newNode(1);
  37.   root->left = newNode(2);
  38.   root->right = newNode(3);
  39.   root->left->left = newNode(4);
  40.   root->left->right = newNode(5);
  41.   root->left->left->left = newNode(6);
  42.   root->left->left->right = newNode(7);
  44.   if (isFullBinaryTree(root))
  45.     cout << "The tree is a full binary tree\n";
  46.   else
  47.     cout << "The tree is not a full binary full\n";
  48. }

完美二叉树定理

  1. 高度为h的完美二叉树具有2^(h+1) – 1节点。
  2. 具有n个节点的理想二叉树的高度为log(n + 1) – 1 = Θ(ln(n))。
  3. 高度为h的理想二叉树具有2^h叶节点。
  4. 完美二叉树中节点的平均深度为Θ(ln(n))。