ПУТЕШЕСТВИЕ - ВСТАВИТЬ - УДАЛИТЬ - ОБЪЕДИНИТЬ

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

Мы обновили наше предыдущее дерево на основе массива «MyLinearTree» до «MyUpgradedLinearTree», которое следует основным правилам ООП ;-) и многие новые функции.

вот сигнатура метода структуры 4 операций.

public String[] traverseTree();
public int searchTree(String key);
public boolean insertNode(String key);
public String deleteNode(String key);
public void mergeTree(MyLinkedTree firstTree,MyLinkedTree secondTree);

они не выглядят так чудесно, не так ли? ну почему бы нам не судить об этом.

Строим наше дерево:

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

Путешествие по нашему дереву:

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

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

1–2–4–5–3–6–7

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

4–2–5–1–6–3–7

Пост-заказ: вы выбираете левый узел, затем правый узел, а затем родительский узел, как показано ниже.

4–5–2–6–7–3–1

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

Вставка узла листа в наше дерево:

как показано в нашем методе insertNodeLeaf, он вызывает другой частный метод (один из многих, где вы можете скрыть дизайн реализации вашего метода… подмигнуть, подмигнуть ;-)), а также в глазах пользователя вашего класса ваш код становится soigné! Чтобы упростить работу по вставке листового узла, мы просто перейдем к левому углу нашего дерева (когда node.leftNode станет нулевым, мы можем безопасно вставить листовой узел) и добавить новый узел, используя предварительный обход .

Удаление узла из нашего дерева:

Задача удаления узла не так уж и сложна, достаточно выполнить пару логических шагов и БУМ !!! вы уничтожили узел дерева.

Сначала вам нужно выполнить поиск по всему дереву, используя любой из методов обхода, и, обнаружив узел, который нужно удалить, мы спросим, ​​есть ли у узла два дочерних элемента? то его нельзя удалить. Что ж, жестоко отказываться от двух детей, родительский узел не может ссылаться на обоих детей. таким образом такая попытка НЕВОЗМОЖНА.

Если у узла есть только один дочерний элемент, что ж, прародитель может справиться с одиноким дочерним элементом! (нет одиноких песен для ребенка). Но как вы относитесь к прародителю ребенка или родителю «удаляемого узла». Как показано на изображении ниже, у узла есть ссылка на его родительский узел !!! просто загляните в наш метод buildingTree, есть ссылка на родителя только что созданного узла. Как сказал величайший детектив Шерлок Холмс: «Это не случайно, это сделано по замыслу !!!»

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

Надеюсь, вам понравилось 3/4 операций с деревом, четвертая - слияние двух деревьев - осталась для практики до следующего эпизода.

Ваши аплодисменты и комментарии предпочтительнее. Я увижу вас с большим количеством действий по кодированию, которые мир видел или не видел раньше (я не думаю, что это имеет значение в любом случае). ваше здоровье