CODEWITHSUNDEEP
cbinary-tree
jujik
jujik

Reputation: 1

Deleting from a binary tree

I have a problem with a binary tree. In my code i'm planing to implement functions like adding, deleting and printing. While Adding and printing works fine, im having troubles with deleting. My thoughts - problem is in pointers. I'm adding through 2 pointers and deleting with 1, but i cant figure out how to get it to work. Please help.

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

#include "bintree.h"

void paste_node(Tree ** tr, int x)
{
    Tree *tree_bin;
    if ((*tr) == NULL) {
        tree_bin = (Tree *) malloc(sizeof(Tree));
        tree_bin->item = x;
        tree_bin->lchild = tree_bin->rchild = NULL;
        *tr = tree_bin;
        return;
    }

    if (x < (*tr)->item) {
        paste_node(&((*tr)->lchild), x);
    } else {
        paste_node(&((*tr)->rchild), x);
    }
}

Tree * minimum(Tree *tr)
{
    if (tr->lchild == NULL) return tr;
    return minimum(tr->lchild);
}

void delete_node(Tree ** tr, int num)
{ 
    if (tr == NULL) return;

    if (num < tr->item)
        tr->lchild = delete_node(tr->lchild, num);
    else if (num > tr->item)
        tr->rchild = delete_node(tr->rchild, num);
    else {
        if (tr->lchild == NULL) {
            Tree *tree_bin = tr->rchild;
            free(tr);
            return;
        }
        else if (tr->rchild == NULL) {
            Tree *tree_bin = tr->lchild;
            free(tr);
            return;
        }

        Tree *tree_bin = minimum(tr->rchild);
        tr->item = tree_bin->item;
        tr->rchild = delete_node(tr->rchild, tree_bin->item);
    }

    return;
}

void print_tree(Tree *tr, int depth)
{
    if (tr != NULL) {
        print_tree(tr->lchild, depth + 1);
        for(int i = 0; i < depth; ++i) printf("   ");
        printf("%d<\n", tr->item);
        print_tree(tr->rchild, depth + 1);
    }
}

int check_node(Tree **tr, int x) {
    if ((*tr) == NULL) {
        return 1;
    }

    if (x < (*tr)->item) {
        check_node(&((*tr)->lchild), x);
    } else if (x == (*tr)->item) {
        return -1;
    } else {
        check_node(&((*tr)->rchild), x);
    }
}

Upvotes: 0

Views: 78

Answers (1)

Malcolm McLean
Malcolm McLean

Reputation: 6404

You can't simply delete a node of a binary tree. You can delete a leaf easily enough, just set the parent's lchild or rchild partner to null. But you can't delete an internal node without also deleting all its children. What you can do is rotate the node so that the left child (or right child) becomes the root of the sub-tree, and the root becomes a child. The reattach the new sub-tree root to the tree. Repeat until finally the node you wish to delete becomes a leaf, and remove it.

Upvotes: 4

Related Questions