C++ Как назначить указатель на родительский элемент в двоичном дереве

Question

Я запутался в том, как вы инициализируете m_parent, чтобы указать на узел над дочерним элементом.

class Node 
{ 
public: 
    Node(string city); 
    ~Node(); 
    string m_city; 
    int m_parent_distance; 
    Node *m_left; 
    Node *m_right; 
    Node *m_parent; 
}; 
Node *m_root; 
//void test_print(string target, Node *cur_root); 
Node * find_node(Node *m_root, string target); 

это конструктор узла

Stree::Node::Node(string city) 
{ 
    m_city = city; 
    m_left = NULL; 
    m_right = NULL; 
    //what do i do with m_parent?? 
    m_parent_distance = 0; 
} 

Answer 1

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

class Node 
{ 
public: 
    Node(string city, Node *parent); 
    ~Node(); 
    string m_city; 
    int m_parent_distance; 
    Node *m_left; 
    Node *m_right; 
    Node *m_parent; 
}; 

Stree::Node::Node(string city, Node *parent) 
    : m_city(city), 
     m_left(NULL), 
     m_right(NULL), 
     m_parent(parent), 
     m_parent_distance(0) 
{ 
} 

Кстати, вы должны использовать список инициализации (как я писал выше), а не присвоения в конструкторе (как код, который вы нам показали).

Answer 2

Наиболее естественный способ может быть, чтобы добавить метод AddChild(Node * child, bool left) и называют, что на родителей. Это необходимо будет:

• m_parent у ребенка.
• m_left или m_right в исходном.

Альтернативой может быть добавление parent и left параметр для детского конструктора и делать эти операции там.

Answer 3

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

Это изобретает колесо, однако. Если это не касается школьного задания, которое запрещает использование стандартной библиотеки, вероятно, вы должны использовать std::map или std::set.