Дерево Абстрактный Тип данных

Question

Я делаю блок под названием Структуры данных и алгоритмы. Мы только начали, и мой профессор только что научил нас основам алгебраической семантики, аксиом и т. Д. До сих пор я использовал деревья только в виде массивов. Не использовать подпись для предварительно упорядоченного дерева в качестве дерева (значение, дерево, дерево), где значение - это значение в узле, левый узел - это первое дерево, а правый узел - второе дерево.

Теперь, когда я определяю свое дерево как дерево (значение, дерево, дерево) или как ноль, я не могу понять, как определить алгебру для addNode (значение, дерево).

С каждым уровнем все сложнее и сложнее, плюс, я никак не могу подумать о том, чтобы сканировать один уровень, как когда-то, пытаясь вот уже как час. Когда мы спускаемся по дереву, алгебра просто разветвляется на все больше и больше if-эльсов. Я делаю это правильно? Можете ли вы указать мне правильное направление? Или деревья не могут быть реализованы как дерево (значение, дерево, дерево)?

Это часть моего урока (не стоит никаких оценок по дополнительным вопросам), но я не ищу мгновенного ответа, мне нравится предмет, и я хотел бы узнать больше.

Редактировать 1: я проверил Википедию, и я не хочу использовать учебник для четкого ответа, я просто ищу подсказку в правильном направлении, является ли мой подход правильным или совершенно невозможно определить дерево как дерево (значение, дерево, дерево). Я знаю, что вы можете представить дерево ADT в форме списка. Но я хотел действительно подумать об этом. Надеюсь, это имеет смысл. Большое спасибо, ребята!

Редактировать 2: Хм, это трудно объяснить через Интернет. Допустим, я определяю новую структуру данных под названием «дерево». Я могу определить его так, как я хочу, и он должен вести себя как сбалансированное двоичное дерево (хотя значения родителей и детей не имеют значения) Поэтому я определяю его как дерево: дерево (значение, дерево, дерево) ИЛИ ноль Это не программный код, это просто то, как я его определяю. Tree - это значение + 2 других дерева или Tree - ноль. Теперь addNode (значение, дерево) добавляет узел в дерево, сохраняя его сбалансированным. Это не программный код, это просто алгебраическая семантика. Я не знаю, смогу ли я объяснить это правильно. Но я нашел решение, которого я могу достичь с помощью очередей или стеков, но это еще один ADT, который я должен определить, который недопустим.

Редактировать 3: Похоже, я предположил много вещей, которые сделали проблему сложнее, чем она должна была быть на самом деле. Прежде всего, из небольшого объяснения, которое я дал, Gamecat ответил идеально. Но я согласен с комментариями, вполне допустимо включать другие ADT. Фактически, когда мы строим что-либо, использующее Int, мы используем ADT для этой структуры. Я думал, что каждый ADT должен быть уникальным. В любом случае, большое спасибо, ребята, за ваши ответы!

Answer 1

Если вы хотите добавить узел в дерево, вы можете использовать рекурсивную функцию.

Я предполагаю, что дерево упорядочено. Таким образом, вы должны получить что-то вроде этого:

AddNode(value, tree)

if tree is empty, create a new tree with value as node and no subtrees.
if value lesser than the treenode, call AddNode on the left branch.
else call AddNode on the right branch. (if duplicates are allowed).

Обязательно обновите поддеревья, если они изменились!

Вы можете преобразовать это в нерекурсивную функцию следующим образом:

if tree is empty, return a new tree with value as node and no subtrees.
if value is lesser than treenode, and there is no left subtree, create a new left subtree with value as node and no subtrees.
if value is lesser that treenode, and there is a left subtree, try again with the left subtree.
if value is greater or equal than treenode, and there is no right subtree, create a new right subtree with value as node and no subtrees.
if value is greater or equal than treenode, and there is a right subtree, try again with the right subtree.

Если дерево должно быть сбалансировано. Вам необходимо хранить балансир (который может быть -1, 0 или 1). Если вам нужно добавить узел на "Heavy" сайт, вам нужно переставить это. Например, если левая сторона на один узел больше правой, и вам нужно добавить еще один узел слева. Вам нужно получить узел с наибольшим значением из левого поддерева и повысить его до текущей вершины. Предыдущая вершина добавляется в правое поддерево. Убедитесь, что поддеревья также сбалансированы.

Пример: добавление узлов 0,1,2,3,4

Add(0)           0

Add(1)           0
                  \
                   1

Add(2)           0 (2)  =>      1 (2) =>  1
                  \            /         / \
                   1          0         0   2

Add(3)           1
                / \
               0   2
                    \ 
                     3

Add(4)           1 (4)     => 2 (4)  =>      2
                / \          / \            / \
               0   2        1   3          1   3
                    \      /              /     \
                     3    0              0       4

Answer 2

Это сложный вопрос, так как он очень расплывчатый. Я предполагаю, что у вас есть учебник или что-то похожее как часть вашего материала курса. Несмотря на это, создается впечатление, что многие вещи, с которыми у вас возникают проблемы, объясняются базовым ресурсом, таким как запись в Википедии на бинарные деревья.

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