Вставка порядка уровней в двоичное дерево? - PullRequest
8 голосов
/ 02 июля 2011

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

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

Например:

Пусть a [] = {A, B, C, D, E, F, G};// выходной поток в массиве

Таким образом, дерево порядка уровней будет выглядеть так:

            A
           / \ 
          B   C
        / \  / \
       D   E F  G

Предположим, что существует структура древовидного узла, например:

typedef struct node
{
    char data;
    struct node* left;
    struct node* right;
}tree;

Теперь я пытаюсь прочитать значения [] и закодировать это дерево, чтобы оно выглядело как диаграмма.Существует много примеров порядка уровней traversal , но не удалось найти ничего подходящего для фактического кодирования для двоичного дерева construction .Это своего рода «обратный ход».

Также обратите внимание, что это не домашняя работа, хотя у меня нет проблем с ее пометкой, если больше людей заметят это таким образом.:)

Ответы [ 4 ]

6 голосов
/ 02 июля 2011

Это похоже на BFS , поэтому вы можете использовать очередь .

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

5 голосов
/ 02 июля 2011

Одно из возможных решений:

char a[SIZE] = {A,B,C,D,E,F,G}; 
    node* func(int index){
        if(index < SIZE){
            node *tmp = new node();
            tmp->data = a[index];
            tmp->left = func(2*index + 1);
            tmp->right = func(2*index + 2);
        }
        return tmp;
    }

трассировка стека для дерева:

                                     A->a[0]
          B->func(2*0 + 1)=[1]                              C->func(2*0 + 2)=[2]
D->func(2*1 + 1)=[3]    E->func(2*1 + 2)=[4]        F->func(2*2 + 1)=[5]     G->func(2*2 + 2)=[6]
5 голосов
/ 02 июля 2011

Для полного (или заполняющего) двоичного дерева легко преобразовать обход уровня в любой обход, потому что дочерние узлы в позиции n находятся в 2n и 2n+1, когдамассив имеет индекс 1 и имеет значения 2n+1 и 2n+2, если массив проиндексирован 0 .

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

например, рекурсивный псевдокод:

void fill( TreeNode* node, char a[], int arrayLength, int n ){
    // n is the position of the current "node" in the array
    if( n < arrayLength ){
        node->data = a[n];
        fill( node->left, a, arrayLength, 2n+1 );
        fill( node->right, a, arrayLength, 2n+2 );
    }
}
2 голосов
/ 02 июля 2011

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

node* theTree (char[] a, int arraylength) {
   if (arraylength == 0) return NULL;

   node** nodes = new node*[arraylength];
   nodes[0] = new node();
   nodes[0]->data = a[0];

   for (int i = 0, j = 0; TRUE ; j++) {
      if (++i >= arraylength) return nodes[0];

      nodes[i] = new node();
      nodes[i]->data = a[i];
      nodes[j]->left = nodes[i];

      if (++i >= arraylength) return nodes[0];

      nodes[i] = new node();
      nodes[i]->data = a[i];
      nodes[j]->right = nodes[i];
   }
}

Возможные улучшения включают сокращение необходимой памяти в два раза путем перезаписи части массива указателей при i> arraylength / 2 и, возможно, предварительного выделения всех узловсразу в массиве (хотя тогда вам нужно быть осторожным с освобождением).

...