C++ 이진 검색 트리 삽입 구현

Question

이진 검색 트리에 삽입 할 함수를 작성하려고하지만 작동하지 않는 이유를 파악하는 데 어려움을 겪고 있습니다. 함수가 어떻게 작동해야하는지는 근본적으로 이해하지만 템플릿을 기반으로 BST 클래스를 만드는 것을 피하는 대신 Node 클래스에 의존하고이를 수행 할 원하는 함수를 빌드하는 것처럼 보입니다. 여기에 주어진 템플릿입니다 :

#include <iostream> 
#include <cstddef> 

using std::cout; 
using std::endl; 

class Node { 
    int value; 
public: 
    Node* left;  // left child 
    Node* right;  // right child 
    Node* p;   // parent 
    Node(int data) { 
     value = data; 
     left = NULL; 
     right = NULL; 
     p = NULL; 
    } 
    ~Node() { 
    } 
    int d() { 
     return value; 
    } 
    void print() { 
     std::cout << value << std::endl; 
    } 
}; 

function insert(Node *insert_node, Node *tree_root){ 
    //Your code here 
} 

내가 getValue 간단한 게터 노드에 대한 방법 다음 코드를 구현할 때 데 문제 :

int main(int argc, const char * argv[]) { 
    Node* root = NULL; 
    Node* a = new Node(2); 
    insert(a, root); 
} 

void insert(Node *insert_node, Node *tree_root){ 
    if (tree_root == NULL)  
     tree_root = new Node(insert_node->getValue()); 

코드는 컴파일 나타나고 실행 오류없이,하지만이 후 루트에 대한 다른 검사를 실행하면 NULL을 반환합니다. 내가 여기서 무엇을 놓치고 있는지 아는 어떤 생각? 루트를 insert_node와 같은 새 노드로 바꾸지 않는 이유는 무엇입니까?

나는 이것이 BST를 구현하는 최적의 방법으로 보이지 않는다는 것을 알고 있지만, 나에게 주어진 템플릿으로 작업하려고합니다. 어떤 조언을 주시면 감사하겠습니다.

Answer 1

요아킴은 귀하의 문제는 참조를 기준으로 매개 변수를 전달하는 것과 가치에 따라 매개 변수를 전달하는 것과 관련이 있다고 말했습니다.

코드 void insert(Node *insert_node, Node *tree_root)에는 Node* tree_root을 값으로 전달합니다. 함수 내에서이 포인터의 로컬 복사본을 변경하므로 바깥 쪽 값이 변경되지 않습니다.

수정하려면 Node* tree_root을 reference으로 전달해야합니다. 매개 변수 선언은 Node*& tree_root (또는 Node** tree_root)이 될 수 있습니다. 예 :

void insert(Node* insert_node, Node*& tree_root){ 
    if (tree_root == NULL)  
     tree_root = new Node(insert_node->getValue());