0

我一直在玩这个二叉搜索树一段时间，但我似乎无法插入或更改任何树属性。

我的二叉树定义为：

struct tree{
    Node * root;
    int size;
};
struct node{
    int value;
    Node * left;
    Node * right;
};

因此我的二叉树由节点组成。现在不起作用的位：

void add(int value, Tree *t){
    //1. if root is null create root
    if(t->root == NULL){
        t->root = nodeCreate(value);
        t->size ++;
        return;
    }
    Node * cursor = t->root;

    while(cursor != NULL){
        if(value == cursor->value){
            printf("value already present in BST\n");
            return;
        }
        if(value < cursor->value){
            cursor = cursor->left;
        }
        if(value > cursor->value){
            cursor = cursor->right;
        }
    }
    //value not found in BST so create a new node.
    cursor = nodeCreate(value);
    t->size = t->size + 1;
}

有人可以告诉我哪里出错了吗？我预计调用add()会增加成员的大小以及创建新节点，但我似乎无法得到它。

4

3 回答 3

1

您的循环中既有设计缺陷，也有彻底的错误。

设计缺陷：您正在分配一个新节点，但分配给cursor并不意味着您将首先分配给您的父节点左或右子指针。您需要对要填充的实际指针的引用。一种方法是使用指向指针的指针，作为奖励，这消除了开头的 is-my-root-null 检查。

彻底的错误：您的左侧移动子句（即追逐左侧指针）可能会更改cursor为 NULL。但是在else if条件下不排除追逐右侧的逻辑。如果您的搜索跟随左侧为空，则在追逐空指针的右侧时会出错。这显然是个问题。

void add(int value, Tree *t)
{
    Node **pp = &(t->root);
    while (*pp)
    {
        if(value == (*pp)->value) {
            printf("value already present in BST\n");
            return;
        }
        if(value < (*pp)->value)
            pp = &(*pp)->left;

        else if(value > (*pp)->value)
            pp = &(*pp)->right;
    }
    *pp = nodeCreate(value);
    t->size++;
}

我还应该注意，您可以通过假设严格-弱顺序来跳过相等性检查。即以下规则可以被认为是有效的：

if (!(a < b) && !(b < a)) then a == b is true.

这也使您的插入更简单。

void add(int value, Tree *t)
{
    Node **pp = &(t->root);
    while (*pp)
    {
        if (value < (*pp)->value)
            pp = &(*pp)->left;

        else if ((*pp)->value < value)
            pp = &(*pp)->right;

        else { // must be equal.
            printf("value already present in BST\n");
            return;
        }
    }
    *pp = nodeCreate(value);
    t->size++;
}
于 2013-10-25T17:15:53.817 回答
1

我相信以下更改将解决您的问题。

void add(int value, Tree *t){
    if(t->root == NULL){
        t->root = nodeCreate(value);
        t->size ++;
        return;
    }
    Node * cursor = t->root;
    Node * last = null;
    while(cursor != NULL){
        last = cursor;
        if(value == cursor->value){
            printf("value already present in BST\n");
            return;
        }
        if(value < cursor->value){
            cursor = cursor->left;
        }
        if(value > cursor->value){
            cursor = cursor->right;
        }
    }
    //value not found in BST so create a new node.
    cursor = nodeCreate(value);
    if (value > cursor->value)
    {
        last->right = cursor;
    }
    else
    {
        last->left = cursor;
    }
    t->size = t->size + 1;
}
于 2013-10-25T17:13:01.743 回答
0

您没有分配任何现有节点以指向新节点。您遍历树，到达尽头时创建一个新节点，但您没有将任何现有节点设置为指向新节点。

您可能希望将结构更改为：

if ( value < cusor->value )
{
  if ( cursor->left )
  {
    cursor = cursor->left;
  }
  else
  {
    cursor->left = newNode(value);
    break;
  }
}

与右手光标类似的逻辑。

于 2013-10-25T17:25:36.507 回答