enum
{
pageSize = 125,
minItems = pageSize - 2 // minimal number of items in internal node
};
enum TraverseOrder
{
PreOrder,
InOrder,
PostOrder,
LevelOrder
};
typedef int ElementData;
typedef int ElementType;
typedef struct tagTTREENODE
{
tagTTREENODE *left; // Left child pointer.
tagTTREENODE *right; // Right child pointer.
unsigned short int nItems; // Internal node items.
ElementType item[pageSize]; // Item key array.
ElementData data[pageSize]; // Item data array.
char bf; // Balabce factor(bf = right subtree height - left subtree height)
} TTREENODE, *LPTTREENODE, *PTTREENODE;
class CTtree
{
public:
// Constructor.
CTtree();
// Destructor.
virtual ~CTtree();
public:
// Insert key with data into T-Tree.
void Insert(ElementType key, ElementData data);
// Delete node with key from T-Tree.
void Delete(ElementType key);
// Find a node with key, retutrn value = -1 no found, >=0 found.
ElementData Find(ElementType key);
// Traversing T-tree.
void TraverseTree(TraverseOrder order);
// return the current size of the t-tree's node.
int GetNodeSize();
// Get t-tree's depth.
int Depth();
// Get the minimum node.
const TTREENODE *GetMinNode();
// Get the maximum node.
const TTREENODE *GetMaxNode();
// Depending on the application, you can inherit your comparison function.
virtual int keycompare(ElementType key1, ElementType key2);
// Clean the whole T-Tree's nodes.
void Clear();
// Test if the tree is logically empty.Return true if empty, false otherwise.
bool IsEmpty( ) const;
// Traverse nodes
private:
// Pre-order traverse.
void PreOrderTraverse(TTREENODE *pNode) const;
// In-order traverse.
void InOrderTraverse(TTREENODE *pNode) const;
// Post-order traverse.
void PostOrderTraverse(TTREENODE *pNode) const;
// Level-order traverse.
void LevelOrderTraverse(TTREENODE *pNode) const;
private:
// Malloc node space from memory buffer.
TTREENODE *MallocNode();
// Free node from memory buffer.
void FreeNode(TTREENODE *pNode);
// To obtain the maximum value of a, b.
int Max(int a, int b) const;
bool _insert(TTREENODE *&pNode, ElementType key, ElementData data);
int remove(TTREENODE *&pNode, ElementType key);
void _earse(TTREENODE *pNode);
// Rotate operate
private:
// Get balabce factor of node.
int BalanceFactor(TTREENODE *pNode) const;
// LL (clock wise) type adjustment.
TTREENODE *SingleRotateLeft(TTREENODE *pNode);
// RR (counter clock wise) type adjustment.
TTREENODE *SingleRotateRight(TTREENODE *pNode);
// LR (after the first reverse cis) type adjustment.
TTREENODE *DoubleRotateLeft(TTREENODE *pNode);
// RL (Soon after the first reverse) type adjustment.
TTREENODE *DoubleRotateRight(TTREENODE *pNode);
// Balance T-tree's right branch.
int BalanceRightBranch(TTREENODE *&pNode);
// Balance T-tree's left branch.
int BalanceLeftBranch(TTREENODE *&pNode);
// Attributes
protected:
// T-tree's root.
TTREENODE *root;
// T-tree's current already alloc node size.
int m_nSize;
};
#endif // _TTEE_H_
TTREENODE* FindMin(TTREENODE *pNode)
{
if (pNode != NULL)
{
if (pNode->left == NULL)
{
return pNode;
}
else
{
return FindMin(pNode->left);
}
}
return NULL;
}
TTREENODE* FindMax(TTREENODE *pNode)
{
if (pNode != NULL)
{
if (pNode->right == NULL)
{
return pNode;
}
else
{
return FindMax(pNode->right);
}
}
return NULL;
}
CTtree::CTtree()
{
root = NULL;
m_nSize = 0;
}
CTtree::~CTtree()
{
Clear();
root = NULL;
m_nSize = 0;
}
int CTtree::GetNodeSize()
{
return m_nSize;
}
ElementData CTtree::Find(ElementType key)
{
TTREENODE *pNode = root;
while (pNode != NULL)
{
int n = pNode->nItems;
ElementType keymin = pNode->item[0];
ElementType keymax = pNode->item[n > 0 ? n - 1 : 0];
int nDiff1 = keycompare(key, keymin);
int nDiff2 = keycompare(key, keymax);
if (nDiff1 >= 0 && nDiff2 <= 0)
{
int l = 0, r = n-1;
// Binary search.
while (l <= r)
{
int i = (l + r) >> 1;
ElementType itemkey = pNode->item[i];
int nDiff = keycompare(key, itemkey);
if (nDiff == 0)
{
return pNode->data[i];
}
else if (nDiff > 0)
{
l = i + 1;
}
else
{
r = i - 1;
}
}
break;
}
else if (nDiff1 < 0)
{
pNode = pNode->left;
}
else if (nDiff2 > 0)
{
pNode = pNode->right;
}
}
return -1;
}
int CTtree::BalanceFactor(TTREENODE *pNode) const
{
int l, r;
TTREENODE *p1, *p2;
l = r = 0;
p1 = p2 = pNode;
if (p1 != NULL)
{
while (p1->left != NULL)
{
p1 = p1->left;
l++;
}
}
if (p2 != NULL)
{
while (p2->right != NULL)
{
p2 = p2->right;
r++;
}
}
return (r - l);
}
int CTtree::Depth()
{
int l, r;
TTREENODE *p1, *p2;
l = r = 0;
p1 = p2 = root;
if (p1 != NULL)
{
while (p1->left != NULL)
{
p1 = p1->left;
l++;
}
}
if (p2 != NULL)
{
while (p2->right != NULL)
{
p2 = p2->right;
r++;
}
}
return max(l, r);
}
const TTREENODE *CTtree::GetMinNode()
{
return FindMin(root);
}
const TTREENODE *CTtree::GetMaxNode()
{
return FindMax(root);
}
int CTtree::Max( int a, int b ) const
{
return (a > b ? a : b);
}
/**
* Rotate T-tree node with left child.this is a single rotation for case LL.
* Update balance factor, then return new root.
*/
TTREENODE *CTtree::SingleRotateLeft(TTREENODE *pNode)
{
TTREENODE *K = pNode->left;
pNode->left = K->right;
K->right = pNode;
// Adjust the balance factor.
pNode->bf = BalanceFactor(pNode);
K->bf = BalanceFactor(K);
return K; // new root
}
/**
* Rotate T-tree node with right child.this is a single rotation for case RR.
* Update balance factor, then return new root.
*/
TTREENODE *CTtree::SingleRotateRight(TTREENODE *pNode)
{
TTREENODE *K = pNode->right;
pNode->right = K->left;
K->left = pNode;
// Adjust the balance factor.
pNode->bf = BalanceFactor(pNode);
K->bf = BalanceFactor(K);
return K; // new root
}
/**
* Rotate T-tree node with left child.this is a double rotation for case LR.
* Update balance factor, then return new root.
*/
TTREENODE *CTtree::DoubleRotateLeft(TTREENODE *pNode)
{
pNode->left = SingleRotateRight(pNode->left);
// Adjust the balance factor.
pNode->bf = BalanceFactor(pNode);
return SingleRotateLeft(pNode);
}
/**
* Rotate T-tree node with right child.this is a double rotation for case RL.
* Update balance factor, then return new root.
*/
TTREENODE *CTtree::DoubleRotateRight(TTREENODE *pNode)
{
pNode->right = SingleRotateLeft(pNode->right);
// Adjust the balance factor.
pNode->bf = BalanceFactor(pNode);
return SingleRotateRight(pNode);
}
void CTtree::Insert(ElementType key, ElementData data)
{
if (root == NULL)
{
root = MallocNode();
root->item[0] = key;
root->data[0] = data;
root->nItems = 1;
root->left = NULL;
root->right = NULL;
}
else
{
TTREENODE *pNode = root;
bool bRet = _insert(pNode, key, data);
if (pNode != root)
{
root = pNode;
}
}
}
void CTtree::FreeNode(TTREENODE *pNode)
{
if (pNode)
{
delete pNode;
pNode = NULL;
}
}
TTREENODE *CTtree::MallocNode()
{
TTREENODE *pNode = new TTREENODE;
memset(pNode, 0, sizeof(TTREENODE));
m_nSize++;
return (pNode);
}
bool CTtree::_insert(TTREENODE *&pNode, ElementType key, ElementData data)
{
int n = pNode->nItems;
ElementType keymin = pNode->item[0];
ElementType keymax = pNode->item[n > 0 ? n - 1 : 0];
int nDiff = keycompare(key, keymin);
if (nDiff <= 0)
{
TTREENODE *pLeftId = pNode->left;
if ((pLeftId == 0 || nDiff == 0 ) && pNode->nItems != pageSize)
{
for (int i = n; i > 0; i--)
{
pNode->item[i] = pNode->item[i-1];
pNode->data[i] = pNode->data[i-1];
}
pNode->item[0] = key;
pNode->data[0] = data;
pNode->nItems += 1;
return false;
}
if (pLeftId == 0)
{
pLeftId = MallocNode();
pLeftId->item[0] = key;
pLeftId->data[0] = data;
pLeftId->nItems += 1;
pNode->left = pLeftId;
}
else
{
TTREENODE *pChildId = pLeftId;
bool bGrow = _insert(pChildId, key, data);
if (pChildId != pLeftId)
{
pNode->left = pLeftId = pChildId;
}
if (!bGrow)
{
return false;
}
}
if (pNode->bf > 0)
{
pNode->bf = 0;
return false;
}
else if (pNode->bf == 0)
{
pNode->bf = -1;
return true;
}
else
{
if (pLeftId->bf < 0)
{
pNode = SingleRotateLeft(pNode); // single LL turn
}
else
{
pNode = DoubleRotateLeft(pNode); // double LR turn
}
return false;
}
}
nDiff = keycompare(key, keymax);
if (nDiff >= 0)
{
TTREENODE *pRightId = pNode->right;
if ((pRightId == 0 || nDiff == 0 ) && pNode->nItems != pageSize)
{
pNode->item[n] = key;
pNode->data[n] = data;
pNode->nItems += 1;
return false;
}
if (pRightId == 0)
{
pRightId = MallocNode();
pRightId->item[0] = key;
pRightId->data[0] = data;
pRightId->nItems += 1;
pNode->right = pRightId;
}
else
{
TTREENODE *pChildId = pRightId;
bool bGrow = _insert(pChildId, key, data);
if (pChildId != pRightId)
{
pNode->right = pRightId = pChildId;
}
if (!bGrow)
{
return false;
}
}
if (pNode->bf < 0)
{
pNode->bf = 0;
return false;
}
else if (pNode->bf == 0)
{
pNode->bf = 1;
return true;
}
else
{
if (pRightId->bf > 0)
{
pNode = SingleRotateRight(pNode); // single RR turn
}
else
{
pNode = DoubleRotateRight(pNode); // double RL turn
}
return false;
}
}
// Node appears in the middle of the primary key points.
int l = 1, r = n-1;
while (l < r)
{
int i = (l + r) >> 1;
ElementType itemkey = pNode->item[i];
nDiff = keycompare(key, itemkey);
if (nDiff > 0)
{
l = i + 1;
}
else
{
r = i;
if (nDiff == 0)
{
break;
}
}
}
// Insert before item[r]
if (n != pageSize)
{
for (int i = n; i > r; i--)
{
pNode->item[i] = pNode->item[i-1];
}
pNode->item[r] = key;
pNode->nItems += 1;
return false;
}
else
{
ElementType reinsertId;
ElementData reinsertData;
// The right than the left subtree subtree weight, into the left equilibrium.
if (pNode->bf >= 0)
{
// Node in the value of the most left out,
// key inserted into its position in the r-1.
// Value will be inserted into the left of its left subtree.
reinsertId = pNode->item[0];
reinsertData = pNode->data[0];
for (int i = 1; i < r; i++)
{
pNode->item[i-1] = pNode->item[i];
pNode->data[i-1] = pNode->data[i];
}
pNode->item[r-1] = key;
pNode->data[r-1] = data;
return _insert(pNode, reinsertId, reinsertData);
}
else // The left than the right subtree subtree re-insert the right balance.
{
// Node in the value of the most right out,
// key inserted into the location of its r.
// The right value will be inserted to its right subtree.
reinsertId = pNode->item[n-1];
reinsertData = pNode->data[n-1];
for (int i = n-1; i > r; i--)
{
pNode->item[i] = pNode->item[i-1];
pNode->data[i] = pNode->data[i-1];
}
pNode->item[r] = key;
pNode->data[r] = data;
return _insert(pNode, reinsertId, reinsertData);
}
}
}
void CTtree::Clear()
{
_earse(root);
}
void CTtree::_earse(TTREENODE *pNode)
{
if (pNode == NULL)
{
return;
}
_earse(pNode->left);
_earse(pNode->right);
FreeNode(pNode);
}
void CTtree::Delete(ElementType key)
{
TTREENODE *pNode = root;
int h = remove(pNode, key);
assert(h >= 0);
if (pNode != root)
{
root = pNode;
}
}
int CTtree::BalanceLeftBranch(TTREENODE *&pNode)
{
if (pNode->bf < 0)
{
pNode->bf = 0;
return 1;
}
else if (pNode->bf == 0)
{
pNode->bf = 1;
return 0;
}
else
{
TTREENODE *pRightId = pNode->right;
if (pRightId->bf >= 0)
{
pNode = SingleRotateRight(pNode); // single RR turn
if (pRightId->bf == 0)
{
pNode->bf = 1;
pRightId->bf = -1;
return 0;
}
else
{
pNode->bf = 0;
pRightId->bf = 0;
return 1;
}
}
else
{
pNode = DoubleRotateRight(pNode); // double RL turn
return 1;
}
}
}
int CTtree::BalanceRightBranch(TTREENODE *&pNode)
{
if (pNode->bf > 0)
{
pNode->bf = 0;
return 1;
}
else if (pNode->bf == 0)
{
pNode->bf = -1;
return 0;
}
else
{
TTREENODE * pLeftId = pNode->left;
if (pLeftId->bf <= 0)
{
pNode = SingleRotateLeft(pNode); // single LL turn
if (pLeftId->bf == 0)
{
pNode->bf = -1;
pLeftId->bf = 1;
return 0;
}
else
{
pNode->bf = 0;
pLeftId->bf = 0;
return 1;
}
}
else
{
pNode = DoubleRotateLeft(pNode); // double LR turn
return 1;
}
}
return 0;
}
int CTtree::remove(TTREENODE *&pNode, ElementType key)
{
int n = pNode->nItems;
ElementType keymin = pNode->item[0];
ElementType keymax = pNode->item[n > 0 ? n - 1 : 0];
int nDiff = keycompare(key, keymin);
if (nDiff <= 0)
{
TTREENODE *pLeftId = pNode->left;
if (pLeftId != 0)
{
TTREENODE *pChildId = pLeftId;
int h = remove(pChildId, key);
if (pChildId != pLeftId)
{
pNode->left = pChildId;
}
if (h > 0)
{
return BalanceLeftBranch(pNode);
}
else if (h == 0)
{
return 0;
}
}
assert (nDiff == 0);
}
nDiff = keycompare(key, keymax);
if (nDiff <= 0)
{
for (int i = 0; i < n; i++)
{
if (pNode->item[i] == key)
{
if (n == 1)
{
if (pNode->right == 0)
{
TTREENODE *pTempNode = pNode->left;
FreeNode(pNode);
pNode = pTempNode;
return 1;
}
else if (pNode->left == 0)
{
TTREENODE *pTempNode = pNode->right;
FreeNode(pNode);
pNode = pTempNode;
return 1;
}
}
TTREENODE *pLeftId = pNode->left, *pRightId = pNode->right;
if (n <= minItems)
{
if (pLeftId != 0 && pNode->bf <= 0)
{
while (pLeftId->right != 0)
{
pLeftId = pLeftId->right;
}
while (--i >= 0)
{
pNode->item[i+1] = pNode->item[i];
pNode->data[i+1] = pNode->data[i];
}
pNode->item[0] = pLeftId->item[pLeftId->nItems-1];
pNode->data[0] = pLeftId->data[pLeftId->nItems-1];
key = pNode->item[0];
TTREENODE *pChildId = pLeftId;
int h = remove(pChildId, pNode->item[0]);
if (pChildId != pLeftId)
{
pNode->left = pChildId;
}
if (h > 0)
{
h = BalanceLeftBranch(pNode);
}
return h;
}
else if (pNode->right != 0)
{
while (pRightId->left != 0)
{
pRightId = pRightId->left;
}
while (++i < n)
{
pNode->item[i-1] = pNode->item[i];
pNode->data[i-1] = pNode->data[i];
}
pNode->item[n-1] = pRightId->item[0];
pNode->data[n-1] = pRightId->data[0];
key = pNode->item[n-1];
TTREENODE *pChildId = pRightId;
int h = remove(pChildId, key);
if (pChildId != pRightId)
{
pNode->right = pChildId;
}
if (h > 0)
{
h = BalanceRightBranch(pNode);
}
return h;
}
}
while (++i < n)
{
pNode->item[i-1] = pNode->item[i];
pNode->data[i-1] = pNode->data[i];
}
pNode->nItems -= 1;
return 0;
}
}
}
TTREENODE *pRightId = pNode->right;
if (pRightId != 0)
{
TTREENODE *pChildId = pRightId;
int h = remove(pChildId, key);
if (pChildId != pRightId)
{
pNode->right = pChildId;
}
if (h > 0)
{
return BalanceRightBranch(pNode);
}
else
{
return h;
}
}
return -1;
}
bool CTtree::IsEmpty( ) const
{
return root == NULL;
}
int CTtree::keycompare(ElementType key1, ElementType key2)
{
int p = key1;
int q = key2;
return p < q ? -1 : p == q ? 0 : 1;
}
void CTtree::TraverseTree(TraverseOrder order)
{
switch (order)
{
case PreOrder:
PreOrderTraverse(root);
break;
case InOrder:
InOrderTraverse(root);
break;
case PostOrder:
PostOrderTraverse(root);
break;
case LevelOrder:
LevelOrderTraverse(root);
break;
}
}
void CTtree::InOrderTraverse(TTREENODE *pNode) const
{
if (pNode != NULL)
{
InOrderTraverse(pNode->left);
int nSize = pNode->nItems;
for (int i = 0; i < nSize; i++)
{
printf("%02d ", pNode->item[i]);
}
InOrderTraverse(pNode->right);
}
}
void CTtree::PostOrderTraverse(TTREENODE *pNode) const
{
if (pNode != NULL)
{
PostOrderTraverse(pNode->left);
PostOrderTraverse(pNode->right);
int nSize = pNode->nItems;
for (int i = 0; i < nSize; i++)
{
printf("%02d ", pNode->item[i]);
}
}
}
void CTtree::PreOrderTraverse(TTREENODE *pNode) const
{
if (pNode != NULL)
{
int nSize = pNode->nItems;
for (int i = 0; i < nSize; i++)
{
printf("%02d ", pNode->item[i]);
}
PreOrderTraverse(pNode->left);
PreOrderTraverse(pNode->right);
}
}
#include "linkqueue.h"
void CTtree::LevelOrderTraverse(TTREENODE *pNode) const
{
if (pNode == NULL)
{
return;
}
// store siblings of each node in a queue so that they are
// visited in order at the next level of the tree
linkedQueue<TTREENODE *> q;
TTREENODE *p;
// initialize the queue by inserting the root in the queue
q.push(pNode);
// continue the iterative process until the queue is empty
while (!q.empty())
{
// delete front node from queue and output the node value
p = (TTREENODE *)q.front();
q.pop();
int nSize = p->nItems;
for (int i = 0; i < nSize; i++)
{
printf("%02d ", p->item[i]);
}
// if a left child exists, insert it in the queue
if (p->left != NULL)
{
q.push(p->left);
}
// if a right child exists, insert next to its sibling
if (p->right != NULL)
{
q.push(p->right);
}
printf("/n");
}
int n = 0;
}
#ifndef NULL
#include <cstddef>
#endif // NULL
// linked list node
template <typename T>
class node
{
public:
T nodeValue; // data held by the node
node<T> *next; // next node in the list
// default constructor with no initial value
node() : next(NULL)
{}
// constructor. initialize nodeValue and next
node(const T& item, node<T> *nextNode = NULL) :
nodeValue(item), next(nextNode)
{}
};
#endif // _NODE_H_
#include "node.h" // node class
// implements a linked queue
template <typename T>
class linkedQueue
{
public:
// Constructor: creates an empty queue.
// Postcondition: qsize = 0, qfront = qback = NULL
linkedQueue();
// copy constructor. builds a copy of obj
linkedQueue(const linkedQueue<T>& obj);
// destructor. clear the linked list
~linkedQueue();
linkedQueue<T>& operator= (const linkedQueue<T>& rhs);
// insert an element at the rear of the queue
// Postcondition: the queue has one more element
void push(const T& item);
// remove an element from the front of the queue.
// Precondition: the queue is not empty. if the queue
// is empty, throw an underflowError exception
// Postcondition: the queue has one less element
void pop();
// return a reference to the front of the queue.
// Precondition: the queue is not empty. if the queue
// is empty, throw an underflowError exception
T& front();
// constant version
const T& front() const;
// return the current size of the queue
int size() const;
// return true if the queue is empty; otherwise return false
bool empty() const;
// clear the list. used by the destructor and assignment
void clear();
private:
// the linked list with qfront stores the elements.
// qback points to the rear of the queue
node<T> *qfront, *qback;
// number of elements in the queue
int qsize;
// copy q so the current list is identical to q
void copy(const linkedQueue<T>& q);
// allocate a node with value item and pointer value NULL
// and return a pointer to it. if memory allocation fails,
// throw the memoryAllocationError exception
node<T> *getNode(const T& item);
};
template <typename T>
void linkedQueue<T>::copy(const linkedQueue<T>& q)
{
// qback moves through the list we are building and
// winds up at the rear of our new list. p
// moves through the list we are copying
node<T> *newNode, *p = q.qfront;
// initially, the list is empty
qfront = qback = NULL;
// nothing to do if p is NULL
if (p != NULL)
{
// create the first node in the queue and assign
// its addres to qback
qfront = qback = getNode(p->nodeValue);
// move forward in the list we are copying
p = p->next;
// copy remaining items
while(p != NULL)
{
// insert new node at the back
newNode = getNode(p->nodeValue);
qback->next = newNode;
// qback is the new node
qback = newNode;
// move to the next node of the list we are copying
p = p->next;
}
}
// the size of the new list is the size of q
qsize = q.qsize;
}
template <typename T>
void linkedQueue<T>::clear()
{
node<T> *curr = qfront, *p;
// delete nodes until we arrive at the end of the list
while (curr != NULL)
{
// save curr in p and move curr forward
// to the next list node
p = curr;
curr = curr->next;
// delete node p
delete p;
}
// specify an emtpy list
qfront = qback = NULL;
qsize = 0;
}
template <typename T>
node<T> *linkedQueue<T>::getNode(const T& item)
{
// allocate a new node
node<T> *newNode = new node<T> (item);
if (newNode == NULL)
{
assert(newNode == NULL);
}
return newNode;
}
// create the empty list qfront = qback = NULL and qsize = 0
template <typename T>
linkedQueue<T>::linkedQueue(): qfront(NULL), qback(NULL), qsize(0)
{}
template <typename T>
linkedQueue<T>::linkedQueue(const linkedQueue<T>& obj)
{
// call copy() and pass the pointer to the front of
// the linked list in obj
copy(obj);
}
template <typename T>
linkedQueue<T>::~linkedQueue()
{
// call clear()
clear();
}
template <typename T>
linkedQueue<T>& linkedQueue<T>::operator= (const linkedQueue<T>& rhs)
{
// delete the current list
clear();
// make the current object a copy of rhs
copy(rhs);
return *this;
}
// insert item into the queue by inserting it at
// the back of the list
template <typename T>
void linkedQueue<T>::push(const T& item)
{
// allocate space for the new node
node<T> *newNode = getNode(item);
// if the queue is empty, insert the new element at the front of
// the list and update both qfront and qback
if (qfront == NULL)
{
qfront = newNode;
qback = newNode;
}
// in a non-empty list, insert new element at back and update qback
else
{
qback->next = newNode;
qback = newNode;
}
// increment the queue size
qsize++;
}
// remove the item at the front of the queue by erasing
// the first element in the linked list
template <typename T>
void linkedQueue<T>::pop()
{
// if the queue is empty, assert
if (qsize == 0)
{
assert(qsize == 0);
}
// save the location of the front of the queue
node<T> *p = qfront;
// move the front forward one node
qfront= qfront->next;
// if the queue is now empty, set qback to NULL
if (qfront == NULL)
qback = NULL;
// delete the node
delete p;
// decrement the queue size
qsize--;
}
template <typename T>
T& linkedQueue<T>::front()
{
// if the queue is empty, assert
if (qsize == 0)
{
assert(qsize == 0);
}
// return the value at the front
return qfront->nodeValue;
}
template <typename T>
const T& linkedQueue<T>::front() const
{
// if the queue is empty, assert
if (qsize == 0)
{
assert(qsize == 0);
}
// return the value at the front
return qfront->nodeValue;
}
template <typename T>
int linkedQueue<T>::size() const
{
return qsize;
}
template <typename T>
bool linkedQueue<T>::empty() const
{
return qsize == 0;
}
#endif // _LINKEDQUEUE_H_
static int a[] = { 30, 28, 45, 15, 16, 17, 19, 90, 25, 36, 31, 32, 20, 95, 23, 91, 21, 11, 12, 13, 10, 8, 9, 7};
int main( void )
{
CTtree tree;
int nSize = _countof(a);
for(int i = 0; i < nSize; i++ )
{
ElementType key = a[i];
ElementData data = i;
tree.Insert(key, data);
}
tree.TraverseTree(LevelOrder);
ElementType datakey = 90;
int nDepth = tree.Depth();
ElementData dataindex = tree.Find(datakey);
const TTREENODE *pNode = tree.GetMinNode();
datakey = 7;
tree.Delete(datakey);
return 0;
}