二叉搜索树的搜索代码中的错误在哪里？

Question

我已经为严格的二进制搜索树编写了这段代码。 （如果二叉树中的每个非叶节点都有非空左右子树，则该树称为严格二叉树。或者，换句话说，严格二叉树中的所有节点都是零度或二度一个严格的二叉树，N个叶子总是包含2N - 1个节点。）不幸的是，它没有正确打印值。我不知道是什么问题。我在互联网上看过其他网站，代码几乎相同，但我仍然无法在我的代码中找到错误。

#include <stdio.h>
#include <stdlib.h>
struct node
{
    struct node* prev;
    int data;
    struct node* next;
};
void Binary_Search_Tree(struct node *newnode,struct node *p);
void print(struct node* p);

main()
{
    struct node *root,*nnode,*temp;
    int c,d;
    root=malloc(sizeof(struct node));

    printf("Enter the root data\t");
    scanf("%d",&d);
    root->data=d;
    root->prev=NULL;
    root->next=NULL;

    while(1)
    {
        printf("Enter your choice\n1 insert element.\n2 print tree.\n3 Exit");
        scanf("%d",&c);
        switch(c)
        {
            case 1:
                nnode=malloc(sizeof(struct node));
                printf("Enter the node data\t");
                scanf("%d",&d);

                nnode->data=d;
                nnode->prev=NULL;
                nnode->next=NULL;
                temp=root;

                Binary_Search_Tree(nnode,temp);
                break;
            case 2:
                temp=root;
                print(temp);
                break;
            case 3:
                free(root);
                free(nnode);
                free(temp);
                temp=nnode=root=NULL;
                exit(1);
                break;
        }
    }
    return 0;
}

void Binary_Search_Tree(struct node *newnode,struct node *p)
{

    if(newnode->data<p->data)
    {
        if(p->prev=NULL)
        {
            p->prev=newnode;
        }
        else if(p->prev!=NULL)
        {
            p=p->prev;
            Binary_Search_Tree(newnode,p);
        }
    }
    else if(newnode->data>p->data)
    {
        if(p->next=NULL)
        {
            p->next=newnode;
        }
        else if(p->next!=NULL)
        {
            p=p->next;
            Binary_Search_Tree(newnode,p);
        }
    }
}

void print(struct node* p)
{
    if(p!=NULL)
    {
        print(p->prev);
        printf("%d\n",p->data);
        print(p->next);
    }
}

Answer 1

主要问题是你使用了赋值来代替平等。

if( p->next=NULL )

与你的预期完全不同。这将是

if ( p->next == NULL )
             ^^^

同样的p->prev检查将是p->prev == NULL。

那么让我们分析你犯错的第一个案例。

if( p->next = NULL )

首先将NULL分配给p->next，然后我们知道赋值语句的结果是赋值。所以有条件的是

 if( NULL ) 

所以从未输入if声明。所以else因为然后p->next = NULL。所以它不会添加新节点。树保持不变。

它并没有就此止步。当你丢失了新分配节点的地址时 - 这里有内存泄漏。

然后是解决方案

if( p->next == NULL )

那么当我们达到叶子级别时它将等于NULL然后你为它分配新分配的节点的地址。这解决了这个问题。

一些事情 -

1. 检查malloc的返回值。万一失败，它将返回NULL。 1

   root=malloc(sizeof(struct node));
   if( root == NULL ){
      perror("Malloc failure");
      exit(EXIT_FAILURE);
   }

2. 完成后，释放动态分配的内存。

   void freeTree(struct node *root){
      if( root ){
         freeTree(root->prev);
         freeTree(root->next);
         free(root);
      }
   }

3. 启用编译器警告-Wall -Werror。如果您这样做，编译器会清楚地向您显示问题。

   error: suggest parentheses around assignment used as truth value [-Werror=parentheses]
            if(p->next=NULL)
            ^~

4. 另外一件事是检查scanf的返回值。

   if( scanf("%d",&d) != 1 ){
     // Input failed 
     exit(EXIT_FAILURE); // or handle error.
   }

5. 正如Jonathan Leffler在评论中提到的那样，如果你正确地写出语句，可读性将会提高。 else if(newnode->data>p->data)很难读。相比之下，else if (newnode->data > p->data)更具可读性。当您编写语句if(p->next = NULL)时，您的眼睛很容易看到错误。显而易见的是if(p->next == NULL)。

---

释放树有点棘手，因为您必须始终执行后订单遍历。你需要先释放孩子，然后你就可以解雇父母。否则会有内存泄漏。

1.之前我提到fprintf(stderr,...) Basile Starynkevitch使用perror，这是打印诊断错误消息的好选择。