一棵完整的二叉树是一棵二叉树，除最后一层外，它的所有层次都被完全填满，最后一层的所有叶子都在左边。关于完整的二叉树的更多信息可以找到 在这里 .
null
例如：- 树下面是一棵完整的二叉树（直到最后一个节点的所有节点都被填满，所有的叶子都在左边）
这个问题的迭代解决方案将在下文中讨论。 检查给定的二叉树是否完整|集1（使用级别顺序遍历） 本文讨论了一种递归解决方案。
在二叉树的数组表示中，如果父节点被分配了一个“i”索引，左子节点被分配了一个“2*i+1”索引，而右子节点被分配了一个“2*i+2”索引。如果我们将上面的二叉树表示为一个数组，从上到下、从左到右分别为树的不同节点分配相应的索引。
因此，为了检查二叉树是否是完整的二叉树，我们按照以下方式进行。
- 计算二叉树中的节点数（计数）。
- 从二叉树的根节点开始递归二叉树，索引（i）设置为0，二叉树中的节点数（计数）。
- 如果正在检查的当前节点为空，则该树是一个完整的二叉树。返回true。
- 如果当前节点的索引（i）大于或等于二叉树中的节点数（count），即（i>=count），则该树不是一个完整的二叉树。返回false。
- 递归检查二叉树的左、右子树是否满足相同条件。对于左子树，使用索引为（2*i+1），而对于右子树，使用索引为（2*i+2）。
上述算法的时间复杂度为O（n）。下面是检查二叉树是否为完整二叉树的代码。
C++
/* C++ program to checks if a binary tree complete ot not */ #include<bits/stdc++.h> #include<stdbool.h> using namespace std; /* Tree node structure */ class Node { public : int key; Node *left, *right; Node *newNode( char k) { Node *node = ( Node*) malloc ( sizeof ( Node)); node->key = k; node->right = node->left = NULL; return node; } }; /* Helper function that allocates a new node with the given key and NULL left and right pointer. */ /* This function counts the number of nodes in a binary tree */ unsigned int countNodes(Node* root) { if (root == NULL) return (0); return (1 + countNodes(root->left) + countNodes(root->right)); } /* This function checks if the binary tree is complete or not */ bool isComplete ( Node* root, unsigned int index, unsigned int number_nodes) { // An empty tree is complete if (root == NULL) return ( true ); // If index assigned to current node is more than // number of nodes in tree, then tree is not complete if (index >= number_nodes) return ( false ); // Recur for left and right subtrees return (isComplete(root->left, 2*index + 1, number_nodes) && isComplete(root->right, 2*index + 2, number_nodes)); } // Driver code int main() { Node n1; // Let us create tree in the last diagram above Node* root = NULL; root = n1.newNode(1); root->left = n1.newNode(2); root->right = n1.newNode(3); root->left->left = n1.newNode(4); root->left->right = n1.newNode(5); root->right->right = n1.newNode(6); unsigned int node_count = countNodes(root); unsigned int index = 0; if (isComplete(root, index, node_count)) cout << "The Binary Tree is complete" ; else cout << "The Binary Tree is not complete" ; return (0); } // This code is contributed by SoumikMondal |
C
/* C program to checks if a binary tree complete ot not */ #include<stdio.h> #include<stdlib.h> #include<stdbool.h> /* Tree node structure */ struct Node { int key; struct Node *left, *right; }; /* Helper function that allocates a new node with the given key and NULL left and right pointer. */ struct Node *newNode( char k) { struct Node *node = ( struct Node*) malloc ( sizeof ( struct Node)); node->key = k; node->right = node->left = NULL; return node; } /* This function counts the number of nodes in a binary tree */ unsigned int countNodes( struct Node* root) { if (root == NULL) return (0); return (1 + countNodes(root->left) + countNodes(root->right)); } /* This function checks if the binary tree is complete or not */ bool isComplete ( struct Node* root, unsigned int index, unsigned int number_nodes) { // An empty tree is complete if (root == NULL) return ( true ); // If index assigned to current node is more than // number of nodes in tree, then tree is not complete if (index >= number_nodes) return ( false ); // Recur for left and right subtrees return (isComplete(root->left, 2*index + 1, number_nodes) && isComplete(root->right, 2*index + 2, number_nodes)); } // Driver program int main() { // Le us create tree in the last diagram above 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->right = newNode(6); unsigned int node_count = countNodes(root); unsigned int index = 0; if (isComplete(root, index, node_count)) printf ( "The Binary Tree is complete" ); else printf ( "The Binary Tree is not complete" ); return (0); } |
JAVA
// Java program to check if binary tree is complete or not /* Tree node structure */ class Node { int data; Node left, right; Node( int item) { data = item; left = right = null ; } } class BinaryTree { Node root; /* This function counts the number of nodes in a binary tree */ int countNodes(Node root) { if (root == null ) return ( 0 ); return ( 1 + countNodes(root.left) + countNodes(root.right)); } /* This function checks if the binary tree is complete or not */ boolean isComplete(Node root, int index, int number_nodes) { // An empty tree is complete if (root == null ) return true ; // If index assigned to current node is more than // number of nodes in tree, then tree is not complete if (index >= number_nodes) return false ; // Recur for left and right subtrees return (isComplete(root.left, 2 * index + 1 , number_nodes) && isComplete(root.right, 2 * index + 2 , number_nodes)); } // Driver program public static void main(String args[]) { BinaryTree tree = new BinaryTree(); // Le us create tree in the last diagram above Node NewRoot = null ; 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.right = new Node( 6 ); int node_count = tree.countNodes(tree.root); int index = 0 ; if (tree.isComplete(tree.root, index, node_count)) System.out.print( "The binary tree is complete" ); else System.out.print( "The binary tree is not complete" ); } } // This code is contributed by Mayank Jaiswal |
Python3
# Python program to check if a binary tree complete or not # Tree node structure class Node: # Constructor to create a new node def __init__( self , key): self .key = key self .left = None self .right = None # This function counts the number of nodes in a binary tree def countNodes(root): if root is None : return 0 return ( 1 + countNodes(root.left) + countNodes(root.right)) # This function checks if binary tree is complete or not def isComplete(root, index, number_nodes): # An empty is complete if root is None : return True # If index assigned to current nodes is more than # number of nodes in tree, then tree is not complete if index > = number_nodes : return False # Recur for left and right subtrees return (isComplete(root.left , 2 * index + 1 , number_nodes) and isComplete(root.right, 2 * index + 2 , number_nodes) ) # Driver Program root = Node( 1 ) root.left = Node( 2 ) root.right = Node( 3 ) root.left.left = Node( 4 ) root.left.right = Node( 5 ) root.right.right = Node( 6 ) node_count = countNodes(root) index = 0 if isComplete(root, index, node_count): print ( "The Binary Tree is complete" ) else : print ( "The Binary Tree is not complete" ) # This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
// C# program to check if binary // tree is complete or not using System; /* Tree node structure */ class Node { public int data; public Node left, right; public Node( int item) { data = item; left = right = null ; } } public class BinaryTree { Node root; /* This function counts the number of nodes in a binary tree */ int countNodes(Node root) { if (root == null ) return (0); return (1 + countNodes(root.left) + countNodes(root.right)); } /* This function checks if the binary tree is complete or not */ bool isComplete(Node root, int index, int number_nodes) { // An empty tree is complete if (root == null ) return true ; // If index assigned to current node is more than // number of nodes in tree, then tree is not complete if (index >= number_nodes) return false ; // Recur for left and right subtrees return (isComplete(root.left, 2 * index + 1, number_nodes) && isComplete(root.right, 2 * index + 2, number_nodes)); } // Driver code public static void Main() { BinaryTree tree = new BinaryTree(); // Let us create tree in the last diagram above 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.right = new Node(6); int node_count = tree.countNodes(tree.root); int index = 0; if (tree.isComplete(tree.root, index, node_count)) Console.WriteLine( "The binary tree is complete" ); else Console.WriteLine( "The binary tree is not complete" ); } } /* This code is contributed by Rajput-Ji*/ |
Javascript
<script> // JavaScript program to check if // binary tree is complete or not /* Tree node structure */ class Node { constructor(val) { this .data = val; this .left = null ; this .right = null ; } } var root; /* This function counts the number of nodes in a binary tree */ function countNodes(root) { if (root == null ) return (0); return (1 + countNodes(root.left) + countNodes(root.right)); } /* This function checks if the binary tree is complete or not */ function isComplete(root , index , number_nodes) { // An empty tree is complete if (root == null ) return true ; // If index assigned to current node is more than // number of nodes in tree, then tree is not complete if (index >= number_nodes) return false ; // Recur for left and right subtrees return (isComplete(root.left, 2 * index + 1, number_nodes) && isComplete(root.right, 2 * index + 2, number_nodes)); } // Driver program // Le us create tree in the last diagram above var NewRoot = null ; root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.right = new Node(5); root.left.left = new Node(4); root.right.right = new Node(6); var node_count = countNodes(root); var index = 0; if (isComplete(root, index, node_count)) document.write( "The binary tree is complete" ); else document.write( "The binary tree is not complete" ); // This code contributed by umadevi9616 </script> |
输出：
The Binary Tree is not complete
本文由 高瑞夫·古普塔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
