이진 검색 트리 노드 구조가없는 재귀

Question

대학을 위해 프로젝트를 완료해야하지만 어떻게 할 수 있는지 알 수 없습니다.

문제는 다음과 같은 주어진 기능을 가진 이진 검색 트리 응용 프로그램을 만들고 싶다는 것입니다. 어떤 종류의 재귀를 빌드해야하지만 내 문제는 bst_insert (tree * bst, int key) 함수가 트리을 입력으로 사용하고 노드를 사용하지 않는다는 것입니다. 그래서 아래에 작성한 아이디어 (bst_insert (bst-> root_node-> left, key);)가 작동하지 않습니다.

누군가가 내가 해결할 솔루션을 얻기 위해 무엇을 할 수 있는지 알고 있습니까?

감사합니다. 여기

는 bst->root_node->left을 통과, 여기

typedef struct node { 
     int key; 
     struct node *left; 
     struct node *right; 
    } node; 

    typedef struct tree { 
     node *root_node; 
     int (*compare_keys)(int x, int y); 
    } tree; 

    void bst_insert(tree *bst, int key); 

당신이 허용 된 경우에도 tree.c 파일

void init(tree *bst) { 
    bst->root_node = 0; 
    bst->compare_keys = 0; 
} 

void bst_insert(tree *bst, int key) {  
    if (bst->root_node == NULL) { 
    bst->root_node = (node*)malloc(sizeof(node)); 
    bst->root_node->key = key; 
    bst->root_node->left = NULL; 
    bst->root_node->right = NULL; 
    } 
    else { 
    if (key < bst->root_node->key) { 
     bst_insert(bst->root_node->left, key); 
    } 
    if (key > bst->root_node->key) { 
     bst_insert(bst->root_node->right, key); 
    } 
    } 
} 

Answer 1

의 일부입니다 내 헤더 파일의 일부 (tree.h)입니다 직접 작동하지 않습니다. 함수 인수는 값에 의해 전달되며 재귀 호출은 bst->root_node->left (NULL 인 경우) 값을 변경해야 할 수 있습니다. 당신이 함수 f 변수 x을 변경할 수 있도록하려면

는 가장 쉬운 해결책은 f 포인터를 가지고 (x의 주소를 전달) f(&x)로 전화하는 것입니다. 재귀 삽입 함수에 적용 할 수 있습니다.

void bst_insert(node **ppnode, int key) {  
    if (*ppnode == NULL) { 
     *ppnode = malloc(sizeof **ppnode); 
     (*ppnode)->key = key; 
     (*ppnode)->left = NULL; 
     (*ppnode)->right = NULL; 
    } 
    else if (key < (*ppnode)->key) { 
     bst_insert(&(*ppnode)->left, key); 
    } 
    else if (key > (*ppnode)->key) { 
     bst_insert(&(*ppnode)->right, key); 
    } 
} 

이 코드는 작동하지만 잘못된 유형이 있습니다.

그러나 큰 문제는 아닙니다.이 함수의 이름을 바꾸고 올바른 이름과 유형의 래퍼를 제공하기 만하면됩니다.

static void bst_node_insert(node **ppnode, int key) {  
    if (*ppnode == NULL) { 
     *ppnode = malloc(sizeof **ppnode); 
     (*ppnode)->key = key; 
     (*ppnode)->left = NULL; 
     (*ppnode)->right = NULL; 
    } 
    else if (key < (*ppnode)->key) { 
     bst_node_insert(&(*ppnode)->left, key); 
    } 
    else if (key > (*ppnode)->key) { 
     bst_node_insert(&(*ppnode)->right, key); 
    } 
} 

void bst_insert(tree *bst, int key) { 
    bst_node_insert(&bst->root_node, key); 
} 

이 코드의 구조는 데이터 유형의 구조를 반영 : 당신은 tree 자체에 대한 포인터를 포함하는 node에 대한 포인터를 포함합니다. 마찬가지로 트리 삽입 함수 bst_insert에는 노드 삽입 함수 bst_node_insert에 대한 호출이 포함되어 있습니다.이 함수에는 자체 호출이 포함되어 있습니다.

Answer 2

bst_insert의 정의를 변경할 수 없다고 했으므로 해결 방법은 함수를 호출하기 전에 새 임시 트리를 만드는 것입니다. 그것은 조금 이상한 느낌이 있지만, 코드 같은 아래 작동합니다 : 당신이 생각하는 것을 확신

if (key < bst->root_node->key) { 

: 또한

tree tempTree; 
... 
if (key < bst->root_node->key) { 
    if (bst->root_node->left == NULL) 
    { 
     // Add a new node 
     bst->root_node->left = malloc(sizeof(node)); 
     bst->root_node->left->key = key; 
     bst->root_node->left->left = NULL; 
     bst->root_node->left->right = NULL; 
     return; 
    } 

    // Make a temporary tree for a recursive call 
    tempTree.root_node = bst->root_node->left; 
    tempTree.compare_keys = bst->compare_keys; 
    bst_insert(&tempTree, key); 
    return; 
} 

, 당신이이 줄 뭔가 잘못하고 있다고 생각 compare_keys 기능을 사용하십시오. 어쩌면 :

if (compare_keys(key, bst->root_node->key) < 0) {