У меня проблема с бинарными деревьями.Значения вставки для пустого двоичного дерева
Они дали, что
Начиная от пустой двоичного дерева поиска, введение которого из следующих последовательностей целочисленных keyscould производят бинарное дерево выше?
Не мог бы кто-нибудь прокомментировать объяснение этой логики.
Ответ указан как 5, 3, 4, 9, 1, 7 .. Может кто-то объяснить, как это может быть.
При вставке узла в двоичное дерево поиска вы сравниваете его с каждым узлом, начиная с корня. Если он больше текущего узла, сходите вниз по правой ветке и вставьте его туда. В противном случае, опустите левую ветвь и вставьте ее туда. Если нет ветви, то вы нашли место для вставки узла.
Следуйте этому правилу, начиная с пустого дерева и пробуйте заданные значения, пока не получите дерево, которое они вам дали.
Ответ дается как 5, 3, 4, 9, 1, 7. как это может быть. – user3789200
Вы видите только последовательность. Нет другого выбора?
Существует несколько последовательностей, которые могут генерировать двоичное дерево поиска.
Дано любое двоичное дерево поиска, последовательностью вставки, которая его производит, является его обход предварительного порядка.
Причина в том, что при вставке узлы, которые уже вставлены, не меняют положение. Каждый новый узел, который вы вставляете, помещается как дочерний элемент неполного узла.
Вставка симметричного обхода предварительного порядка, то есть посещение корня, а затем посещение в предварительно упорядоченном поддереве и, наконец, посещение в предварительном порядке, левое поддерево также создает одно и то же дерево.
В общем случае вставка любого варианта обхода предзаказа дает исходное дерево.
Кроме того, вставка обхода уровня, то есть сначала корень, затем узлы второго уровня и т. Д., Создает исходное двоичное дерево поиска. Обратите внимание, что вы можете переставлять узлы одного уровня, и результат будет таким же.
Не существует определенной схемы, по которой элементы попадают в двоичное дерево. Вероятно, вы хотите знать, как это работает в двоичном * поиске *. – oarfish