이진 탐색 트리에서 상위 노드를 이해하는 데 도움이 필요합니다.

Question

아래 코드는 노드를 트리의 올바른 위치에 삽입하는 함수입니다. 내가 이해하지 못하는 것은 부모 노드가 실제로 나타내는 것입니다. 그것이 root -> left -> parent = root -> left이라고 할 때, 그것은 무엇을 의미합니까? 그게 뿌리의 왼쪽 부모의 설정 자체가 아닌가요? 루트의 왼쪽 자식 부모가 루트가되고 왼쪽 자식 자체가 아니기 때문에 root -> left -> parent = root이 아니어야합니까? 부모 노드를 명확하게 설명해 주시겠습니까? 고맙습니다.

Node * insert(Node *root, int item) { 
    if (root == NULL) 
    return newNode(item); 

    if (item <= root -> info) 
    if (root -> left == NULL) { 
     root -> left = newNode(item); 
     root -> left -> parent = root -> left;  //**line of interest** 
    } 
    else 
     insert(root -> left, item); 
    else 
    if (root -> right == NULL) { 
     root -> right = newNode(item); 
     root -> right -> parent = root -> right; 
    } 
    else 
     insert(root -> right, item); 
    return root; 
} 

Answer 1

귀하의 설명에 따르면 난

class node{ 
    int info; 
    node *left; 
    node *right; 
    node *parent; 
}; 

지금 BST에 부모가 NULL이됩니다있는 루트 노드가있을 것입니다, 노드 클래스가있을 것이라 생각합니다. 첫 번째 값을 삽입한다고 가정하십시오 (5로 지정하십시오)
이제 루트는 5를가집니다. root->left이 null이고 root->right이 null입니다.

2를 삽입하면 2가 루트의 왼쪽에있게됩니다.

그래서 root-> left는 2가됩니다. root->left은 값이 아닌 노드를 의미하므로 간단하게 할 수 있습니다. 따라서 root->left->info = 2;. 이제 할 일이 하나 더 있습니다. root->left 값을 설정합니다. 이제 root->left의 부모는 무엇입니까? 그 것 루트, 이제 다른 데이터를 삽입하는 경우 그래서 root->left->parent = root;

는 (은 1하자)

root->left->left->info = 1; 
root->left->left->parent = root->left; 

그래서 코드를 BST에 노드를 삽입하는 일을 간단하지 않았다. 내가 뭘 할 것은

,

Node n = new node(); 
n = newNode(item); //as you wrote 
n->parent = root->left.