바이너리 트리 구현 C++

Question

저는 재미있게 C++로 이진 검색 트리를 구현하려고했습니다. 내 문제는 내가 삽입 기능에 문제가 있다는 것입니다. 아래는 내가 지금까지 가지고있는 것이다 :

class TreeNode{ 

public: 
    int data;   
    TreeNode *left;  
    TreeNode *right; 
    void Insert(int value, TreeNode *x); 
    void TreeNode::Print(TreeNode *x); 
    TreeNode(); 
}; 


TreeNode::TreeNode(){ 

left = NULL; 
right = NULL; 

} 

.

void TreeNode::Insert(int value, TreeNode *x){ 

    if(x->left == NULL && x->right == NULL){ 
      TreeNode *tree = new TreeNode();       
      tree->datavalue;        
      x->left = tree;         
    } 

    else if(x->left == NULL && x->right != NULL){ 

      TreeNode *tree = new TreeNode();     
      tree->data = value;       
      x->left = tree;         
    } 

    else if(x->left != NULL && x->right == NULL){ 

      TreeNode *tree = new TreeNode();      
      tree->data = value;        
      x->right = tree;       
    } 

    else if(x->left != NULL && x->right != NULL){ 

     ?????? 

    } 

} 

Answer 1

맹목적으로 삽입해서는 안되며 아래 논리를 따르십시오. x.value가 루트 값보다 작 으면 왼쪽에 삽입하십시오. x.value가> = root.value이면 오른쪽으로 이동하십시오. NULL 값을 누를 때까지이 논리를 반복하십시오. 그것은 당신의 요소를 삽입하는 적절한 장소가 될 것입니다.

로직을 뒤집을 수 있습니다.에 왼쪽을 선택했습니다. 왼쪽보다 약간 작기 때문입니다. P

TreeNode *root = this; 
TreeNode *parent = root; 
//Traverse the tree, go left if x.val < , else go right(>=) 
while(root) { 
    parent = root; 
    root = (root->value > x.value) ? root->left : root->right; 
} 
if(parent->value > x->value) 
    parent->left = x; 
else 
    parent->right = x; 

당신이 큐와 깊이 우선 탐색을 수행 순서를 신경 쓰지 않는 경우 : - <.

queue<TreeNode*> nodes; 
nodes.push(this); 
while(1) 
{ 
    if(!nodes.front()->left) 
    { 
     nodes.front()->left = x; 
     return; 
    } 
    else if (!nodes.front()->right) 
    { 
     nodes.front()->right = x; 
     return; 
    } 
    nodes.push(nodes.front()->left); 
    nodes.push(nodes.front()->right); 
    nodes.pop(); 
} 

Answer 2

왼쪽 및 오른쪽 자식이 모두 null이 아닌 경우 삽입하려는 경우 트리의 맨 왼쪽 노드로 재귀 적으로 이동하여 항목을 삽입 할 수 있습니다. 그리고 특별한 순서없이 값을 삽입하기 만하면 추적하기가 어려울 것입니다. 그 경우 이진 검색 트리를 구현하십시오.

else if(x->left != NULL && x->right != NULL){ 
     Insert(value,x->left); 
     x-> data = value; 
     x->left = x->right = NULL; 
} 

가장 중요한 것은 BASE 케이스를 삽입하여 재귀를 종료하는 것입니다.