привет, я реализовал bst в mips, и мне нужно распечатать это дерево. Каждый узел имеет следующие четыре информации
его значение
адрес родителей
оставил адрес ребенка
правильный адрес ребенка
я должен напечатать дерево в следующем формате. (x означает отсутствие ребенка)
12
8-16
x-9 13-17
x-x x-11 x-x x-x
Не могли бы вы предложить способ реализации этого метода печати?
Порядок, в котором вы печатаете дерево, представляет собой обход в ширину (уровень за уровнем). Один из вариантов может быть следующим: поддерживать рабочий список, изначально засеянный корнем дерева. Затем повторно удалите из рабочего списка очередь, распечатайте текущий элемент (или x, если его нет), затем добавьте двух дочерних элементов в рабочий список. Вам понадобится какой-то способ отслеживать, когда вы закончите обход дерева, возможно, сначала подсчитав количество узлов и остановившись, как только вы напечатаете это количество узлов.
Тем не менее, поскольку вы делаете это в MIPS, один из более простых вариантов — линеаризовать дерево в массив, а затем распечатать массив. Если вы нумеруете узлы так же, как вы нумеруете узлы в неявной двоичной куче, вы можете рекурсивно/итеративно пройтись по дереву, заполнить массив узлами дерева, а затем пройтись по массиву, распечатав все.
Надеюсь это поможет!
Поскольку вам нужно печатать уровень за уровнем вашего двоичного дерева, наиболее очевидный способ вывода информации — пройти по дереву, используя метод поиска в ширину. Остальное просто и не должно быть проблемой. :)
