<da*******@gmail.com> wrote in message

news:11**********************@g43g2000cwa.googlegr oups.com

Hi all,

I am trying to write a Binary Search Tree that each of its node will

have 3 node pointers: left, right and parent. I need a parent pointer

for some the purpose of my project. Without the pointer to the parent

node, the program will be inefficient and slow. It works fine at

first. However, when I started to build the remove function, it

destroys the tree when I delete a node. I already changed the parent

pointer whenever I delete a node, but still doesnt work correctly.

This is the tree node class:

/////////////////////////////////////////////////////////////

template <class Comparable>

class BinaryNode

{ //Binary Tree Node

Comparable element; //element

int frequency; //frequency

int height; //height

BinaryNode * left; //left child

BinaryNode * right; //right child

BinaryNode * parent; //parent

/* more functions here */

friend class BinarySearchTree<Comparable>;

};

//////////////////////////////////////////////////////////////

This is part of the remove function:

//////////////////////////////////////////////////////////////

/* more codes here */

BinaryNode<Comparable> *oldNode = t;

if (NULL != t->left)

{ //the node has a left subtree

t->left->parent = t->parent;

t = t->left;

}

else if (NULL != t->right)

{ //the node has a right subtree

t->right->parent = t->parent;

t = t->right;

}

Your code is too incomplete for me to really know what is going on. I am

guessing that t is a pointer stored in the parent of the node to be deleted

that points to the node that is to be deleted. I will refer to the parent of

the node to be deleted as the grandparent.

What if both t->left and t->right are non-zero? Because of the "else if"

form, you only hook up the left node to the grandparent and lose the right

node. Of course, hooking up both is going to be a problem if the grandparent

started out with two children, because you would be deleting one and adding

two, giving the grandparent three children.

else

{ //no children

}

delete oldNode;

/* more codes here */

//////////////////////////////////////////////////////////////

Can someone tell me how can I solve the problem of deletion? Or is it

possible? Thanks in advance...

--

John Carson