Difficult to write a method that returns the parent Node

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 &gt)
{
	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 &gt)
{
	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
Topic archived. No new replies allowed.