Binárny strom

V tomto výučbe sa dozviete o binárnom strome a jeho rôznych druhoch. Nájdete tiež pracovné príklady binárneho stromu v jazykoch C, C ++, Java a Python.

Binárny strom je stromová dátová štruktúra, v ktorej môže mať každý nadradený uzol najviac dve deti. Napríklad,

Binárny strom

Typy binárneho stromu

Celý binárny strom

Úplný binárny strom je špeciálny typ binárneho stromu, v ktorom má každý nadradený uzol alebo interný uzol dve alebo žiadne deti.

Celý binárny strom

Ak sa chcete dozvedieť viac, navštívte úplný binárny strom.

Perfektný binárny strom

Perfektný binárny strom je typ binárneho stromu, v ktorom má každý vnútorný uzol presne dva podradené uzly a všetky listové uzly sú na rovnakej úrovni.

Perfektný binárny strom

Ak sa chcete dozvedieť viac, navštívte dokonalý binárny strom.

Kompletný binárny strom

Úplný binárny strom je ako úplný binárny strom, má však dva hlavné rozdiely

  1. Každá úroveň musí byť úplne naplnená
  2. Všetky listové prvky sa musia nakláňať doľava.
  3. Prvok posledného listu nemusí mať správneho súrodenca, tj úplný binárny strom nemusí byť úplným binárnym stromom.
Kompletný binárny strom

Ak sa chcete dozvedieť viac, navštívte kompletný binárny strom.

Degenerovaný alebo patologický strom

Degenerovaný alebo patologický strom je strom, ktorý má jedno dieťa vľavo alebo vpravo.

Degenerovať binárny strom

Šikmý binárny strom

Šikmý binárny strom je patologický / zdegenerovaný strom, v ktorom stromu dominujú buď ľavé uzly, alebo pravé uzly. Tak, tam sú dva typy asymetrické binárneho stromu: ľavý skosený binárny strom a pravej šikmé binárny strom .

Šikmý binárny strom

Vyvážený binárny strom

Je to typ binárneho stromu, v ktorom je rozdiel medzi ľavým a pravým podstromom pre každý uzol buď 0 alebo 1.

Vyvážený binárny strom

Ak sa chcete dozvedieť viac, navštívte vyvážený binárny strom.

Reprezentácia binárneho stromu

Uzol binárneho stromu predstavuje štruktúra obsahujúca dátovú časť a dva ukazovatele na iné štruktúry rovnakého typu.

 struct node ( int data; struct node *left; struct node *right; );
Reprezentácia binárneho stromu

Príklady jazyka Python, Java a C / C ++

Python Java C C + 
 # Binary Tree in Python class Node: def __init__(self, key): self.left = None self.right = None self.val = key # Traverse preorder def traversePreOrder(self): print(self.val, end=' ') if self.left: self.left.traversePreOrder() if self.right: self.right.traversePreOrder() # Traverse inorder def traverseInOrder(self): if self.left: self.left.traverseInOrder() print(self.val, end=' ') if self.right: self.right.traverseInOrder() # Traverse postorder def traversePostOrder(self): if self.left: self.left.traversePostOrder() if self.right: self.right.traversePostOrder() print(self.val, end=' ') root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) print("Pre order Traversal: ", end="") root.traversePreOrder() print("In order Traversal: ", end="") root.traverseInOrder() print("Post order Traversal: ", end="") root.traversePostOrder()
 // Binary Tree in Java // Node creation class Node ( int key; Node left, right; public Node(int item) ( key = item; left = right = null; ) ) class BinaryTree ( Node root; BinaryTree(int key) ( root = new Node(key); ) BinaryTree() ( root = null; ) // Traverse Inorder public void traverseInOrder(Node node) ( if (node != null) ( traverseInOrder(node.left); System.out.print(" " + node.key); traverseInOrder(node.right); ) ) // Traverse Postorder public void traversePostOrder(Node node) ( if (node != null) ( traversePostOrder(node.left); traversePostOrder(node.right); System.out.print(" " + node.key); ) ) // Traverse Preorder public void traversePreOrder(Node node) ( if (node != null) ( System.out.print(" " + node.key); traversePreOrder(node.left); traversePreOrder(node.right); ) ) 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.left = new Node(4); System.out.print("Pre order Traversal: "); tree.traversePreOrder(tree.root); System.out.print("In order Traversal: "); tree.traverseInOrder(tree.root); System.out.print("Post order Traversal: "); tree.traversePostOrder(tree.root); ) )
 // Tree traversal in C #include #include struct node ( int item; struct node* left; struct node* right; ); // Inorder traversal void inorderTraversal(struct node* root) ( if (root == NULL) return; inorderTraversal(root->left); printf("%d ->", root->item); inorderTraversal(root->right); ) // Preorder traversal void preorderTraversal(struct node* root) ( if (root == NULL) return; printf("%d ->", root->item); preorderTraversal(root->left); preorderTraversal(root->right); ) // Postorder traversal void postorderTraversal(struct node* root) ( if (root == NULL) return; postorderTraversal(root->left); postorderTraversal(root->right); printf("%d ->", root->item); ) // Create a new Node struct node* createNode(value) ( struct node* newNode = malloc(sizeof(struct node)); newNode->item = value; newNode->left = NULL; newNode->right = NULL; return newNode; ) // Insert on the left of the node struct node* insertLeft(struct node* root, int value) ( root->left = createNode(value); return root->left; ) // Insert on the right of the node struct node* insertRight(struct node* root, int value) ( root->right = createNode(value); return root->right; ) int main() ( struct node* root = createNode(1); insertLeft(root, 2); insertRight(root, 3); insertLeft(root->left, 4); printf("Inorder traversal "); inorderTraversal(root); printf("Preorder traversal "); preorderTraversal(root); printf("Postorder traversal "); postorderTraversal(root); )
 // Binary Tree in C++ #include #include using namespace std; struct node ( int data; struct node *left; struct node *right; ); // New node creation struct node *newNode(int data) ( struct node *node = (struct node *)malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node); ) // Traverse Preorder void traversePreOrder(struct node *temp) ( if (temp != NULL) ( cout << " "  left); traversePreOrder(temp->right); ) ) // Traverse Inorder void traverseInOrder(struct node *temp) ( if (temp != NULL) ( traverseInOrder(temp->left); cout << " "  right); ) ) // Traverse Postorder void traversePostOrder(struct node *temp) ( if (temp != NULL) ( traversePostOrder(temp->left); traversePostOrder(temp->right); cout << " "  left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); cout << "preorder traversal: "; traversePreOrder(root); cout << "Inorder traversal: "; traverseInOrder(root); cout << "Postorder traversal: "; traversePostOrder(root); )

Aplikácie binárnych stromov

  • Pre ľahký a rýchly prístup k údajom
  • V algoritmoch smerovača
  • Implementovať haldy dátovú štruktúru
  • Syntaxový strom

Zaujímavé články...