Komplet binært træ

I denne vejledning lærer du om et komplet binært træ og dets forskellige typer. Du finder også arbejdseksempler på et komplet binært træ i C, C ++, Java og Python.

Et komplet binært træ er et binært træ, hvor alle niveauer er fuldstændigt fyldt undtagen muligvis det laveste, der er fyldt fra venstre.

Et komplet binært træ er ligesom et fuldt binært træ, men med to store forskelle

  1. Alle bladelementer skal læne sig mod venstre.
  2. Det sidste bladelement har muligvis ikke et rigtigt søskende, dvs. et komplet binært træ behøver ikke at være et fuldt binært træ.
Komplet binært træ

Fuldt binært træ vs komplet binært træ

Sammenligning mellem fuldt binært træ og komplet binært træ Sammenligning mellem fuldt binært træ og komplet binært træ Sammenligning mellem fuldt binært træ og komplet binært træ Sammenligning mellem fuldt binært træ og komplet binært træ

Hvordan oprettes et komplet binært træ?

  1. Vælg det første element på listen, der skal være rodnoden. (antal elementer på niveau I: 1) Vælg det første element som rod
  2. Sæt det andet element som et venstre barn af rodnoden og det tredje element som det højre barn. (antal elementer på niveau II: 2) 12 som venstre barn og 9 som højre barn
  3. Sæt de næste to elementer som børn af det venstre niveau på det andet niveau. Igen skal du sætte de næste to elementer som børn af den højre knude på det andet niveau (antal elementer på niveau III: 4) -elementer).
  4. Fortsæt med at gentage, indtil du når det sidste element. 5 som venstre barn og 6 som højre 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 mellem matrixindekser og træelement

Et komplet binært træ har en interessant egenskab, som vi kan bruge til at finde børn og forældre til enhver knude.

Hvis indekset for et hvilket som helst element i matrixen er i, bliver elementet i indekset 2i+1det venstre barn, og elementet i 2i+2indekset bliver det rigtige barn. Også overordnet til ethvert element ved indeks i er givet af den nedre grænse for (i-1)/2.

Lad os teste det ud,

 Venstre barn af 1 (indeks 0) = element i (2 * 0 + 1) indeks = element i 1 indeks = 12 Højre barn af 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øjre barn på 12 = element i (2 * 1 + 2) indeks = element i 4 indeks = 6

Lad os også bekræfte, at reglerne gælder for at finde forælder til enhver node

 Forælder til 9 (position 2) = (2-1) / 2 = ½ = 0,5 ~ 0 indeks = 1 Forælder til 12 (position 1) = (1-1) / 2 = 0 indeks = 1

At forstå denne kortlægning af matrixindekser til træpositioner er afgørende for at forstå, hvordan Heap-datastrukturen fungerer, og hvordan den bruges til at implementere Heap Sort.

Komplette applikationer med binært træ

  • Heap-baserede datastrukturer
  • Heap slags

Interessante artikler...