Inorder tree traversal in C 이진 트리에서

Question

아래 코드에서는 삽입 함수를 사용하여 이진 트리를 만들고 Inorder traversal의 논리를 따르는 inorder 함수를 사용하여 삽입 된 요소를 표시하려고합니다. 숫자가 삽입되고 있지만 inorder 함수 (입력 3)를 시도하면 프로그램은 아무 것도 표시하지 않고 다음 입력을 계속합니다. 논리적 인 오류가있을 수 있습니다. 정리해주십시오. 사전에 감사합니다 ...

#include<stdio.h> 
#include<stdlib.h> 

int i; 
typedef struct ll 
{ 
    int data; 
    struct ll *left; 
    struct ll *right; 
} node; 

node *root1=NULL; // the root node 

void insert(node *root,int n) 
{ 
    if(root==NULL) //for the first(root) node 
    { 
    root=(node *)malloc(sizeof(node)); 
    root->data=n; 
    root->right=NULL; 
    root->left=NULL; 
    } 
    else 
    { 
    if(n<(root->data)) 
    { 
     root->left=(node *)malloc(sizeof(node)); 
     insert(root->left,n); 
    } 
    else if(n>(root->data)) 
    { 
     root->right=(node *)malloc(sizeof(node)); 
     insert(root->right,n); 
    } 
    else 
    { 
     root->data=n; 
    } 
    } 
} 

void inorder(node *root) 
{ 
    if(root!=NULL) 
    { 
    inorder(root->left); 
    printf("%d ",root->data); 
    inorder(root->right); 
    } 
} 

main() 
{ 
    int n,choice=1; 
    while(choice!=0) 
    { 
    printf("Enter choice--- 1 for insert, 3 for inorder and 0 for exit\n"); 
    scanf("%d",&choice); 
    switch(choice) 
    { 
     case 1: 
     printf("Enter number to be inserted\n"); 
     scanf("%d",&n); 
     insert(root1,n); 
     break; 
     case 3: 
     inorder(root1); 
     break; 
     default: 
     break; 
    } 
    } 
} 

Answer 1

귀하의 insert은 함수의 범위에 대해 로컬 인 node에 대한 포인터를 받아들입니다. insert이 반환 된 후에 호출 된 루트는 변경되지 않습니다. 그리고 누수가 생겼어.

당신이 밖에서 볼 수 있도록하지 insert 변경을 원하는 경우에, 그 서명

void insert(node **root,int n) 

을 변경 그래서처럼 호출하여 시작합니다

void insert(&root1, n); 

그 방법을, 그것은 root1을 수정합니다 사본이 아닙니다.

일반적으로 함수가 무언가를 수정해야하는 경우 포인터를 포인터로 전달해야합니다. 함수는 node*을 수정해야하므로 node**을 전달해야합니다. 언 와인드는 지적

편집하는 것은

, 당신은 또한 당신이 하나의 개체를 수정해야하는 경우가

root1 = insert(root1, n); 

이것은 물론에만 작동 갱신하는 수단으로 루트를 반환 할 수 있습니다.

Answer 2

할당 코드가 off 인 경우 root1은 malloc 결과가 로컬 변수에만 할당되므로 NULL으로 유지됩니다. 루트 포인터를 포인터에 대한 포인터로 전달하십시오.

또한 malloc을 무조건 malloc하고 데이터를 이미 가지고있을지라도 insert를 즉시 호출하고 호출 된 insert가 root와 마찬가지로 malloc을 처리하도록해야합니다. 다시 포인터 포인터를 사용하십시오.

마지막으로 else root->data = n은 이해가되지 않습니다. 이미 n입니다. 그리고 당신은 당신의 나무에 중복을 원하지 않는다고 생각합니까? 필요한 경우 코드를 변경해야합니다.

Answer 3

node *을 insert()으로 전달하면 새 노드가 할당되면 해당 노드가 적절하게 업데이트됩니다.

또한 함수에서 아래 트리로 이동하는 동안 할당하지 마십시오. 할당하면 코드가 해당 노드의 값을 확인하고 다시 시도합니다. 이는 올바르지 않습니다.

업데이트 된 코드는 다음과 같습니다 main()에서

void insert(node **root_ptr,int n) 
    { 
    if(root==NULL) //for the first(root) node 
    { 
     root=(node *)malloc(sizeof(node)); 
     root->data=n; 
     root->right=NULL; 
     root->left=NULL; 
     *root_ptr = root; 
    } 
    else 
    { 
     if(n<(root->data)) 
     { 
     //root->left=(node *)malloc(sizeof(node)); 
     insert(&root->left,n); 
     } 
     else if(n>(root->data)) 
     { 
     //root->right=(node *)malloc(sizeof(node)); 
     insert(&root->right,n); 
     } 
     else 
     { 
     root->data=n; 
     } 
    } 
    } 

이 insert(&root1,n);