c - 二叉树 InOrderWalk 实现未按预期工作

Question

我正在尝试在 C 中实现一个二叉树数据结构，并在几次插入后进行中序遍历。 该程序仅打印我插入的第一个元素，而不打印任何其他节点。

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

struct tree
{

   struct node *root;

};


struct node
{

  int val;

  struct node *left;

  struct node *right;

};


struct tree *init ()
{

  struct tree *t = malloc (sizeof (struct tree));


  t->root = NULL;

  return t;

}



void insert (struct tree *t, int val)
{

  struct node *succ;

  struct node *new = malloc (sizeof (struct node));


  new->val = val;

  new->left = NULL;

  new->right = NULL;


  succ = NULL;

  struct node *insertPlace = t->root;

  while (insertPlace != NULL)
  {

       succ = insertPlace;

       if (insertPlace->val < new->val)

       insertPlace = insertPlace->right;

       else

       insertPlace = insertPlace->left;

   }

  if (succ == NULL)
    t->root = new;

  else if (new->val < succ->val)

    insertPlace = succ->right;

  else

   insertPlace = succ->left;

}



void inorderWalk (struct node *p)
{

  if (p != NULL)
  {

    if (p->left != NULL)
      inorderWalk (p->left);

    printf ("%d ", p->val);

    if (p->right != NULL)
       inorderWalk (p->right);

  }

}



void
print (struct tree *t)
{

struct node *p;

p = t->root;


inorderWalk (p);


} 



int

main ()
{

struct tree *t = init ();

insert (t, 5);

insert (t, 15);

insert (t, 20);

insert (t, 1);

insert (t, 2);

insert (t, 4);

insert (t, 10);


print (t);


return 0;

}

代码也可用here使用在线 gdb 调试器。

对于代码未按预期工作的原因的任何反馈都将不胜感激。

预先感谢您的帮助。

Answer 1

除了根之外，您的代码没有向树中添加元素。设置 insertPlace = succRight 只会更新 insertPlace 变量，不会更新树中的任何内容。

我建议在寻找正确节点的实际循环中设置左节点或右节点的值:

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

struct tree
{
   struct node *root;
};


struct node
{
  int val;

  struct node *left;

  struct node *right;
};


struct tree *init ()
{
  struct tree *t = malloc (sizeof (struct tree));
  t->root = NULL;
  return t;
}



void insert (struct tree *t, int val)
{

  struct node *succ;

  struct node *new = malloc (sizeof (struct node));
  new->val = val;
  new->left = NULL;
  new->right = NULL;

  succ = NULL;

  struct node* insertAtNode=t->root;
  if (insertAtNode==NULL) {
    t->root=new;
    return;
  }
  do {
    if (insertAtNode->val < new->val) {
      if (insertAtNode->right==NULL) {
        insertAtNode->right=new;
        return;
      } else {
        insertAtNode=insertAtNode->right;
      }
    } else if (insertAtNode->left==NULL) {
      insertAtNode->left=new;
      return;
    }
    else {
      insertAtNode=insertAtNode->left;
    }
  }
  while(1);
}



void inorderWalk (struct node *p)
{
  if (p != NULL)
  {
    if (p->left != NULL)
      inorderWalk (p->left);
    printf ("%d ", p->val);
    if (p->right != NULL)
       inorderWalk (p->right);
  }
}



void print (struct tree *t)
{
  struct node *p;

  p = t->root;

  inorderWalk (p);
  printf("\n");
}



int main ()
{
  struct tree *t = init ();

  insert (t, 5);

  insert (t, 15);

  insert (t, 20);

  insert (t, 1);

  insert (t, 2);

  insert (t, 4);

  insert (t, 10);


  print (t);


  return 0;

}