Создайте дерево

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

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

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

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

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

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

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

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

Вопиющая копия и вставка с форума Sun's (Oracle now, I guess...):

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

Answer:
Let 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 respectively.

Удалить элемент 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. Это корень левого поддерева исходного дерева. Split 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.

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