Понимание указателей в двоичном дереве

Question

Я новичок в C++, и я обычно использую Java, поэтому мне сложно найти указатели и ссылки. Я должен сделать вариацию двоичного дерева поиска с внутренними узлами и листовыми узлами (только листья содержат данные).

class Node 
    Node *parent; 
    Node *left; 
    Node *right; 
    //other stuff 
} 

Мне нужно реализовать operator<<, который добавляет новый узел со значением к дереву.

//adding a node to tree 
void operator<<(int value){ 
    if(size == 0){ 
     //stuff 
    } else { 
     Node* temp = root; 
     getLeaf(temp,value); 
     //other magic   
     //temp will be used to append a new node into tree, 
     //so it has to point to the actual node in the tree 
     delete temp; 
    }   
} 

Точка функции getLeaf, чтобы найти лист (может или не может содержать нужный value) и хранить его в temp, который должен быть доступен в функции operator<<.

int getLeaf(Node* temp, int value) const{ 
    int depth = 0; 
    //goes trough all inner nodes until it finds specific leaf 
    while(temp->isInner()){ 
     ++depth; 
     if(value < temp->getValue()){ //searched value is smaller 
      temp = temp->getLeft(); // to left subtree 
      continue; 
     } else { 
      temp = temp->getRight(); //to rightsubtree 
      continue; 
     } 
    return depth; 
} 

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

Node* temp = root; 
    getLeaf(temp,value); 

не корневая получить переопределены при обходе дерева в getLeaf функции?

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

Не могли бы вы объяснить?

Answer 1

Миграция с Java на C++ немного жесткая. Миграция с C++ на Java одинаково жесткая. Чтобы облегчить вам жизнь, вам просто нужно поэкспериментировать.

В C++ указатели представляют собой переменные, указывающие на расположение другой переменной в памяти, а ссылки - это указатели, которые синтаксически ведут себя как переменная, на адрес которой указан.

Когда аргументы передаются функции, функция NOT принимает исходные аргументы, но их копия. Выполненная вами работа реализует обход, основанный на вышеупомянутых концепциях. Так как же все это "Волшебно" работы?

Ваша функция: getLeaf(Node *&temp, int value) выполняет поиск правильного листового узла и назначает его temp, на котором должна выполняться вставка. temp здесь копия ссылки на указатель temp (в operator <<). Поэтому, когда ссылку temp присвоено в getLeaf, указатель temp в operator <<, который он указывает, модифицируется.

Если установить

Node *temp = root; 
getLeaf(temp,value);

не корневая получить перекрываться при обходе дерева в функции getLeaf?

Здесь следует отметить, что temp и root два различных указателей, которые указывают на ту же переменную. Содержание указателей одно и то же, они не являются и, следовательно, root NOT переопределяется, когда temp обновляется.

Однако в коде есть проблема.Если вы delete temp;, root также будут удалены в конце ввода, так как delete удаляет содержимое, на которое указывает указатель. Do NOTdelete указатель, который не выделяется new.

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