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

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 也是如此，因为 then p->next = NULL。所以它不会添加新节点。树保持不变。

它并没有就此停止。当您丢失了新分配的节点的地址时 - 您会在此处发生内存泄漏。

然后是解决方案

if( p->next == NULL )

好吧，当我们到达叶级别时，它将等于 NULL，然后您将新分配的节点的地址分配给它。这解决了问题。

几件事-

1. 检查malloc 的返回值。如果失败，它将返回 NULL。 ₁

   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)。

---

释放树有点棘手，因为您必须始终执行后序遍历。您需要先释放 child ，然后再释放 parent 。否则会出现内存泄漏。

<子>1。早些时候我提到 fprintf(stderr,...) Basile Starynkevitch 使用 perror 这是打印诊断错误消息的不错选择。