Двоичное дерево
В этом уроке вы узнаете о разных типах двоичных деревьев и увидите, как их можно реализовать на Си, C++, Java и Python.
Двоичное дерево — древовидная структура данных, в которой у родительских узлов не может быть больше двух детей.
Типы двоичных деревьев
Полное двоичное дерево
Полное двоичное дерево — особый тип бинарных деревьев, в котором у каждого узла либо 0 потомков, либо 2.
Совершенное двоичное дерево
Совершенное двоичное дерево — особый тип бинарного дерева, в котором у каждого внутреннего узла по два ребенка, а листовые вершины находятся на одном уровне.
Законченное двоичное дерево
Законченное двоичное дерево похоже на совершенное, но есть три большие отличия.
- Все уровни должны быть заполнены.
- Все листовые вершины склоняются влево.
- У последней листовой вершины может не быть правого собрата. Это значит, что завершенное дерево необязательно полное.
Вырожденное двоичное дерево
Вырожденное двоичное дерево — дерево, в котором на каждый уровень приходится по одной вершине.
Скошенное вырожденное дерево
Скошенное вырожденное дерево — вырожденное дерево, в котором есть либо только левые, либо только правые узлы. Таким образом, есть два типа скошенных деревьев — скошенные влево вырожденные деревья и скошенные вправо вырожденные деревья.
Сбалансированное двоичное дерево
Сбалансированное двоичное дерево — тип бинарного дерева, в котором у каждой вершины количество вершин в левом и правом поддереве различаются либо на 0, либо на 1.
Представление двоичного дерева
Узел двоичного дерева можно представить структурой, содержащей данные и два указателя на другие структуры того же типа.
struct node
{
int data;
struct node *left;
struct node *right;
};
Примеры реализации
Python
# Двоичное дерево в Python
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
# Прямой обход дерева
def traversePreOrder(self):
print(self.val, end=' ')
if self.left:
self.left.traversePreOrder()
if self.right:
self.right.traversePreOrder()
# Центрированный обход дерева
def traverseInOrder(self):
if self.left:
self.left.traverseInOrder()
print(self.val, end=' ')
if self.right:
self.right.traverseInOrder()
# Обратный обход дерева
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("Прямой обход дерева: ", end="")
root.traversePreOrder()
print("\nЦентрированный обход дерева: ", end="")
root.traverseInOrder()
print("\nОбратный обход дерева: ", end="")
root.traversePostOrder()
Java
// Двоичное дерево на Java
// Создание узла
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;
}
// Центрированный обход дерева
public void traverseInOrder(Node node) {
if (node != null) {
traverseInOrder(node.left);
System.out.print(" " + node.key);
traverseInOrder(node.right);
}
}
// Обратный обход дерева
public void traversePostOrder(Node node) {
if (node != null) {
traversePostOrder(node.left);
traversePostOrder(node.right);
System.out.print(" " + node.key);
}
}
// Прямой обход дерева
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("Прямой обход дерева: ");
tree.traversePreOrder(tree.root);
System.out.print("\nЦентрированный обход дерева: ");
tree.traverseInOrder(tree.root);
System.out.print("\nОбратный обход дерева: ");
tree.traversePostOrder(tree.root);
}
}
Си
// Обход дерева на Си
#include <stdio.h>
#include <stdlib.h>
struct node {
int item;
struct node* left;
struct node* right;
};
// Центрированный обход дерева
void inorderTraversal(struct node* root) {
if (root == NULL) return;
inorderTraversal(root->left);
printf("%d ->", root->item);
inorderTraversal(root->right);
}
// Прямой обход дерева
void preorderTraversal(struct node* root) {
if (root == NULL) return;
printf("%d ->", root->item);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// Обратный обход дерева
void postorderTraversal(struct node* root) {
if (root == NULL) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ->", root->item);
}
// Создание нового узла
struct node* createNode(value) {
struct node* newNode = malloc(sizeof(struct node));
newNode->item = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Вставка потомка слева от родительской вершины
struct node* insertLeft(struct node* root, int value) {
root->left = createNode(value);
return root->left;
}
// Вставка потомка справа от родительской вершины
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("Центрированный обход дерева\n");
inorderTraversal(root);
printf("\nПрямой обход дерева\n");
preorderTraversal(root);
printf("\nОбратный обход дерева\n");
postorderTraversal(root);
}
С++
// Двоичное дерево на С++
#include <stdlib.h>
#include <iostream>
using namespace std;
struct node {
int data;
struct node *left;
struct node *right;
};
// Создание нового узла
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);
}
// Прямой обход дерева
void traversePreOrder(struct node *temp) {
if (temp != NULL) {
cout << " " << temp->data;
traversePreOrder(temp->left);
traversePreOrder(temp->right);
}
}
// Центрированный обход дерева
void traverseInOrder(struct node *temp) {
if (temp != NULL) {
traverseInOrder(temp->left);
cout << " " << temp->data;
traverseInOrder(temp->right);
}
}
// Обратный обход дерева
void traversePostOrder(struct node *temp) {
if (temp != NULL) {
traversePostOrder(temp->left);
traversePostOrder(temp->right);
cout << " " << temp->data;
}
}
int main() {
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
cout << "Прямой обход дерева: ";
traversePreOrder(root);
cout << "\nЦентрированный обход дерева: ";
traverseInOrder(root);
cout << "\nОбратный обход дерева: ";
traversePostOrder(root);
}
Где используется
- Для быстрого доступа к данным.
- В алгоритмах маршрутизации.
- Для реализации куч.
- В синтаксических деревьях.