树的意外预序遍历

Question

当我执行我的代码时，我得到了错误的二叉树预序遍历结果。我期待我的程序打印这个预购订单 5 -> 4 -> 3 -> 2-> 6 -> 7 -> 8。我无法指出我在代码中的错误。请告诉我哪里做错了。

这是我的输入和输出（样本运行）：

ENTER THE NODE DATA
5
ENTER YOUR CHOICE
ENTER THE NODE DATA
4
ENTER YOUR CHOICE
ENTER THE NODE DATA
6
ENTER YOUR CHOICE
ENTER THE NODE DATA
3
ENTER YOUR CHOICE
ENTER THE NODE DATA
7
ENTER YOUR CHOICE
ENTER THE NODE DATA
2
ENTER YOUR CHOICE
ENTER THE NODE DATA
8
ENTER YOUR CHOICE
5 -> 4 -> 3 -> 2 -> 8 -> 7 -> 6 ->

这是创建二叉树并打印树的前序遍历的代码。

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

struct node {
               int data;
               struct node *right;
               struct node *left;
            }  *tmp  = NULL;

typedef struct node NODE;

  NODE *root = NULL;
  NODE *child, *new_node;

 void preorder(NODE *t)
{
     if(t != NULL)
     {
            printf("%d -> ",t->data);
            preorder(t->left);
            preorder(t->right);
     }//IF
 } 
  int main ()
  {
      char choice;
      do{
           new_node = (NODE *)malloc(sizeof(NODE));
           printf("ENTER THE NODE DATA \n");
           scanf("%d",&new_node -> data);

           new_node -> right = NULL;
           new_node -> left  = NULL;

           if(root == NULL)
           {
                   root = new_node;
                   tmp  = new_node;
           }//IF

           else
           {
               child = new_node;

               while(1)
               {
                       if(child -> data < tmp -> data)
                       {
                             if(tmp -> left == NULL)
                              {
                                  tmp -> left = new_node;
                                  break;  
                              }//if2  
                              tmp  = tmp -> left;
                       }//if1

                       if(child -> data > tmp -> data)
                       {
                           if(tmp -> right == NULL)
                           {
                               tmp -> right = new_node;
                               break;
                           }//if4
                           tmp = tmp -> right;
                       }//if3
               }//while
           }//else
           printf("\n ENTER YOUR CHOICE \n");
           choice = getch();
        }//do
         while(choice != 'n');
         preorder(root);
         getch();
         return 0;
  }//main

Answer 1

您没有在每次迭代中都将 tmp 重置为根。

请注意，根本不需要变量 child，因为它的值与 new_node 的值完全相同。

Answer 2

在do while中添加如下语句。

else {
child=new_node;
tmp=root;
...
...
}

每次循环后，tmp值都会改变。我们必须用根本身检查新值。

树的意外预序遍历

Unexpected Pre-order traversal of Tree

c

data-structures