0

我有一个家庭作业来实现二叉搜索树（创建、删除、搜索）。我使用了老师提供的示例，但我无法使其工作。

到目前为止，这是我的代码：

void insert_node(int k){
    struct node *nodnou,*flow,*parent;

    nodnou = (struct node*)malloc(sizeof(node));
    nodnou->st = NULL;
    nodnou->dr = NULL;
    nodnou->nr = k;

    if (root==NULL)
    {
        root = (struct node*)malloc(sizeof(node));

        root = nodnou;
    }
    else
    {
        flow = (struct node*)malloc(sizeof(node));
        parent = (struct node*)malloc(sizeof(node));
        flow = root;
        parent = root;
        while (((flow->st!=NULL) || (flow->dr!=NULL)) && flow!=NULL)
        {
            if (k<flow->nr)
            {
                parent = flow;
                flow = flow->st;
            }
            else
            {
                parent = flow;
                flow = flow->dr;
            }
        }

        if (k<flow->nr)
        {
            parent->st = nodnou;
        }
        else
        {
            parent->dr = nodnou;
        }
    }
}

思路：这个函数获取我们要插入的节点的值作为k参数。该函数只会插入树的根（根是全局变量）。

我认为我最大的问题是while遍历树以找到新节点位置的循环。

如果我使用while (flow!=NULL)它，它将无法工作，因为流指针会分配给不存在的东西。请帮助我理解我错在哪里（作业）。

4

3 回答 3

3

你的代码有几个重要的缺陷，其中最重要的是误解了 C 中动态内存分配的工作原理。永远不要遵循这样的模式：

Type *pointer = malloc(sizeof(Type));
pointer = <<something else>>

它实际上会泄漏内存，并且在两行短行中没有任何好处。这不是像 Java 或 C# 这样的基于对象引用的语言。指针是保存内存地址的变量。就像一个int可以保存一个整数一样，一个指针保存一个地址。就像下面的例子：

int n = 6;
n = 5;      //Hmm. Where did the 6 go? Oh yeah, We overwrote it with 5.

你会失去你的分配链接，用指针做同样的事情：

struct node *root = malloc(sizeof(*root));
root = nodnou; // memory allocated above is gone. forever leaked.

指针是变量。就像任何其他变量一样，它们保存值。然而，在指针的情况下，它的值是一个地址。C 中几乎可以有指向任何东西的指针，包括指向指针的指针；保存指针变量地址的变量。我提出它们是因为它们为您的插入要求提供了一个特别优雅的解决方案。

以下是二叉树插入的一般实现，它支持树中没有重复项（如果允许重复，代码会变得更短）。此外，它使用超出提供的函数参数的零局部变量来执行此操作，我挑战您剖析它并确定它是如何工作的。它甚至可以在最初为 NULL 的树根指针上工作，无需特殊的大小写if (root) {} else {}逻辑：

void insert_node(struct node **pp, int k) 
{
    while (*pp)
    {
        if (k < (*pp)->nr)        // move down left side?
            pp = &(*pp)->st;

        else if ((*pp)->nr < k)   // move down right side?
            pp = &(*pp)->dr;

        else return;              // found the key, no dupes. leave
    }

    // pp contains the address of the pointer we need to set.
    *pp = malloc(sizeof(**pp)); 
    (*pp)->st = (*pp)->dr = NULL;
    (*pp)->nr = k;
}

如果您的树应该支持重复项，您需要在插入的哪一侧保持一致，但这会大大缩短上述算法：

void insert_node(struct node **pp, int k) 
{
    while (*pp)
        pp = (k < (*pp)->nr) ? &(*pp)->st : &(*pp)->dr;

    // pp contains the address of the pointer we need to set.
    *pp = malloc(sizeof(**pp)); 
    (*pp)->st = (*pp)->dr = NULL;
    (*pp)->nr = k;
}

在任何一种情况下，都在调用方调用，如下所示：

struct node *root = NULL;

insert(&root, 5);
insert(&root, 10);
insert(&root, 7); 
...etc...
于 2013-10-24T00:39:11.370 回答
0

你几乎明白了。赶上！

首先，您需要了解更好的内存分配。实际上，您只需要malloc()函数中的第一个调用。insert_node()这是您在每次调用期间为要附加到树的节点分配的内存。malloc您正在执行的所有剩余程序都是不必要的。您似乎直觉地觉得您需要为正在使用的其他指针分配内存，但它们都是临时的，不需要任何分配，只需在尝试取消引用它们之前分配给有效节点即可。事实上，这些不必要的分配会在如下代码中产生所谓的内存泄漏（您请求但未能释放的内存）：

root = (struct node*)malloc(sizeof(node));
root = nodnou;

第二个 assignmet ( root = nodnou) 会覆盖上一次malloc()调用的结果，由于您没有将覆盖的指针值保存在任何其他位置，您将无法再释放该内存，它将被标记为在您的生命周期内使用应用！

接下来，您可以简化遍历树以查找插入点的代码。您似乎担心 flow 会变为 NULL，但这没关系。重要的节点是父节点。while循环结束后，它将指向需要链接插入节点的实际节点。这是您的代码的修改版本。

void insert_node(int k) {
   struct node *nodnou, *flow, *parent;
   // this is the only memory allocation that should be done
   nodnou = (struct node*)malloc(sizeof(node));
   nodnou->st = NULL;
   nodnou->dr = NULL;
   nodnou->nr = k;

   parent = NULL;

   if( root == NULL ) {
      root = nodnou;
   } else {

      flow = root;
      // We will walk the tree in order until we reach the bottom of the 
      // tree (flow becomes null). What we are trying to do is to find out
      // the node that will become the parent of the new node we are inserting
      // It doesn't matter if flow becomes NULL, the important value after the
      // while loop ends is parent 
      while( flow != NULL ) {
         // update the current potential parent node
         parent = flow;
         if( k < flow->nr ) {
            // the number we are inserting is lower than the flow node, walk to the left
            flow = flow->st;
         } else {
            // the number we are inserting is greater or equal than the flow node, 
            // walk to the right
            flow = flow->dr;
         }
      }

      // We have reached the bottom, now compare number again with the node that
      // will become parent, to find out if we need to link this node to the left
      // or to the right of the parent node

      if( k < parent->nr ) {
         parent->st = nodnou;
      } else {
         parent->dr = nodnou;
      }
   }

}

而已。尝试编写其余的树操作，并毫不犹豫地询问您是否感到困惑。=)

于 2013-10-23T23:40:12.473 回答
0

我认为您应该使用 while(flow != NULL) 并在此之后将元素作为流插入。它现在的方式会在不应该的情况下停止，并在停止时做奇怪的事情。试着用笔和纸完成一些例子。

于 2013-10-23T19:59:29.227 回答