c - 打印带有编号节点的二叉搜索树

Question

我想要对 BST 进行按序遍历并打印节点。我可以很好地打印树，但我无法正确编号。

如果有人想编译并尝试一下，这里是所有代码。谢谢!

#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 洞:起始位置 = 503，大小 = 70

Answer 1

将 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);
}