c - 有序二叉树插入

Question

下面这段代码有问题，它是有序二叉树程序的一部分。问题是，当我在输入中输入数字时，一些元素就丢失了，而且它一直在发生。我查看了代码，无法弄清楚为什么会这样。你能帮我解决这个问题吗？谢谢。

void insert_ord(int number, struct treenode *currentNode){
   if(currentNode->flag == 0){
      currentNode->number = number;
      currentNode->flag = 1;                  
   }
   else{
      if(number <= currentNode->number){
         if(currentNode->left != NULL) insert_ord(number, currentNode->left);
         else {
            struct treenode *store = (struct treenode *)malloc(sizeof(struct treenode));
            currentNode->left = store;
            store->number = number;
            store->left = store->right = NULL;
            store->prev = currentNode;
         }
      }
      if(number > currentNode->number){
         if(currentNode->right != NULL) insert_ord(number, currentNode->right);
         else {
            struct treenode *store = (struct treenode *)malloc(sizeof(struct treenode));
            currentNode->right = store;
            store->number = number;
            store->left = store->right = NULL;
            store->prev = currentNode;
         }
      }
   }
}

Answer 1

您没有为新插入的节点设置 store->flag。大概应该设置为1。

您还应该重构您的代码，这样新节点的创建就不会重复 - 使用当前代码执行此操作的最简单方法是将其分离到一个新函数中:

struct treenode *new_node(struct treenode *parent, int number)
{
    struct treenode *store = malloc(sizeof(struct treenode));

    if (store) {
        store->number = number;
        store->left = store->right = NULL;
        store->prev = parent;
        store->flag = 1;
    }

    return store;
}

然后你的插入代码就变成了:

if (currentNode->left)
    insert_ord(number, currentNode->left);
else
    currentNode->left = new_node(currentNode, number);

(和右节点类似)。