Cтраница 1
Бинарное дерево не является частным случаем упорядоченного, но эти понятия тесно связаны. [1]
Бинарное дерево представляет собой ориентированное дерево, у которого в каждую вершину, отличную от корня, входит только одна дуга, а выходит не более двух. При этом для каждой выходящей дуги известно, является ли она правой или левой. Каждая вершина бинарного дерева, отличная от корня, может рассматриваться как корень бинарного поддерева с вершинами, достижимыми из нее. [2]
Бинарное дерево рассматривается в тл. [3]
Бинарное дерево представляет собой древовидную структуру с двоичным ветвлением, в которой каждый узел содержит данные и два прямых указателя. [4]
Бинарное дерево может быть пусто, и каждый из его узлов может иметь О, 1 либо 2 сына; мы делаем различие между правым и левым сыном даже в том случае, когда узел имеет лишь одного сына. [5]
Бинарное дерево В ( F), соответствующее F, можно строго определить следующим образом. [6]
Бинарное дерево может быть пустым, и каждый его узел не может иметь более двух потомков. [7]
Бинарное дерево называется упорядоченным, если его узлы могут быть перечислены в порядке неубывания веса и в этом перечне узлы, имеющие общего родителя, должны находиться рядом, на одном ярусе. Причем перечисление должно идти по ярусам снизу-вверх и слева-направо в каждом ярусе. [8]
Бинарное дерево называется Н - деревом, если все висячие вершины находятся на одном и том же уровне и каждая вершина с единственным потомком имеет правого соседа с двумя потомками. [9]
Бинарное дерево представляет собой структуру, в которой каждый узел ( или вершина) имеет не более двух узлов-потомков и в точности одного родителя. Самый верхний узел дерева является единственным узлом без родителей; он называется корневым узлом. Например, у полного бинарного дерева с 15 узлами один корень, два узла на втором уровне, четыре узла на третьем уровне и восемь узлов на четвертом уровне; наше равенство также дает [ Iog2 15J 1 - 3.9 j 1 4 уровня. [10]
Бинарное дерево называется HS-деревом, если справедливо следующее: все висячие вершины находятся на одном уровне, и если вершина х имеет только одного потомка, то этот потомок есть либо висячая вершина, либо сам имеет двух потомков. [11]
Бинарное дерево решений для сортировки трех имен. [12]
Пусть бинарное дерево расширено указанным способом. Длина внешнего пути дерева Е равна взятой по всем концевым ( квадратным) узлам сумме длин, путей от корня к каждому узлу. Длина внутреннего пути I равна такой же сумме, но взятой по всем неконцевым ( круглым) узлам. [13]
Такое бинарное дерево называют также бинарным деревом поиска. [14]
Определим бинарное дерево как структуру данных, состоящую из узлов, содержащих три поля: значение, левый потомок, правый потомок. В дереве имеется выделенный узел, корень, не являющийся потомком ни одного из узлов. [15]