Make a tree class.

Remember this week is just lazy deletion since the recursive parts are hard. Next week is balancing.

Oh yeah, can't count on everyone actually coming to class. To Dump means to put all of the data in the tree in the provided List in order. So that's left to right. Dump requires recursion, because it forks. Adding, removing, and searching are just loops. Big 3 are recursive, because they fork through the whole tree too.

No dupes in Add.

Main:

// TreeSetup.cpp : Defines the entry point for the console application.

//

#include "pch.h"

#include

#include

#include

#include "Tree.h"

using namespace std;

int main()

{

Tree tTreeOne;

tTreeOne.Insert(50);

tTreeOne.Insert(30);

tTreeOne.Insert(80);

tTreeOne.Insert(90);

tTreeOne.Insert(100);

tTreeOne.Insert(60);

tTreeOne.Insert(20);

tTreeOne.Insert(10);

tTreeOne.Insert(15);

tTreeOne.Insert(55);

tTreeOne.Insert(110);

tTreeOne.Insert(120);

// I bet drawing that out on paper first would help.

if (tTreeOne.Contains(15))

cout << "Check 1" << endl;

if (tTreeOne.Contains(50))

cout << "Check 2" << endl;

if (tTreeOne.Contains(60))

cout << "Check 3" << endl;

if (tTreeOne.Contains(110))

cout << "Check 4" << endl;

if (!tTreeOne.Contains(99))

cout << "Check 5" << endl;

Tree tTreeTwo(tTreeOne);

tTreeOne.Erase(90);

if (tTreeTwo.Contains(90))

cout << "Check 6" << endl;

Tree tTreeThree;

tTreeThree.Insert(999);

tTreeThree = tTreeOne;

tTreeOne.Erase(20);

if (tTreeThree.Contains(20))

cout << "Check 7" << endl;

if (!tTreeThree.Contains(999))

cout << "Check 8" << endl;

if (!tTreeOne.Contains(20))

cout << "Check 9" << endl;

tTreeOne.Insert(90);

if (tTreeOne.Contains(90))

cout << "Check 10" << endl;

std::list tOneFlattened;

tTreeOne.Dump(&tOneFlattened);

for (auto iter = tOneFlattened.begin(); iter != tOneFlattened.end(); ++iter)

cout << (*iter) << " ";

cout << endl;

return 0;

}

H file:

#pragma once

/*

Basic binary search tree with private node class and core contract functions.

Add and Remove and Contains must be done with loops, not recursion.

We won't be balancing trees until next week, so Remove can go ahead and just mark a node as "Dead".

That is, the node stays there so it can route numbers left and right, but it doesn't count as being in

the tree if you search for it.

And remember, only an algorithm that has to fork needs recursion. Any algorithm that follows one path is a loop.

*/

#include // Normally naughty to include in an include, but apparently the rule is you aren't allowed to forward declare stl.

template // T must respond to < operator

class Tree

{

struct TreeNode

{

T mData;

TreeNode *mLeft;

TreeNode *mRight;

bool mIsDead;

};

TreeNode *mHead;

public:

Tree()

{

// Think really hard before you just copy your list homework and make a node here. What should an empty tree look like?

// if node is dead, copy the dead node as well

}

Tree(const Tree &other) : Tree()

{

// Recursive

}

Tree & operator= (const Tree &other)

{

// Recursive

return *this;

}

~Tree()

{

// Recursive

// Anything you new, you must delete.

}

void Insert(const T &tWhat)

{

// Loop

}

void Erase(const T &tWhat)

{

// Loop

}

bool Contains(const T &tWhat)

{

// Loop

TreeNode *curr = mHead;

while (curr!= nullptr)

{

if (x == curr->data)

return true; // fix this, not correct (remember lazy deletion)

else if (x < curr->data)

curr = curr->left;

else

curr = curr->right;

}

return false;

}

void Dump(std::list *tLeftToRight)

{

// Recursive

//

}

};