Как вывести обход дерева по предварительному заказу с учетом трансверса по порядку и по порядку? - PullRequest
Новая
       27

Как вывести обход дерева по предварительному заказу с учетом трансверса по порядку и по порядку?

3 голосов
/ 09 июня 2010

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

void postorder( int preorder[], int prestart, int inorder[], int inostart, int length)
{ 
  if(length==0) return; //terminating condition
  int i;
  for(i=inostart; i<inostart+length; i++)
    if(preorder[prestart]==inorder[i])//break when found root in inorder array
      break;
  postorder(preorder, prestart+1, inorder, inostart, i-inostart);
  postorder(preorder, prestart+i-inostart+1, inorder, i+1, length-i+inostart-1);
  cout<<preorder[prestart]<<" ";
}

Вот прототип для preorder ()

void preorder (int inorderorder [], int inostart, intpostorder [], int poststart, int length)

для использования postorder () будет 

int preorder[6]={6,4,1,5,8,9};
int inorder[6]={1,4,5,6,8,9};
postorder( preorder,0,inorder,0,6);

, на выходе будет 

1 5 4 9 8 6

ниже указан неверныйкод для print_preorder (), все еще не работает ниже 

void print_preorder( int inorder[], int inostart, int postorder[], int poststart, int length)
    {
      if(length==0) return; //terminating condition
      int i;
      for(i=inostart; i<inostart+length; i++)
        if(postorder[poststart+length-1]==inorder[i])
          break; 
      cout<<postorder[poststart+length-1]<<" ";
      print_preorder(inorder, inostart , postorder, poststart, i-inostart);
      print_preorder(inorder, inostart+i-poststart+1, postorder, i+1, length-i+inostart-1);
    }

Ответы [ 2 ]

9 голосов
/ 09 июня 2010

Вот несколько подсказок:

  • Последний элемент в подмассиве postorder - это ваш новый preorder корень.
  • Массив inorder можно разделить на две части по обе стороны от нового корня preorder.
  • Вы можете вызвать рекурсивный вызов функции print_preorder на этих двух inorder подмассивах.
  • При вызове функции print_preorder массивы inorder и postorder будут иметь одинаковый размер.
  • У вас есть доступ к массиву вне границ: postorder[poststart+length] находится за концом массива. Чтобы получить последний элемент, вы хотите postorder[poststart+length-1]
  • Ваша первая рекурсивная функция print_preorder выбирает неправильную длину. Помните, что length - это длина подмассива, но inostart - это абсолютная позиция в массиве inorder. Ваша функция, вероятно, будет вызывать с отрицательным length.
  • Ваша вторая рекурсивная функция довольно далека для перевода границ и длины. Это, вероятно, поможет нарисовать его на бумаге и проследить ваш алгоритм.

Может помочь нарисовать дерево: 

     6
   /   \
  4     8
 / \     \
1   5     9

Затем запишите три обхода: 

// index:         0 1 2 3 4 5
int postorder[6]={1,5,4,9,8,6};
int inorder[6]=  {1,4,5,6,8,9};
int preorder[6]= {6,4,1,5,8,9};

Теперь положи компьютер, достань ручку и бумагу и подумай о проблеме:)

Представьте себе этот стек вызовов (новый корень напечатан слева): 

6 print_preorder(len=6, in=[1 4 5 6 8 9], post=[1 5 4 9 8 6])
4 |-> print_preorder(len=3, in=[1 4 5], post=[1 5 4])
1 |   |-> print_preorder(len=1, in=[1], post=[1])
  |   |   |-> print_preorder(len=0, in=[], post=[])
  |   |   |-> print_preorder(len=0, in=[], post=[])
5 |   |-> print_preorder(len=1, in=[5], post=[5])
  |       |-> print_preorder(len=0, in=[], post=[])
  |       |-> print_preorder(len=0, in=[], post=[])
8 |-> print_preorder(len=2, in=[8 9], post=[9 8])
      |-> print_preorder(len=0, in=[], post=[])
9     |-> print_preorder(len=1, in=[9], post=[9])
          |-> print_preorder(len=0, in=[], post=[])
          |-> print_preorder(len=0, in=[], post=[])

Удачи:)

4 голосов
/ 24 мая 2014

  1. Последним элементом в почтовом заказе будет корень дерева.

  2. После этого мы посмотрим в массив Inorder, чтобы определить положение корня,левая сторона массива - это левое поддерево, а правая - правое поддерево.

  3. Используя этот индекс, мы определим элемент слева, который является корнем.

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

    public static void printpreorder(char []inorder,int i_start,int i_end,char[] postorder,int p_start,int p_end)
{
  if(i_start > i_end || p_start > p_end)
         return ; 
  char root = postorder[p_end];
  System.out.print(root);
  System.out.print("(");
    int k=0;
      for(int i=0; i< inorder.length; i++){
          if(inorder[i]==root){
            k = i;
            break;
          }
      }
  printpreorder(inorder, i_start, k-1, postorder, p_start, p_start+k-(i_start+1));
  System.out.print(")(");
  printpreorder(inorder, k+1, i_end, postorder, p_start+k-i_start, p_end-1);
  System.out.print(")");    
}

Это было для меня просто задом.Спасибо @Stephen за хороший ответ

...