C++에서 이진 탐색 트리에 노드 삽입

Question

이진 탐색 트리를 작성한 다음 가장 왼쪽 노드를 표시된 첫 노드로 사용하여 수평 inorder 인쇄를 시도하고 있습니다. 또한 각 노드 앞에는 트리 자체를 시각화하는 데 도움이되는 틸드뿐만 아니라 깊이 (루트와의 거리)가 있습니다. 개념적으로 내 코드는 정확하지만 어떤 이유로 든 트리를 제대로 만들 수없는 것 같습니다. 오류가 내 삽입 함수에서 발생할 가능성이 높지만 위치를 찾을 수없는 것으로 나타났습니다.

어떤 제안이나 아이디어라도 도움이 될 것입니다. 다음

#include <iostream> 
#include <cstdlib> 
#include <fstream> 
#include <iomanip> 
#include <algorithm> 
using namespace std; 

typedef struct treeNode { 

    treeNode *leftChild; 
    treeNode *rightChild; 
    int data; 
} treeNode; 


void printTree(treeNode*); 
int getNodeDepth(treeNode*); 
treeNode* insert(treeNode*, int); 
treeNode* createNewNode(int); 

int main() 
{ 


    //read in file here 



    treeNode *root = NULL; 

    root = insert(root, 8); 
    root = insert(root, 1); 
    root = insert(root, 90); 
    root = insert(root, 3); 
    root = insert(root, 80); 
    root = insert(root, 6); 
    root = insert(root, 83); 

    printTree(root); 

    return 0; 
} 


/* 
Purpose: Constructs a new node for the tree. 
Inputs: The data for the node. 
Outputs: returns the new node 
*/ 
treeNode* createNewNode(int data) 
{ 
    treeNode *newNode = new treeNode; 
    newNode->data = data; 
    newNode->leftChild = NULL; 
    newNode->rightChild = NULL; 
    return newNode; 
} 

/* 
Purpose: Calculates the depth of a given node using recursion. 
Inputs: The node to check the depth on. 
Outputs: returns the depth 
*/ 
int getNodeDepth(treeNode *node) 
{ 
    if (node == NULL) // tree doesn't exist 
     return(0); 

    return(1 + max(getNodeDepth(node->leftChild), getNodeDepth(node->rightChild))); 
} 


/* 
Purpose: Inserts a node into the tree. 
Inputs: The node to be inserted and the data for the node. 
Outputs: returns the inserted node 
*/ 
treeNode* insert(treeNode *node, int data) 
{ 
    if (node == NULL) 
     return createNewNode(data); 
    else 
    { 
     if (data <= node->data) 
     { 
      node->leftChild = insert(node->leftChild, data); 
     } 
     else 
     { 
      node->rightChild = insert(node->rightChild, data); 
     } 
     return node; 
    } 
} 


/* 
Purpose: Prints the BST in a horizontal inorder format. 
Inputs: The root node. 
Outputs: nothing 
*/ 
void printTree(treeNode *node) 
{ 
    if (node == NULL) 
     return; 
    printTree(node->leftChild); 
    cout << "(" << (getNodeDepth(node)-1) << ") "; 
    for (int i=0; i<(getNodeDepth(node)-1); i++) 
     cout << "~"; 
    cout << node->data << endl; 
    printTree(node->rightChild); 
} 

전류 출력은 :

가

(2) ~~1 
(1) ~3 
(0) 6 
(3) ~~~8 
(1) ~80 
(0) 83 
(2) ~~90 

물론이 두 루트 (즉, 6, 83)를 가질 수 없다. 감사! 처음에

Answer 1

내 원래 질문에 대한 답변의 올바른 구현을 원하는 사람들은 앞으로 리팩토링 된 코드를 사용합니다. OOP 접근 방식을 채택하고 insert 및 getNodeDepth 함수를 수정하여 적절하게 작동하게했습니다. 다음과 같이

// 
// Binary Search Tree 
// 

