Problem With deleting Node in Trees
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: Problem With deleting Node in Trees

  1. #1
    Join Date
    Jun 2013
    Location
    Langrood, Iran
    Posts
    7

    Problem With deleting Node in Trees

    I have Problems with deleting node in trees!my first problem is I don't understand the algorithm of deleting a node with two child! I write some kind of code that delete a node with two child but I think (maybe I should say I am sure ) that it has runtime or logical errors or something like that!
    my second problem is my code doesn't work if my node is root of tree!because I don't know if it is root what should be the parentPtr in my code! I set parentPtr to NULL in this situation but I know it is wrong!
    help me plz! Here is my Code :

    Code:
    #include <iostream>
    #include "TreeNode.h"
    using namespace std;
    
    template<typename NODETYPE> class Tree
    {
    public:
    	Tree();
    	void insertNode(const NODETYPE &);
    	bool removeNode(const NODETYPE &);
    	void preOrderTraversal() const;
    	void inOrderTraversal() const;
    	void postOrderTraversal() const;
    	void printTree() const;
    	int depth() const;
    	TreeNode<NODETYPE> *searchBinaryTree(const NODETYPE &) const;
    
    private:
    	TreeNode< NODETYPE > *rootPtr;
    
    	void insertNodeHelper( TreeNode< NODETYPE > **, const NODETYPE & );
    	void preOrderHelper( TreeNode< NODETYPE > * ) const;
    	void inOrderHelper( TreeNode< NODETYPE > * ) const;
    	void postOrderHelper( TreeNode< NODETYPE > * ) const;
    	void printTreeHelper(TreeNode<NODETYPE> *, int) const;
    	int depthHelper(TreeNode< NODETYPE > *) const;
    	bool isLeaf(const TreeNode<NODETYPE> *) const;
    	TreeNode<NODETYPE> *findParent(TreeNode<NODETYPE> *);
    };
    
    template<typename NODETYPE>
    TreeNode<NODETYPE> *Tree<NODETYPE>::searchBinaryTree(const NODETYPE &value) const
    {
    	TreeNode<NODETYPE> *currentPtr = rootPtr;
    
    	while(currentPtr != 0)
    	{
    		if(value > currentPtr->data)
    			currentPtr = currentPtr->rightPtr;
    
    		else if(value < currentPtr->data)
    			currentPtr = currentPtr->leftPtr;
    
    		else
    			return currentPtr;
    	}
    
    	return 0;
    }
    
    
    template<typename NODETYPE>
    bool Tree<NODETYPE>::isLeaf(const TreeNode<NODETYPE> *ptr) const
    {
    	return(ptr->leftPtr == 0 && ptr->rightPtr == 0);
    }
    
    template<typename NODETYPE>
    bool Tree<NODETYPE>::removeNode(const NODETYPE &value) 
    {
    	TreeNode<NODETYPE> *tempPtr = searchBinaryTree(value); 
    	TreeNode<NODETYPE> *parentPtr = findParent(tempPtr);
    
    	if(tempPtr == 0)
    		return false;
    
    	if(isLeaf(tempPtr))
    	{
    		if(parentPtr->leftPtr == tempPtr)
    			parentPtr->leftPtr = 0;
    
    		else if(parentPtr->rightPtr == tempPtr)
    			parentPtr->rightPtr = 0;
    
    		delete tempPtr;
    	}
    
    	else if(tempPtr->leftPtr == 0 || tempPtr->rightPtr == 0)
    	{
    		if(tempPtr->leftPtr != 0)
    		{
    			if(parentPtr->rightPtr == tempPtr)
    				parentPtr->rightPtr = tempPtr->leftPtr;
    
    			else if(parentPtr->leftPtr == tempPtr)
    				parentPtr->leftPtr = tempPtr->leftPtr;
    
    			delete tempPtr;
    		}
    
    		else if(tempPtr->rightPtr != 0)
    		{
    			if(parentPtr->rightPtr == tempPtr)
    				parentPtr->rightPtr = tempPtr->rightPtr;
    
    			else if(parentPtr->leftPtr == tempPtr)
    				parentPtr->leftPtr = tempPtr->rightPtr;
    
    			delete tempPtr;
    		}
    	}
    
    	else
    	{
    		TreeNode<NODETYPE> *replacementNodePtr = tempPtr->leftPtr;
    
    		while(replacementNodePtr->rightPtr != 0)
    			replacementNodePtr = replacementNodePtr->rightPtr;
    
    		TreeNode<NODETYPE> *replacementNodeParentPtr = findParent(replacementNodePtr);
    
    		if(parentPtr->leftPtr == tempPtr)
    			parentPtr->leftPtr = replacementNodePtr;
    
    		else if(parentPtr->rightPtr == tempPtr)
    			parentPtr->rightPtr = replacementNodePtr;
    
    		if(replacementNodeParentPtr->rightPtr == replacementNodePtr)
    				replacementNodeParentPtr->rightPtr = 0;
    
    		else if(replacementNodeParentPtr->leftPtr == replacementNodePtr)
    				replacementNodeParentPtr->leftPtr = 0;
    
    		replacementNodePtr->rightPtr = tempPtr->rightPtr;
    		delete tempPtr;
    	}
    
    }
    
    
    template<typename NODETYPE>
    TreeNode<NODETYPE> *Tree<NODETYPE>::findParent(TreeNode<NODETYPE> *ptr)
    {
    	if(rootPtr == ptr)
    		return 0;
    
    	TreeNode<NODETYPE> *parent = rootPtr;
    
    	while(parent != 0)
    	{
    		if(parent->leftPtr == ptr || parent->rightPtr == ptr)
    			return parent;
    
    		else
    		{
    			if(parent->data  < ptr->data)
    				parent = parent->rightPtr;
    
    			else 
    				parent = parent->leftPtr;
    		}
    	}
    }
    
    #endif //TREE_H

  2. #2
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,336

    Re: Problem With deleting Node in Trees

    my first problem is I don't understand the algorithm of deleting a node with two child!
    Have a look at these
    http://webdocs.cs.ualberta.ca/~holte...-from-bst.html
    http://faculty.winthrop.edu/dannelly...ree_delete.htm
    http://www.algolist.net/Data_structu...h_tree/Removal
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  3. #3
    Join Date
    Apr 1999
    Posts
    27,427

    Re: Problem With deleting Node in Trees

    Quote Originally Posted by N@R!MAN View Post
    I have Problems with deleting node in trees!my first problem is I don't understand the algorithm of deleting a node with two child!
    If you didn't understand the algorithm, why did you write the code? You're supposed to understand fully what you are supposed to do before writing the code.
    I write some kind of code that delete a node with two child but I think (maybe I should say I am sure ) that it has runtime or logical errors or something like that!
    Of course it will crash.

    Never write code that uses pointers, and not understand fully what you are coding. Otherwise you are almost guaranteed that the code will not work correctly!
    my second problem is my code doesn't work if my node is root of tree!because I don't know if it is root what should be the parentPtr in my code!
    Same thing here.

    Before writing any code, use pencil and paper to design exactly what you need to do.

    Regards,

    Paul McKenzie

  4. #4
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,336

    Re: Problem With deleting Node in Trees

    Unless you need to write a node deletion routine for an assignemnt etc, one other approach is for each node to have a 'delete' flag which is normally clear and is set when the node key is 'deleted'. Search and print routines then ignore nodes that are 'flagged for deletion' and insert routines ignore the flag unless inserting the same key when the flag is simply cleared.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center