如何在 C 的二叉搜索树中找到比选定数字更高值的下一个节点？

Question

例如：如果我的树数据具有以下值的节点 = (10, 20, 30, 40, 50, 60);

如果选择 45，那么我必须 return 具有下一个高度值的节点。（如果 45，则 50）。

如果没有更高的值，则必须 return NULL。

代码：

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

struct Tree {
    int x;
    struct Tree *left, *right;
};
typedef struct Tree Tree;

Tree * create_empty_tree() {
   return NULL;
}

Tree * insert(Tree *t, int x) {
    if (t == NULL) {
        t = (Tree *) malloc(sizeof(Tree));
        t->x= x;
        t->left = NULL;
        t->right = NULL;
    } else if (x < t->x) {
        t->left = insert(t->left, x);
    } else {
        t->right = insert(t->right, x);
    }
}

void print_in_order(Tree *arv) {
   if (arv != NULL) {
      print_in_order(arv->left);
      printf("%d, ", arv->x);
      print_in_order(arv->right);
   }
}

Tree * find_node_higher_than_x(Tree *t, int x) {
     //toDo
}

int main() {
    Tree *t = create_empty_tree();
    t = insert(t, 2);
    t = insert(t, 8);
    t = insert(t, 10);
    t = insert(t, 4);
    t = insert(t, 6);
    t = insert(t, 7);
    t = insert(t, 1);
    
    print_in_order(t);
    
    Tree *node = find_node_higher_than_x(t, 5); //Must return node with x == 6
}

有办法做到吗？

Answer 1

首先更正insert方法，使其总是returns一个节点。

你的函数可以这样工作：

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

struct Tree {
    int x;
    struct Tree *left, *right;
};
typedef struct Tree Tree;

// Create a separate function for constructing a tree node
Tree * create_tree(int x) { 
    Tree *t = (Tree *) malloc(sizeof(Tree));
    t->x= x;
    t->left = NULL;
    t->right = NULL; 
    return t;
}

Tree * create_empty_tree() {
    return NULL;
}

Tree * insert(Tree *t, int x) {
    if (t == NULL) {
        t = create_tree(x);
    } else if (x < t->x) {
        t->left = insert(t->left, x);
    } else {
        t->right = insert(t->right, x);
    }
    return t; // Must return it!
}

void print_in_order(Tree *arv) {
    if (arv != NULL) {
        print_in_order(arv->left);
        printf("%d, ", arv->x);
        print_in_order(arv->right);
    }
}

Tree * find_node_higher_than_x(Tree *t, int x) {
    if (t == NULL) return NULL;
    if (x >= t->x) return find_node_higher_than_x(t->right, x);
    Tree * temp = find_node_higher_than_x(t->left, x);
    return temp != NULL ? temp : t;
}

int main() {
    Tree *t = create_empty_tree();
    t = insert(t, 2);
    t = insert(t, 8);
    t = insert(t, 10);
    t = insert(t, 4);
    t = insert(t, 6);
    t = insert(t, 7);
    t = insert(t, 1);
    
    print_in_order(t);

    // Loop to repeatedly call this function and so traverse the tree
    Tree *node = find_node_higher_than_x(t, 0);
    while (node != NULL) {
        printf("\n%d", node->x);
        node = find_node_higher_than_x(t, node->x);
    }

    return 0; // Must return an int
}

如何在 C 的二叉搜索树中找到比选定数字更高值的下一个节点？

How can I find the next node higher value than a selected number in a Binary Search Tree in C?

c

search

data-structures

binary-search-tree

function-definition