Pilnīgs binārs koks

Šajā apmācībā jūs uzzināsit par pilnīgu bināro koku un tā dažādajiem veidiem. Jūs atradīsit arī pilnīga binārā koka piemērus C, C ++, Java un Python.

Pilnīgs binārs koks ir binārs koks, kurā visi līmeņi ir pilnībā aizpildīti, izņemot, iespējams, zemāko, kas ir aizpildīts no kreisās puses.

Pilnīgs binārs koks ir gluži kā pilns binārs koks, bet ar divām būtiskām atšķirībām

  1. Visiem lapu elementiem jābūt noliektiem uz kreiso pusi.
  2. Pēdējā lapas elementā var nebūt pareizā brāļa / māsas, ti, pilnīgam bināram kokam nav jābūt pilnam bināram kokam.
Pilnīgs binārs koks

Pilns binārs koks vs pilns binārs koks

Pilna binārā koka un pilnīga binārā koka salīdzinājums Pilna binārā koka un pilnīga binārā koka salīdzināšana Pilna binārā koka un pilnīga binārā koka salīdzināšana Pilna binārā koka un pilnīgā binārā koka salīdzinājums

Kā tiek izveidots pilnīgs binārs koks?

  1. Atlasiet saraksta pirmo elementu kā saknes mezglu. (I līmeņa elementu skaits: 1) Atlasiet pirmo elementu kā sakni
  2. Ievietojiet otro elementu kā saknes mezgla kreiso bērnu un trešo elementu kā labo bērnu. (II līmeņa elementu skaits: 2) 12 kā kreisais bērns un 9 kā labais bērns
  3. Ievietojiet nākamos divus elementus kā otrā līmeņa kreisā mezgla bērnus. Atkal ielieciet nākamos divus elementus kā otrā līmeņa labā mezgla bērnus (III līmeņa elementu skaits: 4).
  4. Turpiniet atkārtot, līdz esat sasniedzis pēdējo elementu. 5 kā kreisais bērns un 6 kā labais bērns

Python, Java un C / C ++ piemēri

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

Saistība starp masīva indeksiem un koka elementu

Pilnīgam bināram kokam ir interesanta īpašība, kuru mēs varam izmantot, lai atrastu jebkura mezgla bērnus un vecākus.

Ja jebkura masīva elementa indekss ir i, indeksa elements 2i+1kļūs par kreiso bērnu un 2i+2indeksa elements kļūs par pareizo bērnu. Arī jebkura indeksa i elementa vecāku i indeksā izsaka (i-1)/2.

Pārbaudīsim to,

 1 kreisais bērns (indekss 0) = elements (2 * 0 + 1) indeksā = elements 1 indeksā = 12 Labais 1 bērns = elements (2 * 0 + 2) indeksā = elements 2 indeksā = 9 Līdzīgi, Kreisais 12 bērnu bērns (indekss 1) = elements (2 * 1 + 1) indeksā = elements 3 indeksā = 5 Labais 12 bērnu bērns = elements (2 * 1 + 2) indeksā = elements 4 indeksā = 6

Apstiprināsim arī to, ka noteikumi attiecas uz jebkura mezgla vecāku atrašanu

 Vecāks no 9 (2. pozīcija) = (2-1) / 2 = ½ = 0.5 ~ 0 indekss = 1 Vecāks no 12 (1. pozīcija) = (1-1) / 2 = 0 indekss = 1

Izpratne par šo masīvu indeksu kartēšanu ar koku pozīcijām ir kritiska, lai saprastu, kā darbojas kaudzes datu struktūra un kā to izmanto, lai ieviestu kaudzes kārtošanu.

Pabeigt bināro koku lietojumprogrammas

  • Uz kaudzēm balstītas datu struktūras
  • Heap šķirot

Interesanti raksti...