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 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222
|
"BST.H"
#ifndef BST_H
#define BST_H
#include <iostream>
#include <fstream>
#include <new>
#include "Person.h"
using namespace std;
class Node {
public:
Node* Right;
Node* Left;
int Value;
};
template<class ItemType>
class BinaryTree
{
public:
BinaryTree();
BinaryTree(char *Name);
~BinaryTree();
int GetCount();
bool Search(int Value);
void Insert(int Value); //function prototype with error
void Delete(int Value);
void Print();
Node getRoot();
private:
int Count(Node* Tree);
bool SearchNode(Node* Tree, int Value);
void InsertNode(Node * &Tree, int Value);
void PrintNodeInorder(Node * Tree);
void DestroyNode(Node * Tree); //for Destructor
Node *Root;
};
//void GetPredecessor(Node* tree, int& data);
//void DeleteNode(Node*& Tree);
//void DeleteNode(Node*& Tree, int value);
//-----------------------------------------------------------
// Constructor function.
//-----------------------------------------------------------
template<class ItemType>
BinaryTree<ItemType>::BinaryTree()
{
Root = NULL;
}
//-----------------------------------------------------------
// Constructor function that reads tree from file.
//-----------------------------------------------------------
template<class ItemType>
BinaryTree<ItemType>::BinaryTree(char *Name)
{
Root = NULL;
// Open input file
ifstream din;
din.open(Name);
if (din.fail())
cout << "Error: could not open input file\n";
// Read the data
int Value;
cin >> Value;
while (!din.eof())
{
InsertNode(Root, Value);
cin >> Value;
}
// Close the file
din.close();
}
//-----------------------------------------------------------
// Destructor function Node function.
//-----------------------------------------------------------
template<class ItemType>
void BinaryTree<ItemType>::DestroyNode(Node * Tree)
{
// Delete node and it's children
if (Tree != NULL)
{
DestroyNode(Tree->Left);
DestroyNode(Tree->Right);
delete Tree;
}
}
//-----------------------------------------------------------
// Destructor function.
//-----------------------------------------------------------
template<class ItemType>
BinaryTree<ItemType>::~BinaryTree()
{
// Call tree destroy function
DestroyNode(Root);
}
//-----------------------------------------------------------
// Search Node function.
//-----------------------------------------------------------
template<class ItemType>
bool BinaryTree<ItemType>::SearchNode(Node * Tree, int Value)
{
// Data value not found
if (Tree == NULL)
return false;
// Data value found
else if (Tree->Value == Value)
return true;
// Recursively search for data value
else if (Tree->Value > Value)
return (SearchNode(Tree->Left, Value));
else if (Tree->Value < Value)
return (SearchNode(Tree->Right, Value));
else
return false;
}
//-----------------------------------------------------------
// Search for data in the binary tree.
//-----------------------------------------------------------
template<class ItemType>
bool BinaryTree<ItemType>::Search(int Value)
{
// Call tree searching function
return (SearchNode(Root, Value));
}
//-----------------------------------------------------------
// Insert Node function.
//-----------------------------------------------------------
template<class ItemType>
void BinaryTree<ItemType>::InsertNode(Node * &Tree, int Value)
{
// Insert data into the tree
if (Tree == NULL)
{
Tree = new Node();
Tree->Value = Value;
Tree->Left = NULL;
Tree->Right = NULL;
//return true;
}
// Recursively search for insertion position
else if (Tree->Value > Value)
(InsertNode(Tree->Left, Value));
else
(InsertNode(Tree->Right, Value));
}
//-----------------------------------------------------------
// Insert data into the binary tree. this is is the function with the error
//-----------------------------------------------------------
template<class ItemType>
void BinaryTree<ItemType>::Insert(int Value)
{
// Call tree insertion function
InsertNode(Root, <Person>Value);
}
//-----------------------------------------------------------
// Print Node function. inorder
//-----------------------------------------------------------
template<class ItemType>
void BinaryTree<ItemType>::PrintNodeInorder(Node * Tree)
{
// Check terminating condition
if (Tree != NULL)
{
// Print left subtree
PrintNodeInorder(Tree->Left);
// Print node value
cout << " " << Tree->Value << " ";
// Print right subtree
PrintNodeInorder(Tree->Right);
}
}
//-----------------------------------------------------------
// Print all records in the binary tree.
//-----------------------------------------------------------
template<class ItemType>
void BinaryTree<ItemType>::Print()
{
// Call tree printing function
cout << "Inorder: ";
PrintNodeInorder(Root);
cout << endl;
}
template<class ItemType>
Node BinaryTree<ItemType>::getRoot()
{
return Root;
}
template<class ItemType>
void BinaryTree<ItemType>::Delete(int value)
{
DeleteNode(Root, value);
}
#endif
|