Обход в порядке бинарного дерева поиска, показывает некоторые ошибки - PullRequest
Новая
       11

Обход в порядке бинарного дерева поиска, показывает некоторые ошибки

0 голосов
/ 04 марта 2019

Это функция, которую я использую для прохождения BST inorder 

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, кроме основных элементов, которые я добавил.Недавно я изучил Binary-Search-Tree и попытался его реализовать. Может кто-нибудь помочь мне исправить эту ошибку.Заранее спасибо

1 Ответ

0 голосов
/ 04 марта 2019

in insert 

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");
}
...