#include "Tree.h"

Tree :: Tree()

{

Root = NULL;

}

Tree :: ~Tree()

{

DeleteCompleteTree(Root);

}

void Tree :: Insert(DateType Val)

{

InsertTree(Root, Val);

}

// Qustion #13.(ii):

// The parameter SubtreeRoot in the following member function

// is a reference parameter. If we change it

// to a value parameter by using the prototype

// void Tree :: InsertTree(TreeNode * SubtreeRoot, DateType Val)

// in the Tree.h header file and also in the following

// implementation, is it still able to correctly insert

// Val? What would happen in this situation when you have an empty tree

// object T you try to use T.Insert(Val) to insert Val into the tree?

// Why?

void Tree :: InsertTree(TreeNode * & SubtreeRoot, DateType Val)

{

if (SubtreeRoot==NULL)

{

SubtreeRoot= new TreeNode;

SubtreeRoot->Left=NULL;

SubtreeRoot->Right=NULL;

SubtreeRoot->Value = Val;

return;

}

// handle duplicate

if (Val == SubtreeRoot->Value)

return;

//search Left

if (Val < SubtreeRoot->Value)

InsertTree(SubtreeRoot->Left, Val);

//search Right

else

InsertTree(SubtreeRoot->Right,Val);

}

void Tree::Display()

{

DisplayTree(Root);

cout << endl;

}

void Tree :: DisplayTree(TreeNode * SubtreeRoot)

{

if (SubtreeRoot != NULL)

{

DisplayTree(SubtreeRoot->Left);

cout<<SubtreeRoot->Value<<' ';

DisplayTree(SubtreeRoot->Right);

}

}

bool Tree:: Search(DateType Val)

{

return SearchTree(Root, Val);

}

// Qustion #13.(iii):

// The parameter SubtreeRoot in the following member function

// is a value parameter. If we change it

// to a reference parameter by using the prototype

// void Tree :: InsertTree(TreeNode * & SubtreeRoot, DateType Val)

// in the Tree.h header file and also in the following

// implementation, is it still able to correctly search

// for Val into the tree? Why or why not?

bool Tree:: SearchTree(TreeNode * SubtreeRoot, DateType Val)

{

if (SubtreeRoot == NULL)

return false;

if (SubtreeRoot->Value == Val)

return true;

if (Val < SubtreeRoot->Value)

return SearchTree(SubtreeRoot->Left, Val);

return SearchTree(SubtreeRoot->Right, Val);

}

// Qustion #13.(iv):

// Does it still work if change the implementation of

// void Tree :: DeleteCompleteTree(TreeNode * SubtreeRoot)

// and move

// delete SubtreeRoot;

// two lines up right before

// DeleteCompleteTree(SubtreeRoot->Left);

// ? Why or why not?

void Tree :: DeleteCompleteTree(TreeNode * SubtreeRoot)

{

if (SubtreeRoot != NULL)

{

DeleteCompleteTree(SubtreeRoot->Left);

DeleteCompleteTree(SubtreeRoot->Right);

delete SubtreeRoot;

}

}

//************************************************************

// The following are three global functions as additional Code

// used to support the deletion of a node from a tree

// Not in the book

//***************************************************

bool Tree::GetPredecessor(TreeNode * SubtreeRoot, DateType & data)

// Find the predecessor of the root node in SubtreeRoot.

// If there is one, return true and store the predecessor data in data

//Otherwise, return false.

{

if (SubtreeRoot == NULL || (SubtreeRoot->Left) == NULL)

return false;

TreeNode * temp = SubtreeRoot->Left;

while (temp->Right != NULL)

temp = temp->Right;

data = temp->Value;

return true;

}

void Tree::Delete(TreeNode *& SubtreeRoot, DateType item)

// Deletes item from tree.

// Post: item is not in tree rooted at SubtreeRoot.

{

if (SubtreeRoot == NULL)

return;

if (item < SubtreeRoot->Value)

Delete(SubtreeRoot->Left, item); // Look in Left subtree.

else if (item > SubtreeRoot->Value)

Delete(SubtreeRoot->Right, item); // Look in Right subtree.

else

DeleteNode(SubtreeRoot); // Node found; call DeleteNode.

}

void Tree::DeleteNode(TreeNode * & SubtreeRoot)

// Deletes the node pointed to by SubtreeRoot.

{

if (SubtreeRoot == NULL)

return;

//cout << "To delete " << tree->Value << endl;

if (SubtreeRoot->Left != NULL && SubtreeRoot->Right != NULL)

{ DateType data;

GetPredecessor(SubtreeRoot, data);

SubtreeRoot->Value = data;

Delete(SubtreeRoot->Left, data); // Delete predecessor node.

}

else

{

TreeNode * tempPtr;

tempPtr = SubtreeRoot;

if (SubtreeRoot->Left == NULL)

SubtreeRoot = SubtreeRoot->Right;

else if (SubtreeRoot->Right == NULL)

SubtreeRoot = SubtreeRoot->Left;

delete tempPtr;

}

}

//*****************************************************************

// The following is an additional member function of the Tree class.

// It directly or indirectly uses the three functions above to

// delete an item from the tree.

// Not in the book

//***************************************************

void Tree::DeleteItem(DateType item)

// Calls recursive function Delete to delete item from tree.

{

Delete(Root, item);

}