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

#include "stdafx.h"

#include <iostream>
#include <iomanip>
using namespace std;

#include "llist.h"

template <class T>
class TNode {
public:
	T key;
	TNode<T>* left;
	TNode<T>* right;
	TNode(TNode<T>* l = NULL, TNode<T>* r = NULL) : left(l), right(l) {}
	TNode(T data, TNode<T>* l = NULL, TNode<T>* r = NULL) : key(data), left(l), right(l) {}
};

template <class T>
class Tree {
	TNode<T>* root;
public:

	Tree() : root(NULL) {
		// cout << "default constructor\n";
	}

	Tree(T key, TNode<T>* l = NULL, TNode<T>* r = NULL) : root(NULL) {
		// cout << "node counstrcutr\n";
		root = new TNode<T>();
		root -> key = key;
		CopyNode(root -> left, l);
		CopyNode(root -> right, r);
	}

	Tree(T key, Tree<T> &l, Tree<T> &r) : root(NULL) {
		// cout << "tree counstrcutr\n";
		root = new TNode<T>();
		root -> key = key;
		CopyNode(root -> left, l.root);
		CopyNode(root -> right, r.root);
	}

	Tree(T key, Tree<T>* l, Tree<T>* r) : root(NULL) {
		// cout << "tree counstrcutr\n";
		root = new TNode<T>();
		root -> key = key;
		if (l != NULL) CopyNode(root -> left, l -> root);
		if (r != NULL) CopyNode(root -> right, r -> root);
	}

	Tree(const Tree<T>& obj) : root(NULL) {
		// cout << "copy constructor\n";
		CopyTree(obj);
	}

	~Tree() {
		// cout << "destructor\n";
		DeleteTree();
	}

	Tree<T>& operator= (const Tree<T>& obj) {
		//cout << "operator=\n";
		if (this != &obj) {
			DeleteTree();
			CopyTree(obj);
		}
		return *this;
	}

	void CopyNode(TNode<T>* &dest, const TNode<T>* src) {
		dest = NULL;
		if (src != NULL) {
			dest = new TNode<T>();
			dest -> key = src -> key;
			CopyNode(dest -> left, src -> left);
			CopyNode(dest -> right, src -> right);
		}
	}

	Tree<T>& CopyTree(const Tree<T> &obj) {
		CopyNode(root, obj.root);
		return *this;
	}

	void DeleteNode(TNode<T>* &p) {
		if (p != NULL) {
			// cout << "done: " << p -> key << endl;
			DeleteNode(p -> left);
			DeleteNode(p -> right);
			delete p;
			p = NULL;
		}
	}

	void DeleteTree() {
		DeleteNode(root);
	}

	bool isEmpty() { 
		return root == NULL; 
	}

	T Root() { 
		return root -> key; 
	}

	TNode<T>* RootPtr() {
		return root; 
	}

	Tree LeftTree() {
		Tree<T> t;
		CopyNode(t.root, root -> left);
		return t;
	}

	Tree RightTree() {
		Tree<T> t;
		CopyNode(t.root, root -> right);
		return t;
	}

	void PrintNode(TNode<T>* n, int h = 0) {
		if (n == NULL) return;
		PrintNode(n -> right, h + 1);
		cout << setw(h*8) << n -> key << endl;
		PrintNode(n -> left, h + 1);
	}

	void Print() {
		PrintNode(root);
	}

	TNode<T>* MemberNode(TNode<T>* p, T key) {

		if (p != NULL) {

			if (p -> key == key) return p;
			
			TNode<T>* r = MemberNode(p -> left, key);
			if (r != NULL) return r;

			r = MemberNode(p -> right, key);
			if (r != NULL) return r;

			return NULL;

		}

		return p;
	}

	bool Member(T key) {

		TNode<T> *p = MemberNode(root, key);
		return (p != NULL);

	}

};


typedef Tree<int> IntTree;
typedef TNode<int> IntNode;

/* int main(int argc, char* argv[])
{
	IntTree z;
	IntTree t(15, 
				new IntTree(61, 
				               new IntTree(60), new IntTree(3)), 
				new IntTree(7, new IntTree(6), 
				               new IntTree(-51, NULL, new IntTree(6))));
	t.Print();

	return 0;
} */

