Write a find function for BST

keithzhou (22)
Hi, I want to write a function find() for recursively for my BST
Can anybody tell me how can i implement it?
my code include two files

BST.h
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
 
//#include < iostream>

//using namespace std;

class BST_Node{
	public:
	int data;
	BST_Node *leftSide;
	BST_Node *rightSide;
	BST_Node(int j){
		data = j;
		leftSide = rightSide = NULL;
	}; 
};

class BST{
	public:
		BST()
		{
			bstRoot=NULL;
		}
		void show();
		bool insertR(int integer);
		bool insertI(int Integer);
	private:
		BST_Node *bstRoot;
		bool _insertR(int integer, BST_Node *&treeNode);
		void _show(BST_Node *treeNode);
		
};


BST.CPP
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 
#include<iostream>
#include "BST.h"
using namespace std;
bool BST::_insertR(int integer, BST_Node *&treeNode){
	if(treeNode ==NULL)
	{
		if((treeNode = new BST_Node(integer)) == NULL)
		{
			cout<<"no more space"<<endl;
				return false;
		}
		else return true;
	}
		
	if(treeNode->data = integer)
	{
		cout<<"Duplicated"<<integer<<endl;
		return false;
	}
	
	if(treeNode->data < integer)
	
		return _insertR(integer, treeNode->rightSide);
	else
		return _insertR(integer, treeNode->leftSide);

}
bool BST::insertR(int integer){
	return _insertR(integer, bstRoot);
}

bool BST::insertI(int integer){
	BST_Node *treeNode = bstRoot;
	BST_Node *nTreeNode = NULL;
	if(bstRoot == NULL)
	{
		bstRoot = new BST_Node(integer);
		return true;
	}
	while(true)
	{
		if(treeNode->data == integer)
		{
			cout<<"douplicate:"<<integer<<endl;
			return false;
		}
	if((nTreeNode = new BST_Node(integer)) == NULL)
	{
		cout<<"douplicate"<< integer<<endl;
		return false;
	}
	
	if(treeNode->data < integer)
	{
		if(treeNode ->rightSide == NULL)
		{
		treeNode-> rightSide = nTreeNode;
		return true;
		}
		else treeNode = treeNode->rightSide;
	}
	else
	{
			if(treeNode->leftSide == NULL)
			{
				treeNode->leftSide = nTreeNode;
				return true;
			}
			else treeNode = treeNode->leftSide;
		}	
	}
}

void BST::_show(BST_Node *treeNode){
	if (treeNode ->leftSide)
	_show(treeNode->leftSide);
	cout << treeNode->data << endl;
	if (treeNode ->rightSide)
	_show(treeNode->rightSide);
}

void BST::show(){
	if(bstRoot != NULL)
	_show(bstRoot);
}

int main() {
   BST t;
   t.show();
   t.insertI(23);
   t.insertI(15);
   t.insertI(12);
   t.insertR(4);
   t.insertI(34);
   t.insertI(12);
   t.insertR(1000);
   t.insertI(2);
   t.insertI(66);
   t.insertR(23);
   t.insertR(4);
   t.insertR(300);
   t.insertR(12);
   t.insertI(45);
   t.show();
   return 0;
}


thanks for helping me
Zhuge (4664)
Firstly, when using new, it doesn't return NULL when there is an out of memory error; it throws an exception.

As for your actual question, searching is actually very similar to inserting. Treat the data you are searching for as the data you are inserting, going left and right as applicable. If you reach a leaf without having found the data you are looking for, it isn't in the tree.
Topic archived. No new replies allowed.