Komplett bináris fa

Ebben az oktatóanyagban megismerhet egy teljes bináris fát és annak különböző típusait. A teljes bináris fáról működő példákat is talál a C, C ++, Java és Python nyelven.

A teljes bináris fa olyan bináris fa, amelyben az összes szint teljesen kitöltődött, kivéve a legalacsonyabbat, amelyet balról lehet kitölteni.

A teljes bináris fa olyan, mint egy teljes bináris fa, de két fő különbség van

  1. Az összes levélelemnek balra kell hajolnia.
  2. Előfordulhat, hogy az utolsó levélelemnek nincs megfelelő testvére, vagyis a teljes bináris fának nem kell teljes bináris fának lennie.
Komplett bináris fa

Teljes bináris fa vs teljes bináris fa

Összehasonlítás a teljes bináris fa és a teljes bináris fa között Összehasonlítás a teljes bináris fa és a teljes bináris fa között Összehasonlítás a teljes bináris fa és a teljes bináris fa között Összehasonlítás a teljes bináris fa és a teljes bináris fa között

Hogyan készül egy komplett bináris fa?

  1. Válassza ki a lista első elemét gyökércsomópontként. (elemek száma az I szinten: 1) Válassza ki az első elemet gyökérként
  2. Helyezze a második elemet a gyökércsomópont bal gyermekének, a harmadik elemet pedig a jobb gyermeknek. (elemek száma a II. szinten: 2) 12 bal gyermekként és 9 jobb gyermekként
  3. Tegye a következő két elemet a második szint bal csomópontjának gyermekeiként. Ismét tegyük a következő két elemet a második szint jobb csomópontjának gyermekeiként (elemszám a III. Szinten: 4).
  4. Addig ismételje, amíg el nem éri az utolsó elemet. 5 bal gyermekként és 6 jobb gyerekként

Példák Python, Java és 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"; )

A tömbindexek és a faelem közötti kapcsolat

A teljes bináris fának érdekes tulajdonsága van, amelyet felhasználhatunk bármely csomópont gyermekeinek és szüleinek megkeresésére.

Ha a tömb bármely elemének indexe i, 2i+1akkor az index eleme bal gyermek lesz , az index eleme 2i+2pedig a jobb gyermek. Az i index bármely elemének szülőjét megadja az (i-1)/2.

Próbáljuk ki,

 1 bal gyermeke (0 index) = elem a (2 * 0 + 1) indexben = elem az 1 indexben = 12 Az 1 jobb gyermeke = elem (2 * 0 + 2) indexben = elem a 2 indexben = 9 Hasonlóképpen, 12 bal bal gyermeke (index 1) = elem a (2 * 1 + 1) indexben = elem a 3 indexben = 5 12 jobb oldali gyermeke = elem a (2 * 1 + 2) indexben = elem a 4 indexben = 6

Erősítsük meg azt is, hogy a szabályok érvényesek bármely csomópont szülőjének megtalálásához

 9 szülő (2. pozíció) = (2-1) / 2 = ½ = 0.5 ~ 0 index = 1 12 szülő szülő (1. pozíció) = (1-1) / 2 = 0 index = 1

A tömbindexek fa pozíciókhoz való hozzárendelésének megértése elengedhetetlen annak megértéséhez, hogy a kupac adatstruktúra hogyan működik, és hogyan használják a kupac rendezés megvalósítására.

Teljes bináris fa alkalmazások

  • Halomalapú adatszerkezetek
  • Halomfajta

érdekes cikkek...