Количество вершин бинарного дерева

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

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

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

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

Полное двоичное дерево — особый тип бинарных деревьев, в котором у каждого узла либо 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

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

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

Источник

Деревья поиска

Дерево — одна из наиболее распространенных структур данных в программировании.

Деревья состоят из набора вершин (узлов, нод) и ориентированных рёбер (ссылок) между ними. Вершины связаны таким образом, что от какой-то одной вершины, называемой корневой (вершина 8 на рисунке), можно дойти до всех остальных единственным способом.

• Родитель вершины $v$ — вершина, из которой есть прямая ссылка в $v$.
• Дети (дочерние элементы, сын, дочь) вершины $v$ — вершины, в которые из $v$ есть прямая ссылка.
• Предки — родители родителей, их родители, и так далее.
• Потомки — дети детей, их дети, и так далее.
• Лист (терминальная вершина) — вершина, не имеющая детей.
• Поддерево — вершина дерева вместе со всеми её потомками.
• Степень вершины — количество её детей.
• Глубина вершины — расстояние от корня до неё.
• Высота дерева — максимальная из глубин всех вершин.

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

Деревья также используются в контексте графов.

Бинарные деревья поиска

Бинарное дерево поиска (англ. binary search tree, BST) — дерево, для которого выполняются следующие свойства:

• У каждой вершины не более двух детей.
• Все вершины обладают ключами, на которых определена операция сравнения (например, целые числа или строки).
• У всех вершин левого поддерева вершины $v$ ключи не больше, чем ключ $v$.
• У всех вершин правого поддерева вершины $v$ ключи больше, чем ключ $v$.
• Оба поддерева — левое и правое — являются двоичными деревьями поиска.

Более общим понятием являются обычные (не бинарные) деревья поиска — в них количество детей может быть больше двух, и при этом в «более левых» поддеревьях ключи должны быть меньше, чем «более правых». Пока что мы сконцентрируемся только на двоичных, потому что они проще.

Чаще всего бинарные деревья поиска хранят в виде структур — по одной на каждую вершину — в которых записаны ссылки (возможно, пустые) на правого и левого сына, ключ и, возможно, какие-то дополнительные данные.

Как можно понять по названию, основное преимущество бинарных деревьев поиска в том, что в них можно легко производить поиск элементов:

Эта функция — как и многие другие основные, например, вставка или удаление элементов — работает в худшем случае за высоту дерева. Высота бинарного дерева в худшем случае может быть $O(n)$ («бамбук»), поэтому в эффективных реализациях поддерживаются некоторые инварианты, гарантирующую среднюю глубину вершины $O(\log n)$ и соответствующую стоимость основных операций. Такие деревья называются сбалансированными.

Источник

Как найти количество вершин на заданном уровне бинарного дерева ( поиска )

Хочу рассмотреть следующее двоичное дерево ( в данном случае — поисковое ):

Рисунок — обыкновенное двоичное поисковое дерево

➡ Для начала надо понять, как нумеруются уровни дерева, на каком уровне лежит корневая вершина и т.п.

Следующая картинка дает ответы на подобные вопросы:

Рисунок — уровни двоичного дерева

Из рисунка видно, что корневая вершина лежит на первом уровне. Иногда в теории алгоритмов нумерацию уровней бинарного дерева начинают с $0$. По-большему счету это непринципиально и мало влияет на логику алгоритма определения количества узлов на заданном уровне.

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

# уровня	Количество вершин	Значения вершин
$1$	$1$	$52$
$2$	$2$	$45,\ 125$
$3$	$3$	$24,\ 88,\ 154$
$4$	$4$	$61,\ 100,\ 132,\ 167$
$5$	$3$	$82,\ 102,\ 155$
$6$	$2$	$74,\ 118$
$7$	$0$	$—$

💡 Но хочу напомнить, что моя задача — написать программную функцию, которая вычисляет количество вершин на заданном ( $N$-ом ) уровне двоичного дерева.

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

Рисунок — уровни анонимного двоичного дерева ( поиска )

Например, пользователь «говорит», что хочет узнать количество вершин на $5$-ом уровне. Моя программная функция должна в качестве результата выдать ответ $3$, так как на уровне #$5$ находится три вершины:

Рисунок — на уровне #$5$ находится $3$ вершины

➡ Если пользователь сделает запрос по номеру уровня, которого не существует в двоичном дереве, то программа должна выдать ответ $0$. Например, уровня #17 в анализируемом анонимном двоичном дереве нет физически, поэтому и узлов на этом уровне также нет физически.

Кстати, в одной из своих статей-шпаргалок я показывал, как реализовать поуровневый вывод вершин бинарного дерева ( поиска ). Мне пришлось задействовать классическую структуру данных «Очередь» ( Queue, FIFO — First-In, First-Out ). Весь процесс был построен итеративно, то есть без рекурсии. В текущем алгоритме ( нахождения количества узлов на заданном уровне ) мне не придется прибегать к вспомогательным структурам данных и, думаю, все реализую рекурсивно в одной компактной функции.

💡 Основная идея алгоритма определения количества узлов двоичного дерева ( поиска ) на заданном ( $N$-ом ) уровне: так как до каждой вершины дерева существует строго один путь от корневой вершины ( корень лежит на уровне #$1$ ), то я буду рекурсивно перебирать все пути до тех пор, пока не будет достигнут заданный уровень или NULL.

Под перебором я понимаю стандартный обход двоичного дерева. Всего их существует $6$ штук. Я выберу LKP-обход ( симметричный левый, левый-корень-правый ).

Если в процессе обхода дерева я вышел на заданный уровень, то дальше спускаться по дереву смысла нет, поэтому это будет окончанием рекурсивного спуска для текущего пути и в качестве ответа верну из функции $1$.

В результате закодировал на языке «чистый» Си следующую функцию, а также поставил детальные комментарии к каждой строке кода:

Источник