番号付きノードのバイナリ検索ツリーの印刷

Question

BSTのInOrderトラバーサルを行い、ノードを印刷したいとします。私はツリーをうまく印刷することができますが、番号付けを正しく行うことはできません。

誰かがコンパイルしてショットを付ける場合は、ここにすべてのコードがあります。ありがとうございました！

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



struct Node_h { 
    int start_addr; 
    int size; 

    struct Node_h* left; 
    struct Node_h* right; 
}; 

struct Node_h* newHoleNode(int st, int size) { 
    struct Node_h* tmp = (struct Node_h*)malloc(sizeof(struct Node_h)); 
    tmp->start_addr = st; 
    tmp->size = size; 
    tmp->left = NULL; 
    tmp->right = NULL; 
    return tmp; 
} 

int compare(struct Node_h* lhs, struct Node_h* rhs) { 
    if(lhs->size != rhs->size) 
     return (lhs->size < rhs->size) ? -1 : 1; 
    else if(lhs->start_addr == rhs->start_addr) 
     return 0; 
    else 
     return (lhs->start_addr < rhs->start_addr) ? -1 : 1; 
} 

struct Node_h* insertHole(struct Node_h* cur, struct Node_h* add) { 
    /* If the tree is empty, return a new node */ 
    if (cur == NULL) 
     return add; 

    /* Otherwise, recur down the tree */ 
    if (compare(add, cur) == -1) { 
     cur->left = insertHole(cur->left, add); 
    } 
    else if(compare(add, cur) == 1) { 
     cur->right = insertHole(cur->right, add); 
    } 

    /* return the (unchanged) node pointer */ 
    return cur; 
} 

int printHoles(struct Node_h* cur, int num) { 
    if(cur == NULL) { 
     return 0; 
    } 
    int t = 1 + num; 
    t += printHoles(cur->left, num); 
    printf("Hole %d: start location = %d, size = %d\n", t, cur->start_addr, cur->size); 
    t += printHoles(cur->right, t); 
    return t; 
} 

int main(int argc, char const *argv[]) { 
    srand(time(NULL)); // should only be called once 
    int pid = 0; 
    struct Node_h* root = NULL; 
    for (int i = 0; i < 1000; ++i) { 
     int size = rand() % 10000; 
     root = insertHole(root, newHoleNode(pid++, size)); 
    } 
    printHoles(root, 0); 
    return 0; 
} 

番号付けは、常に大量のランダム+/-数字かそのようなものです。助けて！

ホール1：開始位置= 168、サイズ= 12

穴2：開始位置= 665、サイズ= 12

孔4：開始位置= 506、サイズ= 14

ホール5：開始位置= 908、サイズ= 30

孔11：開始位置= 498、サイズ= 31

孔13：開始位置= 340、サイズ= 38

孔14：開始位置= 378、サイズ= 44

孔29：開始位置= 303、サイズ= 54

孔30：開始位置= 948、サイズ= 58

ホール60：あなたは

int printHoles(struct Node_h* cur, int num) { 
    if(cur == NULL) { 
     return num; 
    } 
    num = printHoles(cur->left, num) + 1; 
    printf("Hole %d: start location = %d, size = %d\n", num, cur->start_addr, cur->size); 
    num = printHoles(cur->right, num); 
    return num; 
} 

それの笙のようなあなたの機能を書き換える場合は場所= 503、サイズ= 70

Answer 1

// num is the number of nodes printed so far 
// return the number of nodes printed so far 
int printHoles(struct Node_h* cur, int num) { 
    if(NULL == cur) { 
     // last printed not changed 
     return num; 
    } 
    num = printHoles(cur->left, num); 
    printf("%d. size = %d\n", num + 1, cur->size); 
    num = printHoles(cur->right, num + 1); 
    return num; 
} 

我々はこれまでに印刷されたノードの数を追跡するためnumを使用することができます。 tを使用しないと、これはより明確で正しいはずです。

Answer 2

を開始uldは、出力された値の数を正しく追跡します。それぞれprintf() -callの前に、numは1だけインクリメントされ、各再帰呼び出しが返されます。それまで出力された値の数。これはあなたが期待することを行うはずです。

Answer 3

numは、ノードが訪問された直後にポインタとインクリメントになります。以下の修正を加えて、printHolesはもはやintを返す必要がありません：

void printHoles(struct Node_h* cur, int* num) { 
    if (cur == NULL) { 
    return; 
    } 
    printHoles(cur->left, num); 
    printf("Hole %d: start location = %d, size = %d\n", *num, cur->start_addr, cur->size); 
    (*num)++; 
    printHoles(cur->right, num); 
}