트리 프로그램의 오류는 어디에 있습니까?

Question

다음은 VS2008에서 작성한 두 가지 샘플 코드입니다. 첫 번째 샘플 코드는 잘 작동하지만 두 번째 (트리의) 코드는 오류가 발생합니다.

1) 
#include<iostream> 
using namespace std; 

struct node{ 
     int number; 
     struct node *right; 
     struct node *left; 
    }nodeType; 

int insert(struct node *,int); 

int main(){ 

     struct node * root=(struct node *)malloc(sizeof(node)); 
     root->left=NULL; 
     root->right=NULL; 
     root->number=10; 
     insert(root,100); 
     cout<<root->right->number; //This works fine 

     return 1; 
    } 

int insert(struct node * leaf,int data){ 
     leaf->left =(struct node *)malloc(sizeof(node)); 
     leaf->right =(struct node *)malloc(sizeof(node)); 
     struct node *temp = leaf; 
     temp->right->number=12; 
     temp->left->number=11; 
     temp->right->right=NULL; 
     temp->right->left=NULL; 
     temp->left->left=NULL; 
     temp->left->right=NULL; 
     return 1; 
    } 





    2) 

#include<iostream> 
using namespace std; 
struct node{ 
    int number; 
    struct node *right; 
    struct node *left; 
}nodeType; 

int insert(struct node *,int); 

int main(){ 

    int data[50]; 
    int i; 
    for(i=0;i<50;i++){ 
    data[i]=rand()%100; 
    } 

    struct node * root=(struct node *)malloc(sizeof(node)); 
    root->left=NULL; 
    root->right=NULL; 

    root->number = 36; 
    for(i=0;i<50;i++){ 
     insert(root,data[i]); 
    } 
    cout<<root->right->number; //This doesn't work, and it throws some memory error. Though it assigns a value(it is 41) which goes to the right side in the insert function, the root's right side pointer is not able to point into that memory location. Similar case with root->.... also. 
    return 1; 
} 

int insert(struct node * leaf,int data){ 

    if(leaf==NULL){ 
     leaf = (struct node *)malloc(sizeof(node)); 
     leaf->number=data; 
     leaf->left=NULL; 
     leaf->right=NULL; 
    } 
    else if(data>=leaf->number){ 
     insert(leaf->right,data); 
    } 
    else if (data<leaf->number){ 
     insert(leaf->left,data); 
    } 
    else 
    { 

    } 

    return 1; 
} 

왜 두 번째 프로그램에서 해당 위치를 가리킬 수 없습니까?

편집 : 내가 런타임 중에있어 오류가이었다가 0xc0000005 : TEST.EXE에서 0x004114b4에서

처리되지 않은 예외 액세스 vioation 위치를 읽는 0x000000004.

중단 계속 무시

Answer 1

@whozcraig는 자신을 제한하는 올바른 남자 다운 작업을 수행했습니다. 나는 자제심이 적기 때문에, 아직 눈치 채지 못했던 (또는 심지어 증상을 보았던) 코드의 문제에 관해 이야기 할 것이다.

먼저, C++ 코드에서 malloc을 사용하지 말아야하며, 구조체의 인스턴스를 정의하는 데는 struct xxx을 사용하지 않아야합니다.

둘째, 당신은 정말 node의 ctor에 의해 처리되어야 일을하고 있어요 main 및 insert 모두 코드가 (예를 들어, NULL에 노드의 자식 포인터를 설정).

세 번째로 insert에서 절대 거짓이 될 수없는 조건을 테스트 한 다음 실행될 수없는 빈 else을 추가합니다 (아무튼 작동하지 않음).

나는이 같은 것을보고 node를 다시 작성하여 시작 했죠 :

struct node{ 
    int number; 
    node *right; 
    node *left; 

    node(int n) : number(n), right(NULL), left(NULL) {} 
}; 

이 방법은 노드의 ctor에 NULL로 자식 포인터를 초기화하고, 노드 자체에 원하는 값을 넣습니다.

이렇게하면 다른 코드를 크게 단순화 할 수 있습니다.

void insert(node *&leaf, int data){ 
    if (leaf == NULL) 
     leaf = new node(data); 
    else if (data < leaf->number) 
     insert(leaf->left, data); 
    else 
     insert(leaf->right, data); 
} 

이 이진 트리 정말 단지 세 가지 가능성이있다, 때문에 : -이 경우, 우리는 새로운 데이터를 삽입 1)에는 "현재"노드가 없다 예를 들어, insert은 다음과 같이 찾고 끝 "여기"또는 2) 새 데이터가 현재 노드의 왼쪽에 속하거나 3) 현재 노드의 오른쪽에 속합니다. 이 코드는 3 자 결정 프로세스를 직접 반영합니다.

main의 코드 중 일부는 불필요한 것으로 보입니다. 우리가 나무에 몇 가지 숫자를 삽입 할 경우 예를 들어, 이런 식으로 뭔가에 아래 코드를 단순화하기 쉽습니다 :

node *root = NULL; 

for (int i = 0; i < 50; i++) 
    insert(root, rand() % 100); 

먼저 배열에 데이터를 입력 할 필요가 없습니다 - 우리는 넣을 수 있습니다 각 항목은 생성 될 때 트리에 직접 표시됩니다.

물론, 무슨 일이 일어나고 있는지 알기 위해서 우리는 아마 트리의 특정 노드뿐만 아니라 모든 데이터를 인쇄하고 싶을 것입니다. 다행히도, 그 역시 할 매우 쉽습니다 :

void show(node *tree) { 
    if (tree == NULL) 
     return; 
    show(tree->left); 
    std::cout << "\t" << tree->number; 
    show(tree->right); 
} 

이이 횡단있어 각 노드를 인쇄, 나무의 간단한에서 주문 탐색을 수행합니다. 트리에 대해 작성한 메모리 누출을 방지하려면 트리에서 노드를 삭제하는 것과 비슷한 작업을 수행하는 것이 좋습니다. 가장 큰 차이점은 post-order traversal (재귀 적으로 두 자식을 삭제 한 다음 현재 노드를 삭제)을 수행하려는 것입니다.

또 다른 점은 구성원 함수로 insert이라는 트리가 실제로 자체 클래스 여야한다는 것입니다 (그리고 위의 show과 같은 것을 원한다면 트리를 삭제하고 모든 내용을 삭제하는 dtor 일 수도 있습니다. 아마도 operator<<의 오버로드 등)

Answer 2

두 번째 삽입 함수는 노드 포인터 by-value를 전달합니다. 참조 또는 주소가 아닌 따라서 그 변경 사항은 기능 범위 밖에서 수행되지 않습니다.

변경이 : 여기에

int insert(struct node * leaf,int data) 

: 프로토 타입 및 구현 모두에서

int insert(struct node*& leaf,int data) 

.

C++ 프로그램에서 malloc()의 사용에 대한 모든 의견을 유보합니다. 그것이 나쁘지 않은 것처럼, 그것은 당신의 문제와 관련이 없습니다.