Why i can't delete a leaf from the binary tree

[honglao15]

Acturally, i am not really understand the whole program. I just want to delete a leaf from the Binary tree. But i can't. Can anyone help me?

with my understanding, in remove(), i find the node that i want to delete by find(n).Then i try to remove the found node, but i can't. T.T

There are some functions in my BinaryTree.h :

template<class T>
void BinaryTree<T>::remove( const T& n, TreeNode<T>* current ){
     find(n);
     if( current->leftChild == NULL && current->rightChild == NULL)
     delete current;
}

template<class T>
TreeNode<T>* BinaryTree<T>::find(const T& n)const{
     if (find(n, root) == NULL)
        cout << n <<" not found. \n";
     return find(n, root);
}

template <class T>
TreeNode<T> * BinaryTree<T>::find( const T & target, TreeNode<T> *current ) const
{
    while( current != NULL ){
        if( target < current->data )
            current = current->leftChild;
        else if( target > current->data )
            current = current->rightChild;
        else
            return current;    // Match
    }
    return NULL;   // No match
}

TreeNode.h

#ifndef TreeNode_H
#define TreeNode_H

template <class T> class BinaryTree;

template <class T>
class TreeNode {
   friend class BinaryTree<T>;
   public:
      TreeNode() {leftChild = rightChild = NULL;}
      TreeNode(const T& n)
            {data = n; leftChild = rightChild = NULL;}
      TreeNode(const T& n, TreeNode *l, TreeNode *r)
       {data = n; leftChild = l; rightChild = r;}
      const T& getData() const{ return data;}
   private:
      T data;
      TreeNode<T> *leftChild;  // left subtree
      TreeNode<T> *rightChild; // right subtree
};

#endif 

main.cpp

#include <cstdlib>
#include <iostream>
#include "BinaryTree.h"

using namespace std;

int main(int argc, char *argv[])
{
    BinaryTree<int> tree01; //a new tree
    tree01.insert( 15 ); //inserting data
    tree01.insert( 6 );
    tree01.insert( 18 ); 
    tree01.insert( 3 );
    tree01.insert( 7 );
    tree01.insert( 17 );
    tree01.insert( 20 );
    tree01.insert( 2 );
    tree01.insert( 4 );
    tree01.insert( 13 );
    tree01.insert( 9 );
    cout << "\nInorder: "; //print inorder
    tree01.printTreeInorder();
    cout << "\nPreorder: ";
    tree01.printTreePreorder();
    cout << "\nPostorder: ";
    tree01.printTreePostorder();
    cout<<endl;
    cout << "\nMin number: ";
    cout << tree01.findMin() << endl;
        cout << "\nMax number: ";
    cout << tree01.findMax() << endl;
    
    tree01.remove(10);

    system("PAUSE");
    return EXIT_SUCCESS;
}

If you want the whole program, please leave me e-mail address.

[mahlerfive]

To remove a leaf you cant just delete the leaf node, you must also remove the link from the parent to that leaf. In the case that there is only 1 node in the tree, removing the leaf is also removing the root, so this is also a special case. Instead of using find, your remove should be something similar to find at first, but you need to also keep track of the parent node as you go so you can delete the child link to the leaf.

[honglao15]

How can i find the parnet node
in fact, i am dummy in c++. What code i need?

[gen1mx6]

its like removing from a singly linked list, just keep track of where you came from except your going to need to know if your a left/right child

your find function is going to work for you as is you have two choices really,

modify the find functions to give you back additional information or just do the traversal inside the remove method itself keeping track of parent/ isleft or isright child

[kdenisk]

Removing a node from a BST is not so simple. As it were said, you should remove a link from the parent and, therefore, in find() you should track the parent. See more detailed description along with a source code here: http://simpleprogrammingtutorials.com/tutorials/bst-remove.php

[honglao15]

Thank you everybody!! ^.^
i will look about this.

[grey127]

You can just go to that leaf
1) take a previous and current pointer and then when you reach the leaf which will be the current at that time ,you can store its value ( if you need that one ).

2)Now point the previous to NULL so that now the node will be deleated ...

I hope this is the easiest way to do .....

[roodtree]

in C++ we can use the "free();"to remove the node you want do it.
+find the node you want delete;
+add the template val the remember that node;
+remove all the cornect tor to it. form his father node,
+if you want delete that node ,that must be the left(n) what is it???
uhm that is the node which has no the son node.
+then you can delete template val== node want be remove.
THAT RIGHT????????????

[Zaita]

@roodtree: Incorrect. Please don't post guesses.

free() is a C call to free memory allocated with malloc(). It shouldn't be used to de-allocate any other kind of memory.

delete is used to free memory allocated with the new keyword. This is typically a C++ memory allocation method used instead of malloc/free.