#include <iostream> 
#include <cstdlib> 
#include <fstream> 
#include <iomanip> 
#include <algorithm> 
using namespace std; 

// binary search tree 
class BST { 

private: 
    typedef struct treeNode { 
     treeNode *leftChild; 
     treeNode *rightChild; 
     int data; 
    } treeNode; 

    treeNode *root; 

public: 
    //Constructor 
    BST() { root = NULL; } 

    /* 
    Purpose: Constructs a new node for the tree. 
    Inputs: The data for the node. 
    Outputs: returns the new node 
    */ 
    treeNode* createNewNode(int data) 
    { 
     treeNode *newNode = new treeNode; 
     newNode->data = data; 
     newNode->leftChild = NULL; 
     newNode->rightChild = NULL; 
     return newNode; 
    } 

    //Check if the tree is empty 
    bool isEmpty() const { return root==NULL; } 

    /* 
    Purpose: Calculates the depth of a given node using recursion. 
    Inputs: The node to check the depth on and the node to check the depth from. 
    Outputs: returns the depth 
    */ 
    int getNodeDepth(treeNode *node, treeNode *from) 
    { 
     if (node == from) 
      return 0; 
     else if (node->data < from->data) 
      return getNodeDepth(node, from->leftChild) + 1; 
     else 
      return getNodeDepth(node, from->rightChild) + 1; 
    } 


    /* 
    Purpose: Inserts a node into the tree. 
    Inputs: The data for the node. 
    Outputs: none 
    */ 
    void insert(int newData) 
    { 
     treeNode* t = createNewNode(newData); 
     treeNode* parent; 
     parent = NULL; 


     if(isEmpty()) //check if tree exists or not 
      root = t; 
     else { 
      //Note: ALL insertions are as leaf nodes 
      treeNode* curr; 
      curr = root; 
      // Find the Node's parent 
      while(curr) 
      { 
       parent = curr; 
       if (t->data > curr->data) 
        curr = curr->rightChild; 
       else 
        curr = curr->leftChild; 
      } 

      if ((t->data) < (parent->data)) 
       parent->leftChild = t; 
      else 
       parent->rightChild = t; 
     } 

    } 


    /* 
    Purpose: Prints the BST in a horizontal inorder format. 
    Inputs: The root node. 
    Outputs: nothing 
    */ 
    void printTree(treeNode *node) 
    { 
     if (node == NULL) 
      return; 
     printTree(node->leftChild); 
     cout << "(" << getNodeDepth(node, root) << ") "; 
     for (int i=0; i<getNodeDepth(node, root); i++) 
      cout << "~"; 
     cout << node->data << endl; 
     printTree(node->rightChild); 
    } 

    //Getter for private member variable root 
    void printInorder() 
    { 
     printTree(root); 
    } 

}; 

int main() 
{ 
    // read file in here 

    BST temp; 

    temp.insert(8); 
    temp.insert(1); 
    temp.insert(90); 
    temp.insert(3); 
    temp.insert(80); 
    temp.insert(6); 
    temp.insert(83); 

    temp.printInorder(); 

    return 0; 
} 

올바른 출력은 루트로 8 같습니다

(1) ~1 
(2) ~~3 
(3) ~~~6 
(0) 8 
(2) ~~80 
(3) ~~~83 
(1) ~90 

희망이 도움이!

Answer 2

당신이 메모리 누수를 만드는 두 번째에서 두 번

typedef struct { 
    treeNode *leftChild; 
    treeNode *rightChild; 
    int data; 
} treeNode; 

을 treeNode를 작성하지해야합니다

treeNode *root = new treeNode; 
root = NULL; 

당신은 작성해야 :

treeNode *root = NULL; 

분명히 두 개의 뿌리를 가질 수는 없습니다 (즉, 6과 83). 감사!

6 및 83은 뿌리가 아닙니다. 8은 루트입니다. 그래서 당신의 프로그램은 정답을주었습니다.