Как создать функцию вставки в BST без указания root в качестве параметра

Question

Мне дали задание создать метод класса Binary Search Tree для вставки элементов в нужное место в дереве. Объявление этой функции:

void BST::insert(int k)
{   

}

Может кто-нибудь объяснить, почему узел root не задан в качестве параметра? Как я могу пройти по дереву, когда у меня нет его узла root? Наличие возвращаемого типа void намекает на использование ключевого слова "this"

. Я попытался реализовать следующее:

void BST::insert(int k)    {
   while(this->root != NULL) {
        if(k < this->root->value) {
            this->root = this->root->leftChild;
        } else {
            this->root = this->root->rightChild;
        }
   }
    this->root = new node(k); 
    }

Это дополнительный OOP код:

struct node {
  int value;
  node* parent;
  node* leftChild;
  node* rightChild;

  node (int);
  int dessiner(ofstream&, int);
};

class BST {
  public:
    node* root;
    BST();
    void dessiner(string);
    void swap(node*, node*);
    void inserer(int);
};

РЕДАКТИРОВАТЬ: я добавил 2 указателя. tmp для обхода дерева и P для отслеживания родительского узла tmp

node* tmp = this->root;
    node* p = NULL;
    while(tmp!=NULL) { 
        p = tmp;
        if(k < tmp->value) {
            tmp = tmp->leftChild;
        } else {
            tmp = tmp->rightChild;
        }

    }

    tmp = new node(k);
    tmp->parent = p;

Answer 1

Может кто-нибудь объяснить, почему узел root не задан в качестве параметра?

Это так. BST::insert неявно имеет параметр BST * с именем this. Оттуда вы можете получить на root. Обратите внимание, что вам не нужно this-> для ссылки на root, это подразумевается в теле функции-члена.

Наличие возвращаемого типа void намекает мне на использование «this» Ключевое слово

Тип возвращаемого значения не имеет к этому никакого отношения.

Обратите внимание, что вам нужно будет присвоить новый узел p leftChild или rightChild, после того как insert завершится, на него ничего не указывает.

Answer 2

При работе с BST я обычно пишу функцию publi c, подобную той, что у вас есть, которая вызывает приватную рекурсивную функцию с root дерева. У вас нет доступа к root дерева извне класса, поэтому для функции publi c не имеет смысла принимать что-либо большее, чем элемент для вставки.

void BST::insert(int k)
{   
  insert(k, root);
}

void BST::insert(int k, node* curr)
{   
  // logic to insert the new element
  ...
}

Вы можете объединить эти функции с параметром по умолчанию, чтобы из-за пределов класса вы могли вызывать bst.insert(5) и curr начинались как root дерева.

void BST::insert(int k, node* curr = root)
{   
  // logic to insert the new element
  ...
}