如何在C语言中从数组构建二叉树？递归索引异常问题求助

问题描述 #

通过前序遍历（根->左->右）从数组构建二叉树，数组中-1代表空节点。尝试用index变量遍历数组时，左节点构建正常，但右节点数值与左节点完全相同，需排查原因并解决。

问题代码 #

#include<stdio.h>
#include<stdlib.h>
typedef struct no{
    int data;
    struct no * left;
    struct no * right;
}node;
node* building_node(int);
node* building_binary_tree(int*,int,node*);
int main()
{
    system("clear||cls");
    int a[]={4,2,9,-1,-1,8,-1,-1,7,-1,-1};
    node*root=NULL;
    root=building_binary_tree(a, -1,root);
    printf("The Binary Has:\n\n");
    printf("root = %d \n",root->data);
    printf("root->left = %d \n",root->left->data);
    printf("root->right = %d \n",root->right->data);
    // printf("%d ",root->left->left->data);
    // printf("%d ",root->left->right->data);
}
 
node * building_node(int data)
{
    //for building an empty node with data
    node* newnode=(node*)calloc(1,sizeof(node));
    newnode->data=data;
    newnode->right=NULL;
    newnode->left=NULL;
    return newnode;
}

node* building_binary_tree(int* a,int index,node* root)
{  
    //for building the tree recursively
    index++;
    if(a[index]==-1) return NULL;
    root=building_node(a[index]);
    root->left=building_binary_tree(a,index,root->left);
    root->right=building_binary_tree(a,index,root->right);
    return root;
}

问题根源 #

核心问题是**index变量按值传递**：

• 递归调用左子树时，index的修改仅在当前递归栈中生效，不会同步到父函数的index变量。
• 当左子树递归完成后，构建右子树时传入的仍是父函数未修改的index值，导致右子树从左子树的起始位置重新读取数组，最终出现值重复的情况。

比如构建根节点4后，index变为0；调用左子树时，index在递归中逐步递增到5（处理完2的左右子节点），但回到根节点的右子树调用时，传入的index还是0，导致右子树重新从index=0开始读取，重复构建出与左子树相同的节点。

解决方法 #

有两种可行方案，优先推荐第二种（避免全局变量副作用）：

方案1：使用全局变量存储index #

将index声明为全局变量，所有递归调用共享同一个index值，修改会全局生效：

#include<stdio.h>
#include<stdlib.h>
typedef struct no{
    int data;
    struct no * left;
    struct no * right;
}node;
node* building_node(int);
node* building_binary_tree(int*, node*);
int index = -1; // 全局index变量

int main()
{
    system("clear||cls");
    int a[]={4,2,9,-1,-1,8,-1,-1,7,-1,-1};
    node*root=NULL;
    root=building_binary_tree(a, root);
    printf("The Binary Has:\n\n");
    printf("root = %d \n",root->data);
    printf("root->left = %d \n",root->left->data);
    printf("root->right = %d \n",root->right->data);
    printf("%d \n",root->left->left->data); // 输出9
    printf("%d \n",root->left->right->data); // 输出8
}
 
node * building_node(int data)
{
    node* newnode=(node*)calloc(1,sizeof(node));
    newnode->data=data;
    newnode->right=NULL;
    newnode->left=NULL;
    return newnode;
}

node* building_binary_tree(int* a, node* root)
{  
    index++;
    if(a[index]==-1) return NULL;
    root=building_node(a[index]);
    root->left=building_binary_tree(a, root->left);
    root->right=building_binary_tree(a, root->right);
    return root;
}

方案2：使用指针传递index（推荐） #

将index的指针作为参数传递，递归中对index的修改会直接作用于原变量，避免全局变量的副作用（比如多次调用构建函数时不会互相干扰）：

#include<stdio.h>
#include<stdlib.h>
typedef struct no{
    int data;
    struct no * left;
    struct no * right;
}node;
node* building_node(int);
node* building_binary_tree(int*, int*, node*);

int main()
{
    system("clear||cls");
    int a[]={4,2,9,-1,-1,8,-1,-1,7,-1,-1};
    node*root=NULL;
    int index = -1; // 局部index变量
    root=building_binary_tree(a, &index, root);
    printf("The Binary Has:\n\n");
    printf("root = %d \n",root->data);
    printf("root->left = %d \n",root->left->data);
    printf("root->right = %d \n",root->right->data);
    printf("%d \n",root->left->left->data); // 输出9
    printf("%d \n",root->left->right->data); // 输出8
}
 
node * building_node(int data)
{
    node* newnode=(node*)calloc(1,sizeof(node));
    newnode->data=data;
    newnode->right=NULL;
    newnode->left=NULL;
    return newnode;
}

node* building_binary_tree(int* a, int* index, node* root)
{  
    (*index)++; // 递增指针指向的原变量
    if(a[*index]==-1) return NULL;
    root=building_node(a[*index]);
    root->left=building_binary_tree(a, index, root->left);
    root->right=building_binary_tree(a, index, root->right);
    return root;
}

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