Прямой обход дерева python

Двоичное дерево

Двоичное дерево — древовидная структура данных, в которой у родительских узлов не может быть больше двух детей.

Типы двоичных деревьев

Полное двоичное дерево

Полное двоичное дерево — особый тип бинарных деревьев, в котором у каждого узла либо 0 потомков, либо 2.

Совершенное двоичное дерево

Совершенное двоичное дерево — особый тип бинарного дерева, в котором у каждого внутреннего узла по два ребенка, а листовые вершины находятся на одном уровне.

Законченное двоичное дерево

Законченное двоичное дерево похоже на совершенное, но есть три большие отличия.

1. Все уровни должны быть заполнены.
2. Все листовые вершины склоняются влево.
3. У последней листовой вершины может не быть правого собрата. Это значит, что завершенное дерево необязательно полное.

Вырожденное двоичное дерево

Вырожденное двоичное дерево — дерево, в котором на каждый уровень приходится по одной вершине.

Скошенное вырожденное дерево

Скошенное вырожденное дерево — вырожденное дерево, в котором есть либо только левые, либо только правые узлы. Таким образом, есть два типа скошенных деревьев — скошенные влево вырожденные деревья и скошенные вправо вырожденные деревья.

Сбалансированное двоичное дерево

Сбалансированное двоичное дерево — тип бинарного дерева, в котором у каждой вершины количество вершин в левом и правом поддереве различаются либо на 0, либо на 1.

Представление двоичного дерева

Узел двоичного дерева можно представить структурой, содержащей данные и два указателя на другие структуры того же типа.

Примеры реализации

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 #include 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 #include 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 data; traversePreOrder(temp->left); traversePreOrder(temp->right); > > // Центрированный обход дерева void traverseInOrder(struct node *temp) < if (temp != NULL) < traverseInOrder(temp->left); cout data; traverseInOrder(temp->right); > > // Обратный обход дерева void traversePostOrder(struct node *temp) < if (temp != NULL) < traversePostOrder(temp->left); traversePostOrder(temp->right); cout data; > > int main() < struct node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); cout

Где используется

• Для быстрого доступа к данным.
• В алгоритмах маршрутизации.
• Для реализации куч.
• В синтаксических деревьях.

Источник

Бинарное дерево на Python

Дерево представляет из себя узлы, соединенные ребрами, и является нелинейной структурой данных. Бинарное дерево обладает следующими особенностями:

• Один из узлов помечен как корневой.
• Каждый узел, отличный от корневого, связан с одним родительским узлом.
• Каждый узел может иметь произвольное количество узлов-наследников.

Мы можем создать древовидную структуру данных в Python, используя понятие узла, которое мы рассматривали ранее. Мы назначаем один узел корневым, а затем добавляем дополнительные узлы в качестве узлов-наследников. Ниже представлен код, который создает корень.

Создание корневого узла

Мы просто создаем класс Node и присваиваем ему значение. Так мы получаем дерево, в котором есть только корень.

class Node: def __init__(self, data): self.left = None self.right = None self.data = data def PrintTree(self): print(self.data) root = Node(10) root.PrintTree()

После выполнения кода выше, вы получите следующий результат:

Добавление узлов в дерево

Чтобы добавить узел в дерево, мы воспользуемся тем же классом Node , который описали выше, и добавим в него метод insert . Этот метод будет сравнивать значение нового узла с родительским узлом и решать, добавить ли его в дерево как левый узел или как правый. Метод PrintTree будет использоваться для вывода дерева.

class Node: def __init__(self, data): self.left = None self.right = None self.data = data def insert(self, data): # Compare the new value with the parent node if self.data: if data < self.data: if self.left is None: self.left = Node(data) else: self.left.insert(data) elif data >self.data: if self.right is None: self.right = Node(data) else: self.right.insert(data) else: self.data = data # Print the tree def PrintTree(self): if self.left: self.left.PrintTree() print( self.data), if self.right: self.right.PrintTree() # Use the insert method to add nodes root = Node(12) root.insert(6) root.insert(14) root.insert(3) root.PrintTree()

После выполнения кода выше, вы получите следующий результат:

Проход по дереву

Дерево можно обойти, выбрав последовательность посещения узлов. Очевидно, что мы можем начать с корня, затем посетить левое поддерево, а затем правое. Или же можно начать с правого поддерева, а потом посетить левое.

Соответственно, у каждого из этих методов обхода есть свое название.

Алгоритмы обхода деревьев

Обход – это процесс, позволяющий посетить все узлы дерева и вывести их значения. Поскольку все узлы соединены ребрами (ссылками), мы всегда будем начинать с корня. То есть мы не можем просто взять и получить доступ к случайному узлу в дереве. Есть три способа, которыми мы можем воспользоваться, чтобы обойти дерево:

Обратный обход

