BST 链接和案例不起作用

Question

我有一个这样的嵌套结构

typedef struct Node_link {
    struct Node_base *parent, *left, *right;
}Node_link;


typedef struct Node_base {
    struct Node_link link[2];
}Node_base;

typedef struct Node{
    struct Node_base base;
    int size;
    int *address;
}Node;


Node_base *head[2] ={NULL, NULL}; 
//head[0] stores int size and head[1] it's corresponding address

节点有右节点、左节点和父节点link，都是嵌套的，例如node->left->link.parent=node。我必须维护所有 links(parent, left and right) 并删除节点。我已经尝试了很多案例，但仍然遗漏了一些案例。有人可以告诉我我需要使用的所有情况吗？或向我推荐一些 material？我搜索了很多但没有成功。我的插入函数如下：

Node_base *   insert(Node_base *location, Node_base *n) {
    if (head[0]==NULL)
    head[0]=n;
else
{
    if (location==NULL){
        location=n;
        return location;
    }
    else{

        if(((Node *)n)->size < ((Node *)location)->size){
            if(location->link[0].left==NULL)
            {
                location->link[0].left=n;
                location->link[0].left->link[0].parent=location;
            }
            else
                location->link[0].left=insert(location->link[0].left,n);
        return location;
    }
}

我对 head[1] 有相同的嵌套插入函数，它存储插入到 head[0] 中的节点的大小。

Answer 1

很难说这是怎么回事。您的代码看起来一点也不像我见过的任何 BST 实现。为什么需要 Node_Link 结构？ Node 结构中的指针应该定义链接是什么。为什么是父指针？在标准的 BST 实现中不需要这样做。您只需要：

struct node {
    node *left;
    node *right;
    void *data;
    int size;
};

struct bst {
    node *root;
};

BST 链接和案例不起作用

BST Links and cases not working

c

binary-search-tree