ПУТЕШЕСТВИЕ - ВСТАВИТЬ - УДАЛИТЬ - ОБЪЕДИНИТЬ
В нашей предыдущей статье мы использовали массив для хранения двоичных данных в памяти, и этот массив, к сожалению, не оставит нас в ближайшее время, на самом деле мы обновили наши в некоторой степени, чтобы дать разработчику возможность поразмышлять о практичности как массива, так и связанного списка в нашем стремлении овладеть чудесами структуры данных 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 операций с деревом, четвертая - слияние двух деревьев - осталась для практики до следующего эпизода.
Ваши аплодисменты и комментарии предпочтительнее. Я увижу вас с большим количеством действий по кодированию, которые мир видел или не видел раньше (я не думаю, что это имеет значение в любом случае). ваше здоровье