# 完全二叉樹 > 原文： [https://www.programiz.com/dsa/complete-binary-tree](https://www.programiz.com/dsa/complete-binary-tree) #### 在本教程中，您將學習完全二叉樹及其不同類型。 此外，您還將在 C，C++ ，Java 和 Python 中找到完全二叉樹的工作示例。 完全二叉樹是一棵二叉樹，其中所有級別均已完全填充，但最低級別可能會從左側填充。 完全二叉樹就像滿二叉樹，但有兩個主要區別 1. 所有葉子元素都必須向左傾斜。 2. 最后一個葉子元素可能沒有正確的同級，即完全二叉樹不必是滿二叉樹。  完全二叉樹 * * * ## 完全二叉樹 vs 滿二叉樹  完全二叉樹與滿二叉樹的比較  完全二叉樹與滿二叉樹的比較  完全二叉樹與滿二叉樹的比較  完全二叉樹與滿二叉樹的比較 * * * ## 如何創建完全二叉樹？ 1. 選擇列表的第一個元素作為根節點。 （級別 I 上的元素數：1）  選擇第一個元素作為根 2. 將第二個元素作為根節點的左子元素，將第三個元素作為右子元素。 （第 II 級元素的數量：2）  12 是左側子級，9 是右側子級 3. 將接下來的兩個元素作為第二級左節點的子級。 同樣，將接下來的兩個元素作為第二層右節點的子元素（第 III 層上的元素數量：4 個）。 4. 不斷重復，直到到達最后一個元素。  5 是左側子級，6 是右側子級 * * * ## Python，Java 和 C/C++ 示例 ```py # Checking if a binary tree is a complete binary tree in C class Node: def __init__(self, item): self.item = item self.left = None self.right = None # Count the number of nodes def count_nodes(root): if root is None: return 0 return (1 + count_nodes(root.left) + count_nodes(root.right)) # Check if the tree is complete binary tree def is_complete(root, index, numberNodes): # Check if the tree is empty 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("The tree is a complete binary tree") else: print("The tree is not a complete binary tree") ``` ```java // Checking if a binary tree is a complete binary tree in Java // Node creation class Node { int data; Node left, right; Node(int item) { data = item; left = right = null; } } class BinaryTree { Node root; // Count the number of nodes int countNumNodes(Node root) { if (root == null) return (0); return (1 + countNumNodes(root.left) + countNumNodes(root.right)); } // Check for complete binary tree boolean checkComplete(Node root, int index, int numberNodes) { // Check if the tree is empty 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("The tree is a complete binary tree"); else System.out.println("The tree is not a complete binary tree"); } } ``` ```c // Checking if a binary tree is a complete binary tree in C #include <stdbool.h> #include <stdio.h> #include <stdlib.h> struct Node { int key; struct Node *left, *right; }; // Node creation struct Node *newNode(char k) { struct Node *node = (struct Node *)malloc(sizeof(struct Node)); node->key = k; node->right = node->left = NULL; return node; } // Count the number of nodes int countNumNodes(struct Node *root) { if (root == NULL) return (0); return (1 + countNumNodes(root->left) + countNumNodes(root->right)); } // Check if the tree is a complete binary tree bool checkComplete(struct Node *root, int index, int numberNodes) { // Check if the tree is complete 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("The tree is a complete binary tree\n"); else printf("The tree is not a complete binary tree\n"); } ``` ```cpp // Checking if a binary tree is a complete binary tree in C++ #include <iostream> using namespace std; struct Node { int key; struct Node *left, *right; }; // Create node struct Node *newNode(char k) { struct Node *node = (struct Node *)malloc(sizeof(struct Node)); node->key = k; node->right = node->left = NULL; return node; } // Count the number of nodes int countNumNodes(struct Node *root) { if (root == NULL) return (0); return (1 + countNumNodes(root->left) + countNumNodes(root->right)); } // Check if the tree is a complete binary tree bool checkComplete(struct Node *root, int index, int numberNodes) { // Check if the tree is empty 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 << "The tree is a complete binary tree\n"; else cout << "The tree is not a complete binary tree\n"; } ``` * * * ## 數組索引和樹元素之間的關系 完全二叉樹具有一個有趣的屬性，我們可以用來查找任何節點的子代和父代。 如果數組中任何元素的索引為`i`，則索引`2i+1`中的元素將成為左子元素，而`2i+2`索引中的元素將成為右子元素。 同樣，索引為`i`的任何元素的父級都由`(i-1)/2`的下限給出。 讓我們測試一下 ``` Left child of 1 (index 0) = element in (2*0+1) index = element in 1 index = 12 Right child of 1 = element in (2*0+2) index = element in 2 index = 9 Similarly, Left child of 12 (index 1) = element in (2*1+1) index = element in 3 index = 5 Right child of 12 = element in (2*1+2) index = element in 4 index = 6 ``` 我們還要確認規則是否適用于尋找任何節點的父節點 ``` Parent of 9 (position 2) = (2-1)/2 = ? = 0.5 ~ 0 index = 1 Parent of 12 (position 1) = (1-1)/2 = 0 index = 1 ``` 了解數組索引到樹位置的這種映射對于了解[堆數據結構](https://www.programiz.com/dsa/heap-data-structure)的工作方式以及如何用于實現[堆排序](https://www.programiz.com/dsa/heap-sort)至關重要。 * * * ## 完全二叉樹應用 * 基于堆的數據結構 * [堆排序](https://www.programiz.com/dsa/heap-sort)