In questo tutorial, imparerai a conoscere l'albero binario completo e i suoi diversi teoremi. Inoltre, troverai esempi funzionanti per controllare l'albero binario completo in C, C ++, Java e Python.
Un albero binario completo è un tipo speciale di albero binario in cui ogni nodo padre / nodo interno ha due o nessun figlio.
È anche conosciuto come un vero e proprio albero binario .
Albero binario completo
Teoremi completi dell'albero binario
Let, i = the number of internal nodes n = be the total number of nodes l = number of leaves λ = number of levels
- Il numero di foglie è
i + 1. - Il numero totale di nodi è
2i + 1. - Il numero di nodi interni è (n - 1) / 2.
- Il numero di foglie è
(n + 1) / 2. - Il numero totale di nodi è
2l - 1. - Il numero di nodi interni è
l - 1. - Il numero di foglie è al massimo .
2λ - 1
Esempi di Python, Java e C / C ++
Il codice seguente serve per verificare se un albero è un albero binario completo.
Python Java C C + # Checking if a binary tree is a full binary tree in Python # Creating a node class Node: def __init__(self, item): self.item = item self.leftChild = None self.rightChild = None # Checking full binary tree def isFullTree(root): # Tree empty case if root is None: return True # Checking whether child is present if root.leftChild is None and root.rightChild is None: return True if root.leftChild is not None and root.rightChild is not None: return (isFullTree(root.leftChild) and isFullTree(root.rightChild)) return False root = Node(1) root.rightChild = Node(3) root.leftChild = Node(2) root.leftChild.leftChild = Node(4) root.leftChild.rightChild = Node(5) root.rightChild.leftChild.leftChild = Node(6) root.rightChild.leftChild.rightChild = Node(7) if isFullTree(root): print("The tree is a full binary tree") else: print("The tree is not a full binary full")
// Checking if a binary tree is a full binary tree in Java class Node ( int data; Node leftChild, rightChild; Node(int item) ( data = item; leftChild = rightChild = null; ) ) class BinaryTree ( Node root; // Check for Full Binary Tree boolean isFullBinaryTree(Node node) ( // Checking tree emptiness if (node == null) return true; // Checking the children if (node.leftChild == null && node.rightChild == null) return true; if ((node.leftChild != null) && (node.rightChild != null)) return (isFullBinaryTree(node.leftChild) && isFullBinaryTree(node.rightChild)); return false; ) public static void main(String args()) ( BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.leftChild = new Node(2); tree.root.rightChild = new Node(3); tree.root.leftChild.leftChild = new Node(4); tree.root.leftChild.rightChild = new Node(5); tree.root.rightChild.leftChild = new Node(6); tree.root.rightChild.rightChild = new Node(7); if (tree.isFullBinaryTree(tree.root)) System.out.print("The tree is a full binary tree"); else System.out.print("The tree is not a full binary tree"); ) )
// Checking if a binary tree is a full binary tree in C #include #include #include struct Node ( int item; struct Node *left, *right; ); // Creation of new Node struct Node *createNewNode(char k) ( struct Node *node = (struct Node *)malloc(sizeof(struct Node)); node->item = k; node->right = node->left = NULL; return node; ) bool isFullBinaryTree(struct Node *root) ( // Checking tree emptiness if (root == NULL) return true; // Checking the presence of children if (root->left == NULL && root->right == NULL) return true; if ((root->left) && (root->right)) return (isFullBinaryTree(root->left) && isFullBinaryTree(root->right)); return false; ) int main() ( struct Node *root = NULL; root = createNewNode(1); root->left = createNewNode(2); root->right = createNewNode(3); root->left->left = createNewNode(4); root->left->right = createNewNode(5); root->left->right->left = createNewNode(6); root->left->right->right = createNewNode(7); if (isFullBinaryTree(root)) printf("The tree is a full binary tree"); else printf("The tree is not a full binary full"); )
// Checking if a binary tree is a full binary tree in C++ #include using namespace std; struct Node ( int key; struct Node *left, *right; ); // New 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; ) bool isFullBinaryTree(struct Node *root) ( // Checking for emptiness if (root == NULL) return true; // Checking for the presence of children if (root->left == NULL && root->right == NULL) return true; if ((root->left) && (root->right)) return (isFullBinaryTree(root->left) && isFullBinaryTree(root->right)); return false; ) 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->left->right->left = newNode(6); root->left->right->right = newNode(7); if (isFullBinaryTree(root)) cout << "The tree is a full binary tree"; else cout << "The tree is not a full binary full"; )
