Создание двоичного дерева из Pre и In

Question

Я пытаюсь построить двоичное дерево из In-order и Pre-order. Каждый узел имеет целочисленное значение для данных. я столкнулся с проблемой при наличии этих массивов:

Предзаказ: 3,9,2,6,1,1,1,4
В-заказ: 2,9,3,1, 1,1,6,4

Это оригинальное дерево, из которого были извлечены из обходы:

3 
/\ 
    9 6 
//\ 
2 1 4 
/\ 
    1 1 

проблема заключается в том, что функция, которую я написал не может отличить последовательные равные числа.

Это функция в C:

TREE createTreeFromPreAndIn(int pre[], int in[], int n){ 
    TREE res; 
    res.root = createTreeFromPreAndInHelper(pre, in, n); 
    return res; 
} 

TNODE* createTreeFromPreAndInHelper(int pre[], int in[], int n){ 
    int index; 
    TNODE* rootL, *rootR, *root; 

    if (n == 0) 
     return NULL; 
    else { 
     index = findIndex(in, n, pre[0]); //returns the index of the first appearance of pre[0] in 'in' 
     rootL = createTreeFromPreAndInHelper(pre+1, in, index); 
     rootR = createTreeFromPreAndInHelper(pre+1+index, in+index+1, n-index-1); 
     root = createNewTreeNode(pre[0], rootL, rootR); 
     return root; 
    } 
} 

Заранее спасибо

Answer 1

Вы не имеете достаточно требование, чтобы определить точное изображение. Ваше дерево выше, также может быть выражено как

   Fig 1      Fig 2      Fig 3 

       3       3       3 
      /\      /\      /\ 
       9 6      9 6      9 6 
      //\     //\     //\ 
      2 1 4     2 1 4     2 1 4 
      /\      /       \ 
       1 1      1        1 
             /       /
             1        1 

Все вышеприведенном дерево дает то же самое в заказ и наборы Предварительный заказ в соответствии с вашими инициировании.

В-порядке = {2,9,3,1,1,1,6,4}

Предзаказ = {3,9,2,6,1,1,1,4}

Существует двусмысленность. Таким образом, вы не можете определить точное дерево с этой информацией. Вы должны указать дополнительную информацию для работы с этой проблемой.

Если вы хотите его заново создать, вы можете попробовать включить границы в массив.

Для примера: Используйте -1 для указания no-child (Предполагая, что значения моего узла не будут равны -1 в любом случае).

Рисунок 1:

В-порядке: {-1,2, -1,9, -1,3, -1,1, -1,1, -1,1, - 1,6, -1,4, -1}

Предзаказ: {3,9,2, -1, -1, -1,6,1,1, -1, -1,1, -1, -1,4, -1, -1}

Рисунок 2:

В-порядке: {-1,2, -1,9, -1,3, -1, 1, -1,1, -1,1, -1,6, -1,4, -1}

Предзаказ: {3,9,2, -1, -1, -1,6,1,1,1, -1, -1, -1, -1,4, -1, -1}

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

Answer 2

Неоднозначность возникает из-за того, что узлы листа не определены полностью. Определите местозаполнитель (0 или -1) для узлов, которые не должны быть построены, и USE parens, чтобы показать структуру списка.

Предзаказ: 3 (9 (2) (0)) (6 (1 (1) (1)) (4)) с парсером и нумератором без парнов одна и та же последовательность чисел может быть " в скобках "как 3 (9 (2) (0)) (6 (1) (1 (1) (4))).

Дублированные номера не имеют ничего общего с двусмысленностью. Число не определяет свое место в структуре. Скорее, тот факт, что это двоичное дерево предзаказов, где каждый узел (т. Е. Родительский) имеет, по определению, левого и правого детей, но каждый ребенок может быть родителем с двумя детьми! Таким образом, список элементов должен «заполнить» дерево до его листьев.