Не удалось построить двоичное дерево из тестового примера родительского массива - PullRequest
Новая
       29

Не удалось построить двоичное дерево из тестового примера родительского массива

0 голосов
/ 10 июля 2020

Ссылка на вопрос- [Ссылка] [1]

В основном нам дается массив целых чисел и его размер. Вопрос в том, чтобы построить из него бинарное дерево. Каждый индекс соответствует данным, хранящимся в узле, а значение этого индекса является данными родителя. Значение индекса узла root всегда будет -1, так как для root нет родительского элемента. Результатом будет отсортированный обход дерева в порядке уровней.

Теперь мой подход состоит в том, что я анализирую массив от 1 до n (не 0-й элемент / root узел), и для каждого элемента я получить его родителем, используя первую функцию, и соответственно вставить дочерний элемент. Но один конкретный тестовый пример терпит неудачу. Возможно, собственный вывод веб-сайта неверен. Я опубликую все ниже: -

Пример тестового примера -

Размер массива-7

Элементы- -1 0 0 1 1 3 5

Выход - 0 1 2 3 4 5 6

Частный тестовый пример (в чем я сомневаюсь) -

Размер массива - 42

Элементы - 3 19 1 41 35 29 27 11 17 23 9 15 33 13 39 23 19 25 21 1 33 15 31 21 5 7 37 29 7 11 31 39 -1 27 3 9 25 17 13 41 37 35

Вывод веб-сайта - 32

Мой вывод - 0

Функции 


void getParent(Node* root, int val, Node* &main)
{
    if(root==NULL) return;
    if(root->data==val){
        main=root;
        return;
    }
    getParent(root->left,val,main);
    getParent(root->right,val,main);
    
}

Node *createTree(int parent[], int n)
{
    if(n==0) return NULL;
    Node * root=new Node(0);
    for(int i=1;i<n;i++)
    {
        Node* main=NULL;
        getParent(root,parent[i],main);
        //main has the parent
        
        Node* child=new Node(i);
        if(main==NULL) break;
        
        
        if(main->left==NULL)
        {
            main->left=child;
        }
        else if(main->right==NULL)
        {
            main->right=child;
        }
    }
    return root;
} 


  [1]: https://www.geeksforgeeks.org/construct-a-binary-tree-from-parent-array-representation/
  [2]: https://i.stack.imgur.com/0fRmn.png

1 Ответ

0 голосов
/ 10 июля 2020

Не уверен, что вы делаете со своим getParent методом. Также вы запускаете узел root со значением 0 и ничего не делаете с ним в l oop, а затем, наконец, возвращаете root. Я подозреваю, что ваш root всегда будет иметь значение 0.

На самом деле решение очень простое. Вы инициализируете массив узлов со значением каждого узла в качестве индекса массива. Например, для массива размером 5 вы создаете массив из 5 узлов, каждый из которых имеет значение индекса, в котором он расположен.

Затем следующий шаг - go через массив parent и посмотрите, есть ли у узла, расположенного в parent[i], left или right "доступно", если да, назначьте узел соответственно.

код: 

Node* createTree(int parent[], int n) {
  Node** nodes = new Node*[n];
  for ( int i = 0; i < n; i++ )
      nodes[i] = new Node(i);
  int rootIndex = 0;
  for ( int i  = 0; i < n; i++ ) {
    if ( parent[i] == -1 ) {
      rootIndex = i;
    } else {
      if ( nodes[parent[i]] -> left == NULL ) {
        nodes[parent[i]] -> left = nodes[i];
      } else if ( nodes[parent[i]] -> right == NULL ) {
          nodes[parent[i]] -> right = nodes[i];
      }
    }
    
  }
  return nodes[rootIndex];
}
...