c - 树遍历没有给出预期的输出

Question

我有下面的简单代码，我相信这是遍历的标准。问题是我得到了一组特定输入的预期输出，而其他输入则得到了意外的输出。例如对于输入序列15,3,6,11,45,54,65,3,66我收到了预期的预购订单:15,3,6,11,45,54,65,66 。但对于序列45,3,54,65,23,66,5,3我希望预购 o/p 45,3,23,5,54,65,66但我得到 45 3 5 23 54 65 66 。对于后序，我对这两个序列都感到意外，得到 3,6,11,45,54,65,66,15和3,5,23,54,65,66,45当我期待11,6,3,66,65,54,45,15和5,23,3,66,65,54,45分别。是我理解错误还是我的代码有问题？

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

typedef struct treenode
{
  int val;
  struct treenode *left;
  struct treenode *right;
} bnode;

bnode *rootnd = NULL;

bnode * ins_node(bnode *bootstrap, bnode *newnode)
{
  if (bootstrap == NULL )
  {
    bootstrap = newnode;
  }
  else if (newnode->val < bootstrap->val)
    bootstrap->left = ins_node(bootstrap->left, newnode);
  else if (newnode->val > bootstrap->val)
    bootstrap->right = ins_node(bootstrap->right, newnode);

  return bootstrap;
}

void print_tree_inorder(bnode *root)
{
  if (root != NULL )
  {
    print_tree_inorder(root->left);
    printf("%d ", root->val);
    print_tree_inorder(root->right);
  }
}

void print_tree_postorder(bnode *root)
{
  if (root != NULL )
  {
    print_tree_inorder(root->left);
    print_tree_inorder(root->right);
    printf("%d ", root->val);
  }
}

void print_tree_preorder(bnode *root)
{
  if (root != NULL )
  {
    printf("%d ", root->val);
    print_tree_inorder(root->left);
    print_tree_inorder(root->right);
  }
}

int main(int argc, char *argv[])
{
  int insval;

  printf("Keep entering numbers... press 0 to finish\n");

  while (1)
  {
    scanf("%d", &insval);

    if (insval == 0)
      break;

    bnode *nd = malloc(sizeof(bnode));
    nd->val = insval;
    nd->left = NULL;
    nd->right = NULL;

    if (rootnd == NULL )
    {
      rootnd = nd;
    }
    else
      ins_node(rootnd, nd);
  }

  if (atoi(argv[1]) == 1)
    print_tree_preorder(rootnd);
  else if (atoi(argv[1]) == 2)
    print_tree_inorder(rootnd);
  else
    print_tree_postorder(rootnd);

  return 0;
}

Answer 1

你的例程没有像应该的那样递归地调用自己。请参阅下面代码中的注释。

void print_tree_inorder(bnode *root)
{
  if (root != NULL )
  {
    print_tree_inorder(root->left);
    printf("%d ", root->val);
    print_tree_inorder(root->right);
  }
}

void print_tree_postorder(bnode *root)
{
  if (root != NULL )
  {
    print_tree_inorder(root->left); // should be print_tree_postorder
    print_tree_inorder(root->right); // same
    printf("%d ", root->val);
  }
}

void print_tree_preorder(bnode *root)
{
  if (root != NULL )
  {
    printf("%d ", root->val);
    print_tree_inorder(root->left); // should be print_tree_preorder
    print_tree_inorder(root->right); // ditto
  }
}