Difficult to write a method that returns the parent Node
Mar 10, 2013 at 3:17am UTC
Hi everyone, I have written a small program on "binary search tree".But I'm having difficulty in writing a method that returns the parent node.This method because when I delete a node has a child node, then we need to find the parent node.Hope you help.Thanks you!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
#ifndef BST_H
#define BST_H
#include <iostream>
using namespace std;
template <class T>
struct Node
{
T data;
Node *left;
Node *right;
};
template <class T>
class BST
{
private :
Node<T> *root;
public :
//Constructor
BST();
//Check Empty Tree
bool isEmpty()const ;
//Insert a Node
void InsertNode(const T &);
//return Parent Node
Node<T> *returnParentNode(T const &);
};
template <class T>
BST<T>::BST()
{
root = NULL;
}
//
template <class T>
bool BST<T>::isEmpty()const
{
return root == NULL;
}
//
template <class T>
void BST<T>::InsertNode(const T >)
{
Node<T> *newNode = new Node<T>;
newNode->data = gt;
newNode->left = NULL;
newNode->right = NULL;
if (isEmpty())
{
root = newNode;
return ;
}
else
{
//begin from root
Node<T> *curr = root;
Node<T> *parent;
while (curr!=NULL)
{
parent = curr;
if (curr->data > newNode->data)
curr = curr->left;
else
curr = curr->right;
}
if (parent->data > newNode->data)
parent->left = newNode;
else
parent->right= newNode;
}
}
//method find parent Node
template <class T>
Node<T> *BST<T>::returnParentNode(const T >)
{
Node<T> *tmp = root;
Node<T> *parent;
while (tmp != NULL && tmp->data != gt)
{
parent = tmp;
if (tmp->data > gt)
tmp = tmp->left; // move left
else if (tmp->data <gt)
tmp = tmp->right; // move right
}
if (parent->left->data == gt || parent->right->data == gt)
return parent;
}
#endif
Last edited on Mar 10, 2013 at 3:19am UTC
Topic archived. No new replies allowed.