c - 二叉搜索树的中序遍历，显示一些错误

Question

这是我用于 BST 中序遍历的函数

void inOrder(struct node* root)
{
    if(root==NULL)
    {
      return;
    }
    inOrder(root->left);
    printf("Key:%d,Pointer:%p\n",root->key,root);
    inOrder(root->right);
}

同样的结构是

struct node{
    int key;
    struct node *left,*right;
};

当我运行该函数时，我为以下插入获得了两个额外的 0 元素:

root=insert(root,7);
insert(root,4);
insert(root,10);
insert(root,3);
insert(root,5);
insert(root,1);
insert(root,2);
insert(root,0);
insert(root,8);
insert(root,14);
insert(root,6);
insert(root,9);
insert(root,16);
insert(root,12);
insert(root,15);
insert(root,17);
inOrder(root);printf("\n");

插入函数如下:

struct node *insert(struct node * root,int ele)
{
  struct node *temp=newNode(ele);
  struct node *tree=root;
  struct node *saver;

  if(root==NULL)
  {
    root=temp;
  }
  else
  {
    while(tree!=NULL)
    {
       saver=tree;      
        if(ele<tree->key)
          tree=tree->left;
        else
          tree=tree->right;
    }
    if(ele<saver->key)
    {
      saver->left=temp;
    }
    else
    {
      saver->right=temp;
    }
  }
  return saver;
}

除了我添加的主要元素外，输出显示两个 0。我最近学习了二叉搜索树，并尝试实现它，请有人帮我纠正这个错误。提前谢谢你

Answer 1

在插入

if(root==NULL)
    {root=temp;
    }

必须是

if(root==NULL)
{
  saver=temp;
}

因为你返回saver(在你的版本中没有初始化)

我想在您的 main 中，代码也不是您提供的，而是类似于

struct node * root = NULL;

root=insert(root,7);
insert(root,4);
...

如果我这样定义 newNode :

struct node * newNode(int ele)
{
  struct node * r = malloc(sizeof(struct node));

  r->key = ele;
  r->left = r->right = NULL;
  return r;
}

然后我进行其他更改:

pi@raspberrypi:/tmp $ gcc -g -pedantic -Wextra n.c
pi@raspberrypi:/tmp $ ./a.out
Key:0,Pointer:0xf04078
Key:1,Pointer:0xf04058
Key:2,Pointer:0xf04068
Key:3,Pointer:0xf04038
Key:4,Pointer:0xf04018
Key:5,Pointer:0xf04048
Key:6,Pointer:0xf040a8
Key:7,Pointer:0xf04008
Key:8,Pointer:0xf04088
Key:9,Pointer:0xf040b8
Key:10,Pointer:0xf04028
Key:12,Pointer:0xf040d8
Key:14,Pointer:0xf04098
Key:15,Pointer:0xf040e8
Key:16,Pointer:0xf040c8
Key:17,Pointer:0xf040f8

---

完整代码为:

#include <stdio.h>
#include <stdlib.h>

struct node{
    int key;
    struct node *left,*right;
};

void inOrder(struct node* root)
    {
    if(root==NULL)
        {return;}
    inOrder(root->left);
    printf("Key:%d,Pointer:%p\n",root->key,root);
    inOrder(root->right);
    }

struct node * newNode(int ele)
{
  struct node * r = malloc(sizeof(struct node));

  r->key = ele;
  r->left = r->right = NULL;
  return r;
}

struct node *insert(struct node * root,int ele)
{
  struct node *temp=newNode(ele);
  struct node *tree=root;
  struct node *saver;

  if(root==NULL)
  {
    saver=temp;
  }
  else
  {
    while(tree!=NULL)
    {
      saver=tree;        
      if(ele<tree->key)
        tree=tree->left;
      else
        tree=tree->right;
    }
    if(ele<saver->key)
    {
      saver->left=temp;
    }
    else
    {
      saver->right=temp;
    }
  }
  return saver;
}

int main()
{
  struct node * root = NULL;

  root=insert(root,7);
  insert(root,4);
  insert(root,10);
  insert(root,3);
  insert(root,5);
  insert(root,1);
  insert(root,2);
  insert(root,0);
  insert(root,8);
  insert(root,14);
  insert(root,6);
  insert(root,9);
  insert(root,16);
  insert(root,12);
  insert(root,15);
  insert(root,17);
  inOrder(root);printf("\n");
}