TapestryEngine

A 2D Platformer Game Engine
Log | Files | Refs

8e10c473bb8ff23a3d5d8dd5de00b7c6ecaeaac4.svn-base (1949B)

      1 #ifndef BINARY_TREE_H
      2 #define BINARY_TREE_H
      3 
      4 #define NULL 0
      5 
      6 
      7 class Node
      8 {
      9 public:
     10 
     11 	Node() : mParent(NULL), mLeft(NULL), mRight(NULL), mColor(RED)
     12 	{}
     13 
     14 	Node(Node* parent, int item, void* data) : mItem(item), mData(data), mParent(parent), mLeft(NULL), mRight(NULL), mColor(RED)
     15 	{}
     16 
     17 	Node(int item, void* data) : mItem(item), mData(data), mParent(NULL), mLeft(NULL), mRight(NULL), mColor(BLACK) //Used to create debugging root node w/test data
     18 	{}
     19 
     20 	bool Insert(int i, void* data);
     21 	
     22 	Node* Search(int i);
     23 
     24 	int Size(int i = 0);
     25 
     26 	Node** Dump(int index = 0, Node** contents = 0); //Should always be called with no arguments, arguements only used for recursion.
     27 
     28 	bool InsertNode(Node* n);
     29 
     30 	bool InsertNodeAtRoot(Node* n);
     31 
     32 	void Delete();
     33 
     34 	void rotate_left();
     35 	void rotate_right();
     36 
     37 	int GetItem()
     38 	{
     39 		return mItem;
     40 	}
     41 
     42 	void* GetData()
     43 	{
     44 		return mData;
     45 	}
     46 
     47 	void AttachLeft(Node* n)
     48 	{
     49 		n->mParent = this;
     50 		mLeft = n;
     51 	}
     52 
     53 	void AttachRight(Node* n)
     54 	{
     55 		n->mParent = this;
     56 		mRight = n;
     57 	}
     58 
     59 	void SwapColor()
     60 	{
     61 		if (mColor == RED) { mColor = BLACK; }
     62 		else               { mColor = RED; }
     63 	}
     64 
     65 	Node* mParent;
     66 	Node* mLeft;
     67 	Node* mRight;
     68 
     69 protected:
     70 
     71 	enum { RED, BLACK } mColor;
     72 
     73 	int mItem;
     74 
     75 	void* mData;
     76 };
     77 
     78 
     79 class BinaryTree
     80 {
     81 public:
     82 
     83 	BinaryTree() : mRoot(NULL)
     84 	{
     85 	}
     86 
     87 	BinaryTree(Node* Root) : mRoot(Root)
     88 	{
     89 	}
     90 
     91 	bool Insert(int i, void* data)
     92 	{
     93 		if (mRoot != NULL)
     94 		{
     95 			return mRoot->Insert(i, data);
     96 		}
     97 		else //mRoot == NULL -> Tree is empty
     98 		{
     99 			mRoot = new Node(i, data);
    100 			return true;
    101 		}
    102 	}
    103 
    104 	Node* Search(int i)
    105 	{
    106 		if (mRoot != NULL)
    107 		{
    108 			return mRoot->Search(i);
    109 		}
    110 		return NULL;
    111 	}
    112 
    113 	int Size(int i = 0)
    114 	{
    115 		if (mRoot != NULL)
    116 		{
    117 			return mRoot->Size(i);
    118 		}
    119 		return -1;
    120 	}
    121 
    122 	Node** Dump(int index = 0, Node** contents = 0)
    123 	{
    124 		if (mRoot != NULL)
    125 		{
    126 			return mRoot->Dump(index, contents);
    127 		}
    128 		return NULL;
    129 	}
    130 
    131 	void Delete()
    132 	{
    133 		return mRoot->Delete();
    134 	}
    135 
    136 
    137 protected:
    138 
    139 	Node* mRoot;
    140 };
    141 #endif