使用数组创建二叉树后遍历结果异常，求错误排查与修复建议

我尝试用给定数组创建二叉树，输出中序（inorder）、前序（preorder）、后序（postorder）遍历结果，但输出存在明显错误，当前程序输出：

1 2 3 4 5 6 7 8 9 10  #inorder
10 9 8 7 6 5 4 3 2 1  #postorder
1 2 3 4 5 6 7 8 9 10  #preorder

以下是我编写的C语言代码：

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

typedef struct node_s node_t;
struct node_s
{
    int key;
    node_t *left,*right;
};
node_t *new_node(int val)
{
    node_t *new;
    new= malloc(sizeof (node_t));
    if(new==NULL)
    {
        exit(1);
    }
    new->key=val;
    new->left=NULL;
    new->right=NULL;
    return new;
}
void print_inorder(node_t *root)
{
    node_t *new=root;
    if (new != NULL) {
        print_inorder(new->left);
        printf("%d ",new->key);
        print_inorder(new->right);
    }
    return;

}
void print_postorder(node_t *root)
{
    node_t *new=root;
    if (new != NULL) {
        print_postorder(new->left);
        print_postorder(new->right);
        printf("%d ",new->key);
    }
    return;

}
void print_preorder(node_t *root)
{
    node_t *new=root;
    if (new != NULL) {
        printf("%d ",new->key);
        print_preorder(new->left);
        print_preorder(new->right);
    }
    return;

}
node_t *insert_node(node_t *root,int val)
{
     if(root==NULL)
            return new_node(val);
     else
     {
         if(val<root->left)
             root->left= insert_node(root->left,val);
         else if(val>root->left)
             root->right= insert_node(root->right,val);
     }
    return root;
}
int main() {

    int n;
    int v[]={1,2,3,4,5,6,7,8,9,10};
    node_t *root=NULL;
    FILE *file;
    file= fopen("file","r");
    if(file==NULL)
    {
        exit(1);
    }
    for (int i = 0; i < 10; ++i) {
        root= insert_node(root,v[i]);
    }

    print_inorder(root);
    printf("\n");
    print_postorder(root);
    printf("\n");
    print_preorder(root);

    return 0;
}

错误原因分析 #

1. 插入函数核心逻辑错误：insert_node函数中，你将插入值val和root->left（指针地址）做比较，而非和当前节点的root->key（数值）比较。这种指针地址的比较完全不符合二叉搜索树的插入规则，导致所有节点都被错误地插入到单侧，形成了一条链表，所以遍历结果出现异常。
2. 冗余文件操作：main函数中打开了"file"文件，但后续没有任何读取或使用操作，且文件不存在时直接退出程序，完全没必要保留。

修复方案 #

1. 修正insert_node的比较逻辑，将root->left替换为root->key，同时处理值相等的情况（比如直接返回，避免重复插入）。
2. 移除main中无用的文件操作代码。

修复后的完整代码 #

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

typedef struct node_s node_t;
struct node_s
{
    int key;
    node_t *left,*right;
};

node_t *new_node(int val)
{
    node_t *new_node_ptr = malloc(sizeof(node_t));
    if(new_node_ptr == NULL)
    {
        exit(1);
    }
    new_node_ptr->key = val;
    new_node_ptr->left = NULL;
    new_node_ptr->right = NULL;
    return new_node_ptr;
}

void print_inorder(node_t *root)
{
    if (root != NULL) {
        print_inorder(root->left);
        printf("%d ", root->key);
        print_inorder(root->right);
    }
}

void print_postorder(node_t *root)
{
    if (root != NULL) {
        print_postorder(root->left);
        print_postorder(root->right);
        printf("%d ", root->key);
    }
}

void print_preorder(node_t *root)
{
    if (root != NULL) {
        printf("%d ", root->key);
        print_preorder(root->left);
        print_preorder(root->right);
    }
}

node_t *insert_node(node_t *root, int val)
{
    if(root == NULL)
        return new_node(val);
    
    if(val < root->key)
        root->left = insert_node(root->left, val);
    else if(val > root->key)
        root->right = insert_node(root->right, val);
    // 处理值相等的情况，直接返回原节点，避免重复插入
    return root;
}

int main() {
    int v[] = {1,2,3,4,5,6,7,8,9,10};
    node_t *root = NULL;

    for (int i = 0; i < 10; ++i) {
        root = insert_node(root, v[i]);
    }

    printf("inorder: ");
    print_inorder(root);
    printf("\n");
    
    printf("postorder: ");
    print_postorder(root);
    printf("\n");
    
    printf("preorder: ");
    print_preorder(root);
    printf("\n");

    return 0;
}

修复后说明 #

修复后的代码会正确构建二叉搜索树，遍历结果会符合二叉搜索树的特性：

• 中序遍历：1 2 3 4 5 6 7 8 9 10（二叉搜索树的中序遍历天然有序）
• 前序遍历：1 2 3 4 5 6 7 8 9 10（因为输入数组是递增的，构建的树仍然是左斜链表，这是输入数组的特性导致的，若想构建平衡二叉树需要调整插入顺序或使用平衡树算法）
• 后序遍历：10 9 8 7 6 5 4 3 2 1（同样因为左斜链表的结构）

如果需要构建平衡的二叉树，可以调整输入数组的顺序，比如采用折半插入的方式，或者使用AVL树、红黑树等平衡树结构。

内容的提问来源于stack exchange，提问作者Severjan Lici