Построить дерево

Question

Как я могу построить дерево, учитывая его обход и порядок? Я просто ищу эффективный алгоритм.

Answer 1

Явное копирование и вставка с форума Sun (Oracle сейчас, я думаю ...) :

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

Ответ:
Пусть p_1, p_2 ... p_n будет обходом по порядку и пусть i_1, i_2 ... i_n будет обходом по порядку. Из прохождения заказа мы узнаем, что корень дерева - p_n. Найдите этот элемент в обходе порядка, скажем i_1, i_2 ... i_k-1 p_n i_k+1 ... i_n. Из прохождения по порядку мы находим все элементы в левом поддереве, то есть i_1, i_2 ... i_k-1 и в правом поддереве, т.е. i_k+1 ... i_n соответственно.

Удалить элемент p_n (и элемент i_k == p_n). Найдите самый правый элемент p_j в p_1, p_2 ... p_j ... p_n-1, где p_j - элемент в i_1, i_2 ... i_k-1. Это корень левого поддерева исходного дерева. Сплит p_1, p_2 ... p_j и p_j+1 ... p_n-1 и i_1, i_2 ... i_k-1 и i_k+1 ... i_n. Теперь у вас есть две подпоследовательности, представляющие порядок и порядок обхода двух поддеревьев оригинала. дерево.

Автор: JosAH .

Я однажды реализовал алгоритм, следуя инструкциям Джоса, и он отлично работал!

Answer 2

Так как это домашнее задание, я не буду давать вам полный ответ, но, надеюсь, достаточно, чтобы вы двигались.

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

Обход дает вам 2-7-2-6-5-11-5 ... и т. Д. Обратите внимание, что 5 на самом деле является правильным потомком корня.

Очевидно, что вы не можете определить это, просто взглянув на числа, поэтому либо вам сообщат о структуре дерева, либо вам нужно будет сохранить некоторые дополнительные данные (т. Е. Является ли узел левым потомком или правильный ребенок, например).

Синтаксический анализ дерева - это просто рекурсивная функция, которая принимает прохождение предварительного заказа в качестве входных данных (подумайте о своей области действия, когда вы передаете входные данные). Как я упоминал ранее, к вашему обходу по предварительному заказу должны быть приложены некоторые дополнительные данные.

---

Эффективность:

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

---

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