Tässä opetusohjelmassa opit täydellisestä binääripuusta ja sen eri tyypeistä. Löydät myös toimivia esimerkkejä täydellisestä binääripuusta C, C ++, Java ja Python.
Täydellinen binääripuu on binääripuu, jossa kaikki tasot ovat täysin täytettyjä, paitsi mahdollisesti alin, joka on täytetty vasemmalta.
Täydellinen binääripuu on aivan kuin täysi binääripuu, mutta sillä on kaksi suurta eroa
- Kaikkien lehtielementtien on kallistettava vasemmalle.
- Viimeisellä lehtielementillä ei ehkä ole oikeaa sisarusta, ts. Täydellisen binääripuun ei tarvitse olla täysi binääripuu.
Täydellinen binääripuu
Täysi binaarinen puu vs täydellinen binaarinen puu
Vertailu täysbinaarisen puun ja täydellisen binääripuun 
välillä Vertailu täydellisen binäärisen puun ja täydellisen binäärisen puun välillä Vertailu täydellisen binäärisen puun ja täydellisen binäärisen puun 
välillä Täyden binäärisen puun ja täydellisen binäärisen puun 
vertailu
Kuinka täydellinen binaarinen puu luodaan?
- Valitse luettelon ensimmäinen elementti juurisolmuksi. (elementtien lukumäärä tasolla I: 1)
Valitse ensimmäinen elementti juureksi - Aseta toinen elementti juurisolmun vasemmaksi lapseksi ja kolmas elementti oikeaksi lapseksi. (elementtien lukumäärä tasolla II: 2)
12 vasemmalla ja 9 oikealla lapsena - Laita seuraavat kaksi elementtiä toisen tason vasemman solmun lapsina. Laita uudestaan kaksi seuraavaa elementtiä toisen tason oikean solmun lapsina (elementtien lukumäärä tasolla III: 4).
- Jatka toistamista, kunnes saavut viimeisen elementin.
5 vasemmalla ja 6 oikealla lapsena
Python-, Java- ja C / C ++ -esimerkkejä
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"; )
Taulukkoindeksien ja puuelementin suhde
Täydellisellä binääripuulla on mielenkiintoinen ominaisuus, jonka avulla voimme löytää minkä tahansa solmun lapset ja vanhemmat.
Jos matriisin minkä tahansa elementin indeksi on i, indeksin elementistä 2i+1tulee vasen lapsi ja 2i+2indeksin elementistä oikea lapsi. Myös indeksin i minkä tahansa elementin vanhemman antaa alaraja (i-1)/2.
Testataan se,
1: n vasen lapsi (indeksi 0) = elementti (2 * 0 + 1) -hakemistossa = elementti 1-indeksissä = 12 Oikea lapsi 1 = elementti (2 * 0 + 2) -hakemistossa = elementti 2-indeksissä = 9 Samoin 12: n vasen lapsi (indeksi 1) = elementti (2 * 1 + 1) -hakemistossa = elementti 3-indeksissä = 5 Oikea 12-vuotias lapsi = elementti (2 * 1 + 2) -hakemistossa = elementti 4-indeksissä = 6
Vahvistetaan myös, että säännöt koskevat minkä tahansa solmun vanhemman löytämistä
Vanhempi 9: stä (asema 2) = (2-1) / 2 = ½ = 0,5 ~ 0 indeksi = 1 Vanhempi 12: sta (asema 1) = (1-1) / 2 = 0 indeksi = 1
Taulukkoindeksien kartoituksen ymmärtäminen puun sijainteihin on kriittistä, jotta ymmärrämme, kuinka kasan tietorakenne toimii ja miten sitä käytetään kasan lajittelun toteuttamiseen.
Täydelliset binääripuun sovellukset
- Kasapohjaiset tietorakenteet
- Kasa lajittelu
