ABB: Values are not printed when traversing it

Question

ABB: Values are not printed when traversing it

Navigation

#1 by (2 votes)

0

I have this implementation of a binary search tree in C; I have to do 3 routes in it: preorder, inbound and bidder. The problem is that I do not print anything and the code has no errors, I guess what is wrong is my logic, but I can not find the fault:

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

typedef struct t_tree{
    int value;
    t_tree* leftChild;
    t_tree* rightChild;
} BinarySearchTree;

void insert(BinarySearchTree* root, int x){
    if(root == NULL){
        root = (BinarySearchTree*) malloc(sizeof(BinarySearchTree));
        root->value = x;
        root->leftChild = NULL;
        root->rightChild = NULL;
    } else {
        if(root->value == x){
            printf("\n\tEse valor ya existe en el arbol");
            return;
        }
        if(x < root->value)
            insert(root->leftChild, x);
        else
            insert(root->rightChild, x);
    }
}

BinarySearchTree* search(BinarySearchTree* root, int x){
    if(root == NULL){
        printf("\n\tEl elemento no existe");
        return NULL;
    } else {
        if(root->value == x){
            printf("\n\tEl valor si existe");
            return root;
        }
        if(x < root->value)
            search(root->leftChild, x);
        else
            search(root->rightChild, x);
    }
}

void update(BinarySearchTree* root, int x, int newValue){
    BinarySearchTree* theChosenOne = search(root, x);
    if(theChosenOne != NULL)
        theChosenOne->value = newValue;
}

void remove(BinarySearchTree* root, int x){
    BinarySearchTree* theChosenOne = search(root, x);
    if(theChosenOne != NULL){
        if(theChosenOne->leftChild==NULL && theChosenOne->rightChild==NULL)
            free(theChosenOne);
        else {
            BinarySearchTree* explorer;
            if(theChosenOne->leftChild){
                explorer = theChosenOne->leftChild;
                while(explorer->rightChild)
                    explorer = explorer->rightChild;
                theChosenOne->value = explorer->value;
                free(explorer);
            } else if(theChosenOne->rightChild){
                explorer = theChosenOne->rightChild;
                while(explorer->leftChild)
                    explorer = explorer->leftChild;
                theChosenOne->value = explorer->value;
                free(explorer);
            }
        }
    }
}

void preOrder(BinarySearchTree* root){
    if(root == NULL)
        return;
    printf("%d ", root->value);
    preOrder(root->leftChild);
    preOrder(root->rightChild);
}

void inOrder(BinarySearchTree* root){
    if(root == NULL)
        return;
    inOrder(root->leftChild);
    printf("%d ", root->value);
    inOrder(root->rightChild);
}

void postOrder(BinarySearchTree* root){
    if(root == NULL)
        return;
    postOrder(root->leftChild);
    postOrder(root->rightChild);
    printf("%d ", root->value);
}

int main(){
    BinarySearchTree* ROOT = NULL;
    insert(ROOT, 5);
    insert(ROOT, 1);
    insert(ROOT, 9);
    insert(ROOT, 1);
    insert(ROOT, 8);
    insert(ROOT, 50);
    printf("\nRecorrido en pre-orden: ");
    preOrder(ROOT);
    printf("\nRecorrido en in-orden: ");
    inOrder(ROOT);
    printf("\nRecorrido en post-orden: ");
    postOrder(ROOT);
    free(ROOT);
    return 0;
}

c algoritmos

asked by Christopher Bryan 19.02.2018 в 05:52

source

1 answer

get the last value of a jtable no matter how many rows have java ForEach javascript

score 2 · Answer 1

The insert function has some errors that prevent the tree from being filled in.

The first thing that strikes the attention of the function is that it receives a simple pointer to the root node and that it does not return anything.

Why is this significant?

Because when calling insert , the function receives a copy of the pointer to root . Using a copy makes certain changes local to the function itself. It looks easier without pointers:

void func(int var)
{
  var = 10;
  printf("var=%d\n",var);
}

int main()
{
  var = 0;
  printf("var=%d\n",var);
  func(var);
  printf("var=%d\n",var);
}

How could it be otherwise, the result of the program is as follows:

var=0
var=10
var=0

That is, the change that has been made within the function is a local change ... and with the pointers the same thing happens:

void func(int *var)
{
  *var = 10;
  var = (int*)1234;
}

int main()
{
  int* var = (int*)calloc(1,sizeof(int));
  printf("var=%d, &var=%x\n",*var,var);
  func(var);
  printf("var=%d, &var=%x\n",*var,var);
}

If you execute the previous program, you will see that while the 10 if it is a persistent change, the value 1234 has been lost. This happens because you are modifying the copy of the pointer instead of the memory region shared by both pointers.

Well, the same thing is happening in your function:

void insert(BinarySearchTree* root, int x){
    if(root == NULL){
        root = (BinarySearchTree*) malloc(sizeof(BinarySearchTree)); // <<--- AQUI!!!
        root->value = x;
        root->leftChild = NULL;
        root->rightChild = NULL;
    } else {
      // ...
    }
}

The consequence is that the function is unable to add elements to the tree ... or at least it can not do so in such a way that the change survives the function.

Solutions?

Perhaps the simplest thing to implement, given your code, is to modify the function so that it supports double pointers. This way the function can modify the pointers happily:

void insert(BinarySearchTree** root, int x){
    if(*root == NULL){
        *root = (BinarySearchTree*) malloc(sizeof(BinarySearchTree));
        *root->value = x;
        *root->leftChild = NULL;
        *root->rightChild = NULL;
    } else {
        if(*root->value == x){
            printf("\n\tEse valor ya existe en el arbol");
            return;
        }
        if(x < *root->value)
            insert(&root->leftChild, x);
        else
            insert(&root->rightChild, x);
    }
}

And, since we have modified the input of the function, we must remember to also modify the calls to it:

insert(&ROOT, 5);