Popolno binarno drevo

V tej vadnici boste izvedeli več o celotnem binarnem drevesu in njegovih različnih vrstah. Prav tako boste našli delovne primere celotnega binarnega drevesa v jezikih C, C ++, Java in Python.

Popolno binarno drevo je binarno drevo, v katerem so vse ravni popolnoma zapolnjene, razen morda najnižje, ki je zapolnjeno z leve.

Popolno binarno drevo je tako kot polno binarno drevo, vendar z dvema glavnima razlikama

  1. Vsi elementi lista se morajo nagniti proti levi.
  2. Zadnji element lista morda nima pravega brata ali sestre, tj. Popolno binarno drevo ne sme biti polno binarno drevo.
Popolno binarno drevo

Celotno binarno drevo vs popolno binarno drevo

Primerjava med celotnim binarnim drevesom in popolnim binarnim drevesom Primerjava med celotnim binarnim drevesom in popolnim binarnim drevesom Primerjava med celotnim binarnim drevesom in popolnim binarnim drevesom

Kako nastane popolno binarno drevo?

  1. Izberite prvi element seznama, ki bo korensko vozlišče. (št. elementov na nivoju I: 1) Izberite prvi element kot root
  2. Drugi element postavite kot levega podrejenega koreninskega vozlišča, tretji element pa kot desnega otroka. (št. elementov na stopnji II: 2) 12 kot levi otrok in 9 kot desni otrok
  3. Naslednja dva elementa postavite kot otroka levega vozlišča druge stopnje. Še enkrat postavite naslednja dva elementa kot podrejena elementa desnega vozlišča druge stopnje (št. Elementov na nivoju III-4: 4).
  4. Ponavljajte, dokler ne dosežete zadnjega elementa. 5 kot levi otrok in 6 kot desni otrok

Primeri Python, Java in C / C ++

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

Povezava med indeksi nizov in drevesnim elementom

Popolno binarno drevo ima zanimivo lastnost, s katero lahko poiščemo otroke in starše katerega koli vozlišča.

Če je indeks katerega koli elementa v matriki i, bo element v indeksu 2i+1postal levi podrejeni element in element v 2i+2indeksu bo postal pravi podrejeni. Nadrejeni element katerega koli elementa v indeksu i je podan z spodnjo mejo (i-1)/2.

Preizkusimo,

 Levi podrejeni element 1 (indeks 0) = element v (2 * 0 + 1) indeks = element v 1 indeksu = 12 Desni podrejeni element 1 = element v (2 * 0 + 2) indeks = element v 2 indeksu = 9 Podobno, Levi podrejeni otrok 12 (indeks 1) = element v (2 * 1 + 1) indeks = element v 3 indeksu = 5 Desni podrejen 12 = element v (2 * 1 + 2) indeks = element v 4 indeksu = 6

Potrdimo tudi, da veljajo pravila za iskanje nadrejenega katerega koli vozlišča

 Starš 9 (položaj 2) = (2-1) / 2 = ½ = 0,5 ~ 0 indeks = 1 Starš 12 (položaj 1) = (1-1) / 2 = 0 indeks = 1

Razumevanje tega preslikavanja indeksov polj v drevesne položaje je ključnega pomena za razumevanje, kako deluje struktura podatkovnih podatkov kopice in kako se uporablja za izvajanje razvrščanja kopice.

Izpolnite aplikacije binarnega drevesa

  • Podatkovne strukture, ki temeljijo na kopici
  • Razvrsti kup

Zanimive Članki...