Двоичное дерево от заказа и порядка

Question

Я только что начал изучать Двоичное дерево. Есть ли алгоритм, чтобы узнать структуру двоичного дерева, учитывая Inorder и Postorder OR Inorder и Preorder? Я пытался сделать это вручную, но она никогда не выходит correct.For eg.-Эти два действительна Симметричная и Postorder обходу данного дерева:

Симметричный: DBFEAGCLJHK Postorder: DFEBGLJKHCA

Ясно, что А является корнем, поскольку он является последним элементом в Postorder. Теперь, глядя в Inorder, левое поддерево становится: {D B F E}, а правое поддерево становится: {G C L J H K}. Корень правого поддерева будет вторым последним элементом в preorder i.e C. Теперь я могу разделить правое поддерево (с C как root), давая {G} как правое поддерево и {L J H K} как левое. Поэтому у меня есть эта структура:

       A 
           \ 
           C 
           / 
           G 

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

Answer 1

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

Если ваш просто пытается получить лучшее понимание бинарных деревьев, это может объяснить это немного лучше: http://www.youtube.com/watch?v=ZkH3SSPwcwI

Answer 2

Пусть заказовМои и Предзаказ обходы быть приведены в IOrder массивы и porder соответственно.

Функция построения дерева будет обозначаться buildTree (i, j, k), где i, j относится к диапазону массива inorder, на который нужно смотреть, и k - позиция в массиве предзаказов.

Первоначальный вызов будет buildTree (0, п-1,0)

Алгоритм имеет следующие шаги:

1. Траверс porder от начала. Первым узлом является корень, тогда у нас есть левое поддерево, а затем правое поддерево. Создайте узел с этим как элементом.

2. Поиск узла в массиве iorder. Предположим, что его найдено в точке x. Сокращение k. k относится к позиции в массиве porder, в котором мы сейчас находимся. k должен быть передан по ссылке.

3. Наконец заполнить левую ребенку и правильный ребенок с возвращаемым значением рекурсивных вызовов левого потомок = buildTree (I, X-1, к) права ребенка = buildTree (х + 1, J, K)

4. В конце концов вернет узел

PS: Got код принят с выше алгоритма на

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=477