如何实现迭代创建二叉树？程序出现无限循环求解析

导致无限循环的核心原因 #

1. 递归遍历函数错误添加while循环 #

你的前序、中序、后序遍历函数都在递归外层多余添加了while(root != NULL)循环。以preorder为例：

void preorder(NODE* root){
    while(root != NULL){ // 此处while完全多余且致命
        printf(" %d ",root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

当调用遍历函数时，只要root不为空，while就会反复执行循环体：每次打印当前节点后递归遍历左子树，左子树遍历完成后回到当前循环，再次重复打印、递归左子树的操作——由于root的值在循环内从未修改，始终不为空，直接触发无限递归+循环。

递归遍历的本质是通过函数调用栈实现遍历，只需用if判断root是否为空作为递归终止条件，完全不需要外层while。

2. main函数错误插入终止标记-1到树中 #

在输入循环里，你先调用createTree(&root,data)插入节点，再判断data == -1才停止。这会导致用户输入-1时，程序先把-1作为有效节点插入二叉树，再停止输入，既不符合“输入-1停止”的预期，还会让树中多一个无意义节点。

修正后的完整代码 #

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

typedef struct node{
    int data;
    struct node *left,*right;
} NODE;

NODE* createNode(int ele){
    NODE* newnode = (NODE*)malloc(sizeof(NODE));
    newnode->data = ele;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}

// 修正后的中序遍历
void inorder(NODE* root){
    if(root != NULL){
        inorder(root->left);
        printf(" %d ",root->data);
        inorder(root->right);
    }
}

// 修正后的前序遍历
void preorder(NODE* root){
    if(root != NULL){
        printf(" %d ",root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

// 修正后的后序遍历
void postorder(NODE* root){
    if(root != NULL){
        postorder(root->left);
        postorder(root->right);
        printf(" %d ",root->data);
    }
}

void createTree(NODE** root, int ele){
    NODE* newnode = createNode(ele);
    if(*root == NULL){
        *root = newnode;
        return;
    }
    NODE* curr = *root;
    while (1){
        if(ele <  curr->data){
            if(curr->left == NULL){
                curr->left = newnode;
                return;
            }
            curr = curr->left;
        }
        else{
            if (curr->right == NULL){
                curr->right = newnode;
                return; 
            }
            curr = curr->right;
        }
    }
}

int main(){
    NODE* root = NULL;
    int data;
    while(1){
        printf("Enter the data for the binary tree(Enter -1 to stop): \n");
        scanf("%d",&data);
        if(data == -1){ // 先判断终止条件，再决定是否插入节点
            break;
        }
        createTree(&root,data);
    }
    printf("\nPreorder traversal:\n");
    preorder(root);

    printf("\nInorder traversal:\n");
    inorder(root);

    printf("\nPostorder traversal:\n");
    postorder(root);
    
    return 0;
}

额外说明 #

你的createTree迭代创建二叉搜索树的逻辑是正确的，无需修改。修正后，程序会在输入-1时直接停止输入，不会插入无效节点，同时遍历函数可正常完成递归遍历，无无限循环问题。

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