Hello! My algorithm does not work for n>7 and I don't know why-CodePudding

I built a perfectly balaced tree using BUILD_TREE and printed it inOrder and using a PRETTY_PRINT. The keys for my tree are in a sorted array named arr and I use n as the number of keys. If I give n a value bigger that 7 it does not print anything and I don't understand why. I need it to work for n=11.

#include <stdio.h>
#include <stdlib.h>     
#define NR_SPATII 7
#define MAX_SIZE 20
using namespace std;

typedef struct Tree {
    int key;
    struct Tree* left;
    struct Tree* right;
    int size;
}Tree;

Tree* createNewNode(int givenkey)
{
    Tree* node = (Tree*)malloc(sizeof(Tree));
    node->key = givenkey;
    node->left = NULL;
    node->right = NULL;
    node->size = NULL;
    return node;
}

Tree* BUILD_TREE(int arr[], int low, int high)
{
    int s = 1;
    if (low > high)
        return NULL;

    int mid = (low   high) / 2;
    Tree* node = createNewNode(mid);
    node->left = BUILD_TREE(arr, low, mid - 1);
    node->right = BUILD_TREE(arr, mid   1, high);

    if (low == high)
        node->size = 1;
    else node->size = node->left->size   node->right->size   1;

    return node;
}

void PRETTY_PRINT(Tree* root, int nivel)
{
    if (root == NULL)
        return;
    nivel  = NR_SPATII; //crestem distanta intre nivele
    PRETTY_PRINT(root->right, nivel);//procesam copilul drept
    printf("\n");
    for (int i = NR_SPATII; i < nivel; i  )
        printf(" ");
    printf("%d,%d\n", root->key, root->size);//scriem nodul dupa spatiu
    PRETTY_PRINT(root->left, nivel);
}

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

void demo()
{
    int n = 7;
    int arr[MAX_SIZE];
    for (int i = 1; i <= n; i  )
        arr[i] = i;

    Tree* root = (Tree*)malloc(sizeof(Tree));
    root = BUILD_TREE(arr, 1, n);
    printf("AFISARE INORDINE:\n");
    inOrder(root);
    printf("\nAFISARE PRETTY PRINT:");
    PRETTY_PRINT(root, 0);
}

int main()
{
    demo();

    return 0;
}

CodePudding user response：

Running your program in a debugger should instantly identify the problem as this line in BUILD_TREE:

else node->size = node->left->size   node->right->size   1;

The issue is that the left or right pointers can be NULL. If they are, you will most likely crash. Dereferencing a NULL pointer and reading (or writing) to that memory is undefined behavior.

You can replace this:

if (low == high)
    node->size = 1;
else node->size = node->left->size   node->right->size   1;

With this:

node->size = 1
      (node->left ? node->left->size : 0)
      (node->right ? node->right->size : 0);

That means if a subtree is NULL, it will be considered to have size zero, and crucially you will not dereference that pointer.

Alternatively you can define a function that returns a tree size and handles NULL-testing internally:

int TreeSize(const Tree* tree)
{
    return tree ? tree->size : 0;
}

Then your calculation becomes a bit neater:

node->size = 1   TreeSize(node->left)   TreeSize(node->right);