При таком обходе сначала посещается левое поддерево, затем корень, а затем правое поддерево. Мы всегда помним о том, что каждый узел может представлять само поддерево.

В коде ниже мы используем класс Node для создания плейсхолдеров для корня, левого и правого узлов-наследников. Затем мы создаем метод insert для добавления данных в дерево. Наконец, логика обратного обхода реализуется путем создания пустого списка и добавления в него сначала левого узла, после которого идет корень.

В конце добавляется правый узел и обратный обход завершается. Обратите внимание, что этот процесс повторяется для каждого поддерева до тех пор, пока не будут пройдены все узлы в нем.

class Node: def __init__(self, data): self.left = None self.right = None self.data = data # Insert Node def insert(self, data): if self.data: if data < self.data: if self.left is None: self.left = Node(data) else: self.left.insert(data) else data >self.data: if self.right is None: self.right = Node(data) else: self.right.insert(data) else: self.data = data # Print the Tree def PrintTree(self): if self.left: self.left.PrintTree() print( self.data), if self.right: self.right.PrintTree() # Inorder traversal # Left -> Root -> Right def inorderTraversal(self, root): res = [] if root: res = self.inorderTraversal(root.left) res.append(root.data) res = res + self.inorderTraversal(root.right) return res root = Node(27) root.insert(14) root.insert(35) root.insert(10) root.insert(19) root.insert(31) root.insert(42) print(root.inorderTraversal(root)) 

После выполнения кода выше, вы получите следующий результат:

Прямой обход

В этом методе обхода сначала посещается корень, затем левое поддерево, и, наконец, правое поддерево.

В коде ниже мы используем класс Node для создания плейсхолдеров для корня, левого и правого узлов-наследников. Затем мы создаем метод insert для добавления данных в дерево. Наконец, логика прямого обхода реализуется путем создания пустого списка и добавления в него сначала корня, после которого идет левый узел.

В конце добавляется правый узел и прямой обход завершается. Обратите внимание, что этот процесс повторяется для каждого поддерева до тех пор, пока не будут пройдены все узлы в нем.

class Node: def __init__(self, data): self.left = None self.right = None self.data = data # Insert Node def insert(self, data): if self.data: if data < self.data: if self.left is None: self.left = Node(data) else: self.left.insert(data) elif data >self.data: if self.right is None: self.right = Node(data) else: self.right.insert(data) else: self.data = data # Print the Tree def PrintTree(self): if self.left: self.left.PrintTree() print( self.data), if self.right: self.right.PrintTree() # Preorder traversal # Root -> Left ->Right def PreorderTraversal(self, root): res = [] if root: res.append(root.data) res = res + self.PreorderTraversal(root.left) res = res + self.PreorderTraversal(root.right) return res root = Node(27) root.insert(14) root.insert(35) root.insert(10) root.insert(19) root.insert(31) root.insert(42) print(root.PreorderTraversal(root))

После выполнения кода выше, вы получите следующий результат:

Центрированный обход

В этом методе обхода корень посещается последним, отсюда получается название обхода. Сначала мы обходим левое поддерево, потом правое, и, наконец, корень.

В коде ниже мы используем класс Node для создания плейсхолдеров для корня, левого и правого узлов-наследников. Затем мы создаем метод insert для добавления данных в дерево. Наконец, логика центрированного обхода реализуется путем создания пустого списка и добавления в него сначала левого узла, а затем правого.

В конце добавляется корень и центрированный обход завершается. Обратите внимание, что этот процесс повторяется для каждого поддерева до тех пор, пока не будут пройдены все узлы в нем.

class Node: def __init__(self, data): self.left = None self.right = None self.data = data # Insert Node def insert(self, data): if self.data: if data < self.data: if self.left is None: self.left = Node(data) else: self.left.insert(data) else if data >self.data: if self.right is None: self.right = Node(data) else: self.right.insert(data) else: self.data = data # Print the Tree def PrintTree(self): if self.left: self.left.PrintTree() print( self.data), if self.right: self.right.PrintTree() # Postorder traversal # Left ->Right -> Root def PostorderTraversal(self, root): res = [] if root: res = self.PostorderTraversal(root.left) res = res + self.PostorderTraversal(root.right) res.append(root.data) return res root = Node(27) root.insert(14) root.insert(35) root.insert(10) root.insert(19) root.insert(31) root.insert(42) print(root.PostorderTraversal(root))

После выполнения кода выше, вы получите следующий результат:

Материал подготовлен в рамках курса «Python Developer. Basic».

Всех желающих приглашаем на онлайн-интенсив «Мобильное приложение для автоматических рассылок с использованием Kivy Framework». За 2 дня интенсива мы создадим мобильное приложение (с использованием Kivy Framework) для планирования автоматических рассылок почтовых сообщений. С его помощью мы сможем отправлять коллегам поздравления с днем рождения и другими важными праздниками и событиями.

РЕГИСТРАЦИЯ

Источник