I am making a program to test out binary search trees in the c language. I want to balance it using a less good array method. I dynamically allocate the array based on the number of nodes in the BST and send the array off to another function that does the search and should place the elements in the array. However, when I run the program just the first element (the root of the tree) shows up in the array with every other iteration nothing happens. I am not sure on what is wrong.

Below is a MCVE for the part of the program that does not work. The first code blocks are simply to make and fill a BST. And it's the sorterToArray function that does not work.

In the recursive function sorterToArray I have tried to send the next place in the array but that does not work since it "is a nullptr".

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;
};

typedef struct treeNode* BSTree;

void insertSorted(BSTree* tree, int data);
void sorterToArray(struct treeNode* temp, int* pArray, int i);
int counter(int i, const BSTree tree);
void goLeftAndRight(struct treeNode* newNode, struct treeNode* tempTree, const int data);
void balanceTree(BSTree* tree);
static int* writeSortedToArray(const BSTree tree);

int main(void) {
    BSTree tree = NULL;
    insertSorted(&tree, 10);
    for (int i = 0; i < 9; i  )
        insertSorted(&tree, i   20);

    balanceTree(&tree);

}

static struct treeNode* createNode(int data)
{
    //Creates the new node for the tree
    struct treeNode* newNode;

    //Allocates memory for the new node
    newNode = calloc(1, 1   sizeof(struct treeNode*));

    //Tests the new memory
    assert(newNode != NULL);

    //Assigns data to the new node
    newNode->data = data;

    //Sets the left and right pointers to NULL so that other functions know where the ends are
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode; //Returns the new node
}

void insertSorted(BSTree* tree, int data)
{

    //Creates a new temp struct
    struct treeNode* newNode = createNode(data);
    struct treeNode* tempTree = (*tree);

    //If the tree is empty then the data will be at the root
    if (tempTree == NULL) {
        (*tree) = newNode;
    }
    //If the tree is not empty the function will call the help function in order to find the right node.
    else {
        goLeftAndRight(newNode, tempTree, data);
    }
}

void goLeftAndRight(struct treeNode* newNode, struct treeNode* tempTree, const int data) {
    if (data < tempTree->data && tempTree->left == NULL) {
        tempTree->left = newNode;
        return;
    }
    else if (data > tempTree->data && tempTree->right == NULL) {
        tempTree->right = newNode;
        return;
    }

    if (data < tempTree->data && data != tempTree->data) {
        goLeftAndRight(newNode, tempTree->left, data);
    }
    else if (data > tempTree->data && data != tempTree->data) {
        goLeftAndRight(newNode, tempTree->right, data);
    }
}

int counter(int i, const BSTree tree) {

    if (tree->left != NULL)
        i = 1   counter(i, tree->left);
    if (tree->right != NULL)
        i = 1   counter(i, tree->right);

    return i;
}

void balanceTree(BSTree* tree) {
    int* sortedArray = writeSortedToArray((*tree));
}

//Code blocks writeSortedToArray ans SorterToArray are the ones causing the problems.
static int* writeSortedToArray(const BSTree tree)
{
    struct treeNode* temp = tree;
    int i = 0, number = 1   counter(i, tree);
    int* pArray = calloc(number, sizeof(int*));
    assert(pArray != NULL);

    sorterToArray(temp, pArray, i);

    return pArray;
}

//Function where the problem is most likely located.
void sorterToArray(struct treeNode* temp, int* pArray, int i) {

    if (temp->left != NULL)
        sorterToArray(temp->left, pArray, i);

    pArray[i] = temp->data;
    i = i   1;

    if (temp->right != NULL)
        sorterToArray(temp->right, pArray, i);
}

CodePudding user response：

The problem is indeed in the function you point to. The variable i is local to the function's execution context, and each recursive execution has thus its "own" i. The i = i 1 only affects one local instance, while other versions of i don't change. That means that none of those i variables will ever get the value 2 or more.

Otherwise put: i is passed by value to the recursive function call.

The solution is to have the function return the updated value of i to the caller:

int sorterToArray(struct treeNode* temp, int* pArray, int i) {
    if (temp->left != NULL)
        i = sorterToArray(temp->left, pArray, i);
    pArray[i] = temp->data;
    i = i   1;
    if (temp->right != NULL)
        i = sorterToArray(temp->right, pArray, i);
    return i;
}