Komplett binært tre

I denne opplæringen vil du lære om et komplett binært tre og dets forskjellige typer. Du finner også arbeidseksempler på et komplett binært tre i C, C ++, Java og Python.

Et komplett binært tre er et binært tre der alle nivåene er fullstendig fylt, bortsett fra muligens det laveste, som er fylt fra venstre.

Et komplett binært tre er akkurat som et fullt binært tre, men med to store forskjeller

  1. Alle bladelementene må lene seg mot venstre.
  2. Det siste bladelementet har kanskje ikke riktig søsken, dvs. et komplett binært tre trenger ikke å være et fullstendig binært tre.
Komplett binært tre

Full Binary Tree vs Complete Binary Tree

Sammenligning mellom fullt binært tre og komplett binært tre Sammenligning mellom fullt binært tre og komplett binært tre Sammenligning mellom fullt binært tre og komplett binært tre Sammenligning mellom fullt binært tre og komplett binært tre

Hvordan blir et komplett binært tre opprettet?

  1. Velg det første elementet i listen som skal være rotnoden. (antall elementer på nivå I: 1) Velg det første elementet som rot
  2. Sett det andre elementet som et venstre barn av rotnoden og det tredje elementet som det høyre barnet. (antall elementer på nivå II: 2) 12 som venstre barn og 9 som høyre barn
  3. Sett de neste to elementene som barn av venstre node på andre nivå. Igjen, sett de to neste elementene som barn av høyre node på det andre nivået (antall elementer på nivå III: 4) -elementer).
  4. Fortsett å gjenta til du kommer til det siste elementet. 5 som venstre barn og 6 som høyre barn

Python, Java og C / C ++ eksempler

Python Java C C ++ 
 # 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") 
 // 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"); ) )
 // Checking if a binary tree is a complete binary tree in C #include #include #include 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"); else printf("The tree is not a complete binary tree"); )
 // Checking if a binary tree is a complete binary tree in C++ #include 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"; else cout << "The tree is not a complete binary tree"; )

Forholdet mellom matriseindekser og treelement

Et komplett binært tre har en interessant egenskap som vi kan bruke til å finne barn og foreldre til hvilken som helst node.

Hvis indeksen til et element i matrisen er i, blir elementet i indeksen 2i+1det venstre barnet og elementet i 2i+2indeksen blir det rette barnet. Også overordnet til ethvert element ved indeks i er gitt av den nedre grensen av (i-1)/2.

La oss teste det ut,

 Venstre barn av 1 (indeks 0) = element i (2 * 0 + 1) indeks = element i 1 indeks = 12 Høyre barn av 1 = element i (2 * 0 + 2) indeks = element i 2 indeks = 9 Tilsvarende, Venstre barn på 12 (indeks 1) = element i (2 * 1 + 1) indeks = element i 3 indeks = 5 Høyre barn på 12 = element i (2 * 1 + 2) indeks = element i 4 indeks = 6

La oss også bekrefte at reglene gjelder for å finne foreldre til en hvilken som helst node

 Forelder til 9 (posisjon 2) = (2-1) / 2 = ½ = 0,5 ~ 0 indeks = 1 Forelder til 12 (posisjon 1) = (1-1) / 2 = 0 indeks = 1

Å forstå denne kartleggingen av matriseindekser til treposisjoner er avgjørende for å forstå hvordan Heap-datastrukturen fungerer og hvordan den brukes til å implementere Heap Sort.

Fullfør applikasjoner for binære treer

  • Heap-baserte datastrukturer
  • Haugsortering

Interessante artikler...