Блог

Постановка задачи: выведите вид сверху двоичного дерева

Мой подход: я поддерживаю очередь, внутри которой есть пара для root->data и horizontal distance(hd) . Я помещаю корень hd в очередь и добавляю его в тот map , который содержит hd и root->data . Затем я выскакиваю из очереди. Теперь, если есть какие-либо дочерние элементы выскочившего корня, я вставляю их в очередь, и описанная выше процедура продолжается до тех пор, пока очередь не станет пустой.

Мой код :-

 void topView(Node * root) {
        queue<pair<int, int>> q;
        map<int, int> m;
        q.push({root->data, 0});
        while(q.empty() == false){
            int node_val = q.front().first;
            int hd = q.front().second;
            m[hd] =node_val;
            q.pop();
            if(root->left){
                int hdl = hd -1;
                q.push({root->left->data, hdl});
            }
            if(root->right){
                int hdr = hd   1;
                q.push({root->right->data, hdr});

            }


        }
        for(auto i=m.begin();i!=m.end();i  ) 
        { 
            cout<<i->second<<" "; 
        } 
    }
  

** ОШИБКА: ** Превышение ограничения по времени (то есть выполнение кода не прекращается)

** ПРИМЕЧАНИЕ **: Кроме того, я обнаружил, что не могу правильно обновить «расстояние по горизонтали (hd)» в моем коде для каждого узла. И я не могу добавить `hd` в качестве члена класса Node, поэтому я должен поместить его в саму эту функцию, и я не могу понять, как это сделать.(`hdl` и `hdr`)
Пожалуйста, помогите и внесите некоторые исправления в код.
Заранее благодарю.

В вашем коде есть две проблемы. Во-первых, вы сохраняете только значения узлов в очереди вместо указателей узлов. Итак, ваше условие обхода

 if(root->left)
  

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

 m[hd] = node_val
  

Поскольку это перезаписывается для каждого hd, это даст вам вид снизу. Мы хотим, чтобы здесь было первое вхождение для каждого hd. Я обновил код.

 void topView(Node * root) {
        queue<pair<Node*, int>> q;
        map<int, int> m;
        q.push({root->data, 0});
        while(q.empty() == false){
            Node* current_node = q.front().first;
            int node_val = current_node->data;
            int hd = q.front().second;

            if(m.find(hd) == m.end())
                m[hd] =node_val;

            q.pop();
            if(current_node->left){
                int hdl = hd -1;
                q.push({current_node->left, hdl});
            }
            if(current_node->right){
                int hdr = hd   1;
                q.push({current_node->right, hdr});

            }


        }
        for(auto i=m.begin();i!=m.end();i  ) 
        { 
            cout<<i->second<<" "; 
        } 
    }