У цьому підручнику ви дізнаєтесь про бінарне дерево та його різні типи. Крім того, ви знайдете робочі приклади бінарного дерева на мовах C, C ++, Java та Python.
Двійкове дерево - це деревоподібна структура даних, в якій кожен батьківський вузол може мати щонайбільше двох дочірніх елементів. Наприклад,
![](https://cdn.wiki-base.com/7722637/binary_tree.png.webp)
Типи бінарного дерева
Повне двійкове дерево
Повне бінарне дерево - це особливий тип бінарного дерева, в якому кожен батьківський вузол / внутрішній вузол має або двох, або взагалі відсутні.
![](https://cdn.wiki-base.com/7722637/binary_tree_2.png.webp)
Щоб дізнатись більше, відвідайте повне двійкове дерево.
Ідеальне бінарне дерево
Ідеальне бінарне дерево - це тип бінарного дерева, в якому кожен внутрішній вузол має рівно два дочірні вузли, і всі листові вузли знаходяться на одному рівні.
![](https://cdn.wiki-base.com/7722637/binary_tree_3.png.webp)
Щоб дізнатись більше, відвідайте ідеальне двійкове дерево.
Повне бінарне дерево
Повне двійкове дерево подібне до повного двійкового дерева, але з двома основними відмінностями
- Кожен рівень повинен бути повністю заповнений
- Всі елементи листя повинні нахилятися вліво.
- Останній елемент листя може не мати правильного брата, тобто повне двійкове дерево не повинно бути повним двійковим деревом.
![](https://cdn.wiki-base.com/7722637/binary_tree_4.png.webp)
Щоб дізнатись більше, відвідайте повне бінарне дерево.
Вироджене або патологічне дерево
Вироджене або патологічне дерево - це дерево, у якого є одна дитина - ліворуч або праворуч.
![](https://cdn.wiki-base.com/7722637/binary_tree_5.png.webp)
Перекошене бінарне дерево
Перекошене бінарне дерево - це патологічне / вироджене дерево, в якому в дереві переважають ліві вузли або праві вузли. Таким чином, існує два типи перекошеною бінарного дерева: лівий перекіс бінарне дерево і правої перекіс бінарне дерево .
![](https://cdn.wiki-base.com/7722637/binary_tree_6.png.webp)
Збалансоване двійкове дерево
Це тип бінарного дерева, в якому різниця між лівим і правим піддеревом для кожного вузла дорівнює 0 або 1.
![](https://cdn.wiki-base.com/7722637/binary_tree_7.png.webp)
Щоб дізнатись більше, відвідайте збалансоване двійкове дерево.
Представлення двійкового дерева
Вузол двійкового дерева представлений структурою, що містить частину даних та два вказівники на інші структури того ж типу.
struct node ( int data; struct node *left; struct node *right; );
![](https://cdn.wiki-base.com/7722637/binary_tree_8.png.webp)
Приклади Python, Java та 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); )
Програми двійкового дерева
- Для легкого та швидкого доступу до даних
- В алгоритмах маршрутизатора
- Для реалізації структури даних купи
- Дерево синтаксису