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

在本教程中，您将学习满二叉树及其不同的定理。 此外，您还将找到一些工作示例，以检查 C，C++ ，Java 和 Python 中的完整二进制树。

满二叉树是二叉树的一种特殊类型，其中每个父节点/内部节点都有两个或没有子节点。

也称为适当的二叉树。

满二叉树 - 图1

满二叉树

满二叉树定理

  1. Let, i = the number of internal nodes
  2.        n = be the total number of nodes
  3.        l = number of leaves
  4.       λ = number of levels
  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++ 示例

以下代码用于检查树是否为满二叉树。

  1. # Checking if a binary tree is a full binary tree in Python
  3. # Creating a node
  4. class Node:
  6.     def __init__(self, item):
  7.         self.item = item
  8.         self.leftChild = None
  9.         self.rightChild = None
  11. # Checking full binary tree
  12. def isFullTree(root):
  14.     # Tree empty case
  15.     if root is None:
  16.         return True
  18.     # Checking whether child is present
  19.     if root.leftChild is None and root.rightChild is None:
  20.         return True
  22.     if root.leftChild is not None and root.rightChild is not None:
  23.         return (isFullTree(root.leftChild) and isFullTree(root.rightChild))
  25.     return False
  27. root = Node(1)
  28. root.rightChild = Node(3)
  29. root.leftChild = Node(2)
  31. root.leftChild.leftChild = Node(4)
  32. root.leftChild.rightChild = Node(5)
  33. root.rightChild.leftChild.leftChild = Node(6)
  34. root.rightChild.leftChild.rightChild = Node(7)
  36. if isFullTree(root):
  37.     print("The tree is a full binary tree")
  38. else:
  39.     print("The tree is not a full binary full")
  1. // Checking if a binary tree is a full binary tree in Java
  3. class Node {
  4.   int data;
  5.   Node leftChild, rightChild;
  7.   Node(int item) {
  8.   data = item;
  9.   leftChild = rightChild = null;
  10.   }
  11. }
  13. class BinaryTree {
  14.   Node root;
  16.   // Check for Full Binary Tree
  17.   boolean isFullBinaryTree(Node node) {
  19.   // Checking tree emptiness
  20.   if (node == null)
  21.     return true;
  23.   // Checking the children
  24.   if (node.leftChild == null && node.rightChild == null)
  25.     return true;
  27.   if ((node.leftChild != null) && (node.rightChild != null))
  28.     return (isFullBinaryTree(node.leftChild) && isFullBinaryTree(node.rightChild));
  30.   return false;
  31.   }
  33.   public static void main(String args[]) {
  34.     BinaryTree tree = new BinaryTree();
  35.     tree.root = new Node(1);
  36.     tree.root.leftChild = new Node(2);
  37.     tree.root.rightChild = new Node(3);
  38.     tree.root.leftChild.leftChild = new Node(4);
  39.     tree.root.leftChild.rightChild = new Node(5);
  40.     tree.root.rightChild.leftChild = new Node(6);
  41.     tree.root.rightChild.rightChild = new Node(7);
  43.     if (tree.isFullBinaryTree(tree.root))
  44.       System.out.print("The tree is a full binary tree");
  45.     else
  46.       System.out.print("The tree is not a full binary tree");
  47.   }
  48. }
  1. // Checking if a binary tree is a full binary tree in C
  3. #include <stdbool.h>
  4. #include <stdio.h>
  5. #include <stdlib.h>
  7. struct Node {
  8.   int item;
  9.   struct Node *left, *right;
  10. };
  12. // Creation of new Node
  13. struct Node *createNewNode(char k) {
  14.   struct Node *node = (struct Node *)malloc(sizeof(struct Node));
  15.   node->item = k;
  16.   node->right = node->left = NULL;
  17.   return node;
  18. }
  20. bool isFullBinaryTree(struct Node *root) {
  21.   // Checking tree emptiness
  22.   if (root == NULL)
  23.     return true;
  25.   // Checking the presence of children
  26.   if (root->left == NULL && root->right == NULL)
  27.     return true;
  29.   if ((root->left) && (root->right))
  30.     return (isFullBinaryTree(root->left) && isFullBinaryTree(root->right));
  32.   return false;
  33. }
  35. int main() {
  36.   struct Node *root = NULL;
  37.   root = createNewNode(1);
  38.   root->left = createNewNode(2);
  39.   root->right = createNewNode(3);
  41.   root->left->left = createNewNode(4);
  42.   root->left->right = createNewNode(5);
  43.   root->right->left->left = createNewNode(6);
  44.   root->right->left->right = createNewNode(7);
  46.   if (isFullBinaryTree(root))
  47.     printf("The tree is a full binary tree\n");
  48.   else
  49.     printf("The tree is not a full binary full\n");
  50. }
  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) {
  21.   // Checking for emptiness
  22.   if (root == NULL)
  23.     return true;
  25.   // Checking for the presence of children
  26.   if (root->left == NULL && root->right == NULL)
  27.     return true;
  29.   if ((root->left) && (root->right))
  30.     return (isFullBinaryTree(root->left) && isFullBinaryTree(root->right));
  32.   return false;
  33. }
  35. int main() {
  36.   struct Node *root = NULL;
  37.   root = newNode(1);
  38.   root->left = newNode(2);
  39.   root->right = newNode(3);
  40.   root->left->left = newNode(4);
  41.   root->left->right = newNode(5);
  42.   root->right->left->left = newNode(6);
  43.   root->right->left->right = newNode(7);
  45.   if (isFullBinaryTree(root))
  46.     cout << "The tree is a full binary tree\n";
  47.   else
  48.     cout << "The tree is not a full binary full\n";
  49. }