Πλήρες δυαδικό δέντρο

Σε αυτό το σεμινάριο, θα μάθετε για ένα πλήρες δυαδικό δέντρο και τους διαφορετικούς τύπους του. Επίσης, θα βρείτε παραδείγματα εργασίας ενός πλήρους δυαδικού δέντρου σε C, C ++, Java και Python.

Ένα πλήρες δυαδικό δέντρο είναι ένα δυαδικό δέντρο στο οποίο όλα τα επίπεδα γεμίζουν εντελώς εκτός πιθανώς το χαμηλότερο, το οποίο γεμίζει από αριστερά.

Ένα πλήρες δυαδικό δέντρο είναι ακριβώς σαν ένα πλήρες δυαδικό δέντρο, αλλά με δύο μεγάλες διαφορές

  1. Όλα τα φύλλα πρέπει να κλίνουν προς τα αριστερά.
  2. Το τελευταίο στοιχείο φύλλου ενδέχεται να μην έχει σωστό αδελφό, δηλαδή ένα πλήρες δυαδικό δέντρο δεν πρέπει να είναι ένα πλήρες δυαδικό δέντρο.
Πλήρες δυαδικό δέντρο

Πλήρες δυαδικό δέντρο έναντι πλήρους δυαδικού δέντρου

Σύγκριση μεταξύ πλήρους δυαδικού δέντρου και πλήρους δυαδικού δέντρου Σύγκριση μεταξύ πλήρους δυαδικού δέντρου και πλήρους δυαδικού δέντρου Σύγκριση μεταξύ πλήρους δυαδικού δέντρου και πλήρους δυαδικού δέντρου Σύγκριση μεταξύ πλήρους δυαδικού δέντρου και πλήρους δυαδικού δέντρου

Πώς δημιουργείται ένα πλήρες δυαδικό δέντρο;

  1. Επιλέξτε το πρώτο στοιχείο της λίστας που θα είναι ο ριζικός κόμβος. (αριθμός στοιχείων στο επίπεδο-I: 1) Επιλέξτε το πρώτο στοιχείο ως root
  2. Βάλτε το δεύτερο στοιχείο ως αριστερό παιδί του ριζικού κόμβου και το τρίτο στοιχείο ως το δεξί παιδί. (αριθμός στοιχείων στο επίπεδο-ΙΙ: 2) 12 ως αριστερό παιδί και 9 ως δεξί παιδί
  3. Βάλτε τα επόμενα δύο στοιχεία ως παιδιά του αριστερού κόμβου του δεύτερου επιπέδου. Και πάλι, βάλτε τα επόμενα δύο στοιχεία ως παιδιά του δεξιού κόμβου του δεύτερου επιπέδου (αριθμός στοιχείων στο επίπεδο-III: 4) στοιχεία).
  4. Συνεχίστε να επαναλαμβάνετε μέχρι να φτάσετε στο τελευταίο στοιχείο. 5 ως αριστερό παιδί και 6 ως δεξί παιδί

Παραδείγματα Python, Java και 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"; )

Σχέση μεταξύ ευρετηρίων πίνακα και στοιχείου δέντρου

Ένα πλήρες δυαδικό δέντρο έχει μια ενδιαφέρουσα ιδιότητα που μπορούμε να χρησιμοποιήσουμε για να βρούμε τα παιδιά και τους γονείς οποιουδήποτε κόμβου.

Εάν το ευρετήριο οποιουδήποτε στοιχείου στον πίνακα είναι i, το στοιχείο στο ευρετήριο 2i+1θα γίνει το αριστερό θυγατρικό και το στοιχείο στο 2i+2ευρετήριο θα γίνει το σωστό παιδί. Επίσης, ο γονέας οποιουδήποτε στοιχείου στο ευρετήριο i δίνεται από το κάτω όριο του (i-1)/2.

Ας το δοκιμάσουμε,

 Αριστερό παιδί 1 (ευρετήριο 0) = στοιχείο σε (2 * 0 + 1) ευρετήριο = στοιχείο σε 1 ευρετήριο = 12 Δεξιό παιδί 1 = στοιχείο σε (2 * 0 + 2) ευρετήριο = στοιχείο σε 2 ευρετήριο = 9 Ομοίως, Αριστερό παιδί 12 (δείκτης 1) = στοιχείο σε (2 * 1 + 1) δείκτης = στοιχείο σε 3 δείκτη = 5 Δεξί παιδί 12 = στοιχείο σε (2 * 1 + 2) δείκτης = στοιχείο σε 4 δείκτη = 6

Ας επιβεβαιώσουμε επίσης ότι ισχύουν οι κανόνες για την εύρεση γονέα οποιουδήποτε κόμβου

 Γονέας 9 (θέση 2) ​​= (2-1) / 2 = ½ = 0,5 ~ 0 δείκτης = 1 Γονέας 12 (θέση 1) = (1-1) / 2 = 0 δείκτης = 1

Η κατανόηση αυτής της χαρτογράφησης ευρετηρίων συστοιχιών σε θέσεις δέντρου είναι ζωτικής σημασίας για την κατανόηση του τρόπου λειτουργίας της δομής δεδομένων σωρού και του τρόπου με τον οποίο χρησιμοποιείται για την εφαρμογή ταξινόμησης σωρού.

Πλήρεις εφαρμογές δυαδικών δέντρων

  • Δομές δεδομένων βάσει σωρού
  • Είδος σωρού

ενδιαφέροντα άρθρα...