Komplett binärt träd

I den här handledningen lär du dig om ett komplett binärt träd och dess olika typer. Du hittar också arbetsexempel på ett komplett binärt träd i C, C ++, Java och Python.

Ett komplett binärt träd är ett binärt träd där alla nivåer är helt fyllda utom möjligen det lägsta som fylls från vänster.

Ett komplett binärt träd är precis som ett fullständigt binärt träd, men med två stora skillnader

  1. Alla bladelement måste luta sig åt vänster.
  2. Det sista bladelementet kanske inte har rätt syskon, dvs ett komplett binärt träd behöver inte vara ett fullständigt binärt träd.
Komplett binärt träd

Fullt binärt träd vs komplett binärt träd

Jämförelse mellan fullständigt binärt träd och komplett binärt träd Jämförelse mellan fullt binärt träd och fullständigt binärt träd Jämförelse mellan fullt binärt träd och fullständigt binärt träd Jämförelse mellan fullt binärt träd och fullständigt binärt träd

Hur skapas ett komplett binärt träd?

  1. Välj det första elementet i listan som ska vara rotnoden. (antal element på nivå I: 1) Välj det första elementet som root
  2. Sätt det andra elementet som ett vänstra barn till rotnoden och det tredje elementet som det högra barnet. (antal element på nivå II: 2) 12 som vänsterbarn och 9 som högerbarn
  3. Sätt de två följande elementen som barn till vänster nod på andra nivån. Sätt igen de två nästa elementen som barn till högernoden på den andra nivån (antal element på nivå III: 4).
  4. Fortsätt upprepa tills du når det sista elementet. 5 som vänsterbarn och 6 som högerbarn

Python, Java och C / C ++ exempel

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"; )

Förhållandet mellan matrisindex och trädelement

Ett komplett binärt träd har en intressant egenskap som vi kan använda för att hitta barn och föräldrar till vilken nod som helst.

Om indexet för något element i matrisen är i, blir elementet i indexet 2i+1det vänstra barnet och elementet i 2i+2indexet blir det rätta barnet. Föräldern till vilket element som helst i index i ges också av den nedre gränsen för (i-1)/2.

Låt oss testa det,

 Vänster barn av 1 (index 0) = element i (2 * 0 + 1) index = element i 1 index = 12 Höger barn av 1 = element i (2 * 0 + 2) index = element i 2 index = 9 På samma sätt, Vänster barn av 12 (index 1) = element i (2 * 1 + 1) index = element i 3 index = 5 Höger barn av 12 = element i (2 * 1 + 2) index = element i 4 index = 6

Låt oss också bekräfta att reglerna gäller för att hitta förälder till vilken nod som helst

 Förälder till 9 (position 2) = (2-1) / 2 = ½ = 0,5 ~ 0 index = 1 Förälder till 12 (position 1) = (1-1) / 2 = 0 index = 1

Att förstå denna kartläggning av matrisindex till trädpositioner är avgörande för att förstå hur Heap-datastrukturen fungerar och hur den används för att implementera Heap Sort.

Kompletta binära trädapplikationer

  • Heap-baserade datastrukturer
  • Heap sort

Intressanta artiklar...