Преобразовать двоичное дерево в зигзагообразном порядке в двусвязный список - PullRequest
Новая
       26

Преобразовать двоичное дерево в зигзагообразном порядке в двусвязный список

0 голосов
/ 12 марта 2011

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

 Given BT:
                 [1]
          [2]                  [3]
      [4]      [5]         [6]        [7]
    [8]  [9] [10] [11] [12] [13] [14] [15]</p>

<p>ZigZag order of BT in DLL:
      [1] [3] [2] [4] [5] [6] [7] [15] [14] [13] [12] [11] [10] [9] [8]

Вот мой псевдокод: 

DLLNode* ConvertBTToZigZgDLL(Node* root)
{
  DLLNode* start=createDLLNode(root->data);
  DLLNode* tail=start;
  Stack<Node> stack1, stack2;
  stack1.push(root->left);
  stack1.push(root->right);
  while( !stack1.Empty() || !stack2.Empty() )
  {
     while(stack1.HasElement())
     {
       Node* temp=stack1.Pop();
       stack2.push(temp->right);
       stack2.push(temp->left);
       tail=Attach(tail,createDLLNode(temp->data));
       tail=tail->next;
     }
     while(stack2.HasElement())
     {
       Node* temp=stack2.Pop();
       stack1.push(temp->left);
       stack1.push(temp->right);
       tail=Attach(tail,createDLLNode(temp->data));
       tail=tail->next;
     }
  }
  return start;

} Здесь TimeComplexity O (N), где N - это количество узлов в данном двоичном дереве. 


  DLLNode* Attach(DLLNode* source, DLLNode* dest)
  {
     source.Next=dest;
     dest.prev=source;
     return source;
  }

  DLLNode* CreateDLLNode(int data)
  {
    DLLNode* res=malloc(sizeof(struct DLLNode));
    res->data=data;
    res->prev=NULL;
    res->next=NULL;
    return res;
   }

Все, что я хочу знать что не так в логике моего кода.

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

Просто проверьте логику моего кода и дайте мне знать.

Моя логика проста: используйте 2 стека. В stack1 я всегда толкаю сначала левого потомка, а затем правого потомка, а в stack2 я всегда толкаю правого потомка сначала, а левого потомка вторым. изначально загружает stack1, в то время как stack1 не является пустым pop и помещает соответствующие правые / левые дочерние узлы в stack2. Для приведенного выше примера мои состояния стека должны быть такими: s1-B [2,3] T s2-B [7,6,5,4] T s1-B [8,9,10,11,12,13,14, 15] T B-стека снизу T-стека сверху. Пожалуйста, проверьте еще раз. спасибо.

Ответы [ 2 ]

1 голос
/ 13 марта 2011

Алгоритм:

Использовать модифицированный алгоритм BFS, где вместо одной очереди fifo используются два стека stack1 используется для размещения узлов на уровнях, которые должны быть посещены справа налево,в то время как stack2 содержит узлы, которые необходимо посетить слева направо.

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

Для общего доказательства случая, предполагая, что элементы в stack1 хранятся в правильном порядке, вытягивая узлы из stack1 для уровня N гарантирует, что они обрабатываются в порядке справа налево.Для каждого обработанного таким образом узла поддеревья сохраняются в stack2 сначала справа, а затем слева.Это гарантирует, что список узлов , извлеченных из stack2 для уровня N + 1, имеет порядок слева направо.Цикл while завершается, когда больше нет узлов на уровне N. В этот момент извлечение узлов из stack2 извлечет все узлы с уровня N + 1 в порядке слева направо.

И наоборот, при вытягивании узлов из stack2 на каждом уровне слева направо, дочерние узлы сохраняются в stack1 сначала слева, затем справа, гарантируя, что когда они будут извлечены на следующей итерации в порядке справа налево.

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

1 голос
/ 12 марта 2011

Это уже рассмотрено в другом вопросе.

См. этот набор ответов для стекового обзора .

...