学步园

//<br /> // Ttree.h: header file<br /> //<br /> // Copyright (C) liuxuezong. All rights reserved<br /> //<br /> // This source is free to use as you like. If you make<br /> // any changes please keep me in the loop. Email them to<br /> // liuxuezong@126.com.<br /> //<br /> // PURPOSE:<br /> //<br /> // To implement thread as a C++ object<br /> //<br /> // REVISIONS<br /> // =======================================================<br /> // Date: 2010.12.03<br /> // Name: liuxuezong<br /> // Description: File creation<br /> //<br /> // Date:<br /> // Name:<br /> // Description:<br /> //<br /> //<br /> //////////////////////////////////////////////////////////////////////<br /> #ifndef _TTREE_H_<br /> #define _TTREE_H_</p> <p>enum<br /> {<br /> pageSize = 125,<br /> minItems = pageSize - 2 // minimal number of items in internal node<br /> };</p> <p>enum TraverseOrder<br /> {<br /> PreOrder,<br /> InOrder,<br /> PostOrder,<br /> LevelOrder<br /> };</p> <p>typedef int ElementData;<br /> typedef int ElementType; </p> <p>typedef struct tagTTREENODE<br /> {<br /> tagTTREENODE *left; // Left child pointer.<br /> tagTTREENODE *right; // Right child pointer.<br /> unsigned short int nItems; // Internal node items.<br /> ElementType item[pageSize]; // Item key array.<br /> ElementData data[pageSize]; // Item data array.<br /> char bf; // Balabce factor(bf = right subtree height - left subtree height)<br /> } TTREENODE, *LPTTREENODE, *PTTREENODE;</p> <p>class CTtree<br /> {<br /> public:</p> <p> // Constructor.<br /> CTtree();</p> <p> // Destructor.<br /> virtual ~CTtree();</p> <p>public:</p> <p> // Insert key with data into T-Tree.<br /> void Insert(ElementType key, ElementData data);</p> <p> // Delete node with key from T-Tree.<br /> void Delete(ElementType key);</p> <p> // Find a node with key, retutrn value = -1 no found, >=0 found.<br /> ElementData Find(ElementType key); </p> <p> // Traversing T-tree.<br /> void TraverseTree(TraverseOrder order);</p> <p> // return the current size of the t-tree's node.<br /> int GetNodeSize();</p> <p> // Get t-tree's depth.<br /> int Depth();</p> <p> // Get the minimum node.<br /> const TTREENODE *GetMinNode();</p> <p> // Get the maximum node.<br /> const TTREENODE *GetMaxNode();</p> <p> // Depending on the application, you can inherit your comparison function.<br /> virtual int keycompare(ElementType key1, ElementType key2);</p> <p> // Clean the whole T-Tree's nodes.<br /> void Clear();</p> <p> // Test if the tree is logically empty.Return true if empty, false otherwise.<br /> bool IsEmpty( ) const;</p> <p>// Traverse nodes<br /> private:</p> <p> // Pre-order traverse.<br /> void PreOrderTraverse(TTREENODE *pNode) const;</p> <p> // In-order traverse.<br /> void InOrderTraverse(TTREENODE *pNode) const;</p> <p> // Post-order traverse.<br /> void PostOrderTraverse(TTREENODE *pNode) const;</p> <p> // Level-order traverse.<br /> void LevelOrderTraverse(TTREENODE *pNode) const;</p> <p>private:</p> <p> // Malloc node space from memory buffer.<br /> TTREENODE *MallocNode();</p> <p> // Free node from memory buffer.<br /> void FreeNode(TTREENODE *pNode);</p> <p> // To obtain the maximum value of a, b.<br /> int Max(int a, int b) const;</p> <p> bool _insert(TTREENODE *&pNode, ElementType key, ElementData data);</p> <p> int remove(TTREENODE *&pNode, ElementType key);</p> <p> void _earse(TTREENODE *pNode);</p> <p>// Rotate operate<br /> private:</p> <p> // Get balabce factor of node.<br /> int BalanceFactor(TTREENODE *pNode) const; </p> <p> // LL (clock wise) type adjustment.<br /> TTREENODE *SingleRotateLeft(TTREENODE *pNode);</p> <p> // RR (counter clock wise) type adjustment.<br /> TTREENODE *SingleRotateRight(TTREENODE *pNode);</p> <p> // LR (after the first reverse cis) type adjustment.<br /> TTREENODE *DoubleRotateLeft(TTREENODE *pNode);</p> <p> // RL (Soon after the first reverse) type adjustment.<br /> TTREENODE *DoubleRotateRight(TTREENODE *pNode);</p> <p> // Balance T-tree's right branch.<br /> int BalanceRightBranch(TTREENODE *&pNode);</p> <p> // Balance T-tree's left branch.<br /> int BalanceLeftBranch(TTREENODE *&pNode);</p> <p>// Attributes<br /> protected:</p> <p> // T-tree's root.<br /> TTREENODE *root; </p> <p> // T-tree's current already alloc node size.<br /> int m_nSize;<br /> };</p> <p>#endif // _TTEE_H_

//<br /> // Ttree.cpp: implementation file<br /> //<br /> // Copyright (C) liuxuezong. All rights reserved<br /> //<br /> // This source is free to use as you like. If you make<br /> // any changes please keep me in the loop. Email them to<br /> // liuxuezong@126.com.<br /> //<br /> // PURPOSE:<br /> //<br /> // To implement mutexes as a C++ object<br /> //<br /> // REVISIONS<br /> // =======================================================<br /> // Date: 2010.12.03<br /> // Name: liuxuezong<br /> // Description: File creation<br /> //<br /> // Date:<br /> // Name:<br /> // Description:<br /> //<br /> //<br /> //////////////////////////////////////////////////////////////////////<br /> #include "stdafx.h"<br /> #include "ttree.h"<br /> #include <math.h><br /> #include <assert.h></p> <p>TTREENODE* FindMin(TTREENODE *pNode)<br /> {<br /> if (pNode != NULL)<br /> {<br /> if (pNode->left == NULL)<br /> {<br /> return pNode;<br /> }<br /> else<br /> {<br /> return FindMin(pNode->left);<br /> }<br /> }<br /> return NULL;<br /> }</p> <p>TTREENODE* FindMax(TTREENODE *pNode)<br /> {<br /> if (pNode != NULL)<br /> {<br /> if (pNode->right == NULL)<br /> {<br /> return pNode;<br /> }<br /> else<br /> {<br /> return FindMax(pNode->right);<br /> }<br /> }<br /> return NULL;<br /> }</p> <p>CTtree::CTtree()<br /> {<br /> root = NULL;<br /> m_nSize = 0;<br /> }</p> <p>CTtree::~CTtree()<br /> {<br /> Clear();<br /> root = NULL;<br /> m_nSize = 0;<br /> }</p> <p>int CTtree::GetNodeSize()<br /> {<br /> return m_nSize;<br /> }</p> <p>ElementData CTtree::Find(ElementType key)<br /> {<br /> TTREENODE *pNode = root;<br /> while (pNode != NULL)<br /> {<br /> int n = pNode->nItems;<br /> ElementType keymin = pNode->item[0];<br /> ElementType keymax = pNode->item[n > 0 ? n - 1 : 0];<br /> int nDiff1 = keycompare(key, keymin);<br /> int nDiff2 = keycompare(key, keymax);<br /> if (nDiff1 >= 0 && nDiff2 <= 0)<br /> {<br /> int l = 0, r = n-1;<br /> // Binary search.<br /> while (l <= r)<br /> {<br /> int i = (l + r) >> 1;<br /> ElementType itemkey = pNode->item[i];<br /> int nDiff = keycompare(key, itemkey);<br /> if (nDiff == 0)<br /> {<br /> return pNode->data[i];<br /> }<br /> else if (nDiff > 0)<br /> {<br /> l = i + 1;<br /> }<br /> else<br /> {<br /> r = i - 1;<br /> }<br /> }<br /> break;<br /> }<br /> else if (nDiff1 < 0)<br /> {<br /> pNode = pNode->left;<br /> }<br /> else if (nDiff2 > 0)<br /> {<br /> pNode = pNode->right;<br /> }<br /> }<br /> return -1;<br /> }</p> <p>int CTtree::BalanceFactor(TTREENODE *pNode) const<br /> {<br /> int l, r;<br /> TTREENODE *p1, *p2;<br /> l = r = 0;<br /> p1 = p2 = pNode;<br /> if (p1 != NULL)<br /> {<br /> while (p1->left != NULL)<br /> {<br /> p1 = p1->left;<br /> l++;<br /> }<br /> }<br /> if (p2 != NULL)<br /> {<br /> while (p2->right != NULL)<br /> {<br /> p2 = p2->right;<br /> r++;<br /> }<br /> }<br /> return (r - l);<br /> }</p> <p>int CTtree::Depth()<br /> {<br /> int l, r;<br /> TTREENODE *p1, *p2;<br /> l = r = 0;<br /> p1 = p2 = root;<br /> if (p1 != NULL)<br /> {<br /> while (p1->left != NULL)<br /> {<br /> p1 = p1->left;<br /> l++;<br /> }<br /> }<br /> if (p2 != NULL)<br /> {<br /> while (p2->right != NULL)<br /> {<br /> p2 = p2->right;<br /> r++;<br /> }<br /> }<br /> return max(l, r);<br /> }</p> <p>const TTREENODE *CTtree::GetMinNode()<br /> {<br /> return FindMin(root);<br /> }</p> <p>const TTREENODE *CTtree::GetMaxNode()<br /> {<br /> return FindMax(root);<br /> }</p> <p>int CTtree::Max( int a, int b ) const<br /> {<br /> return (a > b ? a : b);<br /> }</p> <p>/**<br /> * Rotate T-tree node with left child.this is a single rotation for case LL.<br /> * Update balance factor, then return new root.<br /> */<br /> TTREENODE *CTtree::SingleRotateLeft(TTREENODE *pNode)<br /> {<br /> TTREENODE *K = pNode->left;<br /> pNode->left = K->right;<br /> K->right = pNode;</p> <p> // Adjust the balance factor.<br /> pNode->bf = BalanceFactor(pNode);<br /> K->bf = BalanceFactor(K);</p> <p> return K; // new root<br /> } </p> <p>/**<br /> * Rotate T-tree node with right child.this is a single rotation for case RR.<br /> * Update balance factor, then return new root.<br /> */<br /> TTREENODE *CTtree::SingleRotateRight(TTREENODE *pNode)<br /> {<br /> TTREENODE *K = pNode->right;<br /> pNode->right = K->left;<br /> K->left = pNode;</p> <p> // Adjust the balance factor.<br /> pNode->bf = BalanceFactor(pNode);<br /> K->bf = BalanceFactor(K);</p> <p> return K; // new root<br /> }</p> <p>/**<br /> * Rotate T-tree node with left child.this is a double rotation for case LR.<br /> * Update balance factor, then return new root.<br /> */<br /> TTREENODE *CTtree::DoubleRotateLeft(TTREENODE *pNode)<br /> {<br /> pNode->left = SingleRotateRight(pNode->left);</p> <p> // Adjust the balance factor.<br /> pNode->bf = BalanceFactor(pNode);</p> <p> return SingleRotateLeft(pNode);<br /> } </p> <p>/**<br /> * Rotate T-tree node with right child.this is a double rotation for case RL.<br /> * Update balance factor, then return new root.<br /> */<br /> TTREENODE *CTtree::DoubleRotateRight(TTREENODE *pNode)<br /> {<br /> pNode->right = SingleRotateLeft(pNode->right);</p> <p> // Adjust the balance factor.<br /> pNode->bf = BalanceFactor(pNode);</p> <p> return SingleRotateRight(pNode);<br /> } </p> <p>void CTtree::Insert(ElementType key, ElementData data)<br /> {<br /> if (root == NULL)<br /> {<br /> root = MallocNode();<br /> root->item[0] = key;<br /> root->data[0] = data;<br /> root->nItems = 1;<br /> root->left = NULL;<br /> root->right = NULL;<br /> }<br /> else<br /> {<br /> TTREENODE *pNode = root;<br /> bool bRet = _insert(pNode, key, data);<br /> if (pNode != root)<br /> {<br /> root = pNode;<br /> }<br /> }<br /> } </p> <p>void CTtree::FreeNode(TTREENODE *pNode)<br /> {<br /> if (pNode)<br /> {<br /> delete pNode;<br /> pNode = NULL;<br /> }<br /> }</p> <p>TTREENODE *CTtree::MallocNode()<br /> {<br /> TTREENODE *pNode = new TTREENODE;<br /> memset(pNode, 0, sizeof(TTREENODE));<br /> m_nSize++;</p> <p> return (pNode);<br /> }</p> <p>bool CTtree::_insert(TTREENODE *&pNode, ElementType key, ElementData data)<br /> {<br /> int n = pNode->nItems;<br /> ElementType keymin = pNode->item[0];<br /> ElementType keymax = pNode->item[n > 0 ? n - 1 : 0];<br /> int nDiff = keycompare(key, keymin);<br /> if (nDiff <= 0)<br /> {<br /> TTREENODE *pLeftId = pNode->left;<br /> if ((pLeftId == 0 || nDiff == 0 ) && pNode->nItems != pageSize)<br /> {<br /> for (int i = n; i > 0; i--)<br /> {<br /> pNode->item[i] = pNode->item[i-1];<br /> pNode->data[i] = pNode->data[i-1];<br /> }<br /> pNode->item[0] = key;<br /> pNode->data[0] = data;<br /> pNode->nItems += 1;<br /> return false;<br /> }<br /> if (pLeftId == 0)<br /> {<br /> pLeftId = MallocNode();<br /> pLeftId->item[0] = key;<br /> pLeftId->data[0] = data;<br /> pLeftId->nItems += 1;<br /> pNode->left = pLeftId;<br /> }<br /> else<br /> {<br /> TTREENODE *pChildId = pLeftId;<br /> bool bGrow = _insert(pChildId, key, data);<br /> if (pChildId != pLeftId)<br /> {<br /> pNode->left = pLeftId = pChildId;<br /> }<br /> if (!bGrow)<br /> {<br /> return false;<br /> }<br /> }<br /> if (pNode->bf > 0)<br /> {<br /> pNode->bf = 0;<br /> return false;<br /> }<br /> else if (pNode->bf == 0)<br /> {<br /> pNode->bf = -1;<br /> return true;<br /> }<br /> else<br /> {<br /> if (pLeftId->bf < 0)<br /> {<br /> pNode = SingleRotateLeft(pNode); // single LL turn<br /> }<br /> else<br /> {<br /> pNode = DoubleRotateLeft(pNode); // double LR turn<br /> }<br /> return false;<br /> }</p> <p> }<br /> nDiff = keycompare(key, keymax);<br /> if (nDiff >= 0)<br /> {<br /> TTREENODE *pRightId = pNode->right;<br /> if ((pRightId == 0 || nDiff == 0 ) && pNode->nItems != pageSize)<br /> {<br /> pNode->item[n] = key;<br /> pNode->data[n] = data;<br /> pNode->nItems += 1;<br /> return false;<br /> }<br /> if (pRightId == 0)<br /> {<br /> pRightId = MallocNode();<br /> pRightId->item[0] = key;<br /> pRightId->data[0] = data;<br /> pRightId->nItems += 1;<br /> pNode->right = pRightId;<br /> }<br /> else<br /> {<br /> TTREENODE *pChildId = pRightId;<br /> bool bGrow = _insert(pChildId, key, data);<br /> if (pChildId != pRightId)<br /> {<br /> pNode->right = pRightId = pChildId;<br /> }<br /> if (!bGrow)<br /> {<br /> return false;<br /> }<br /> }<br /> if (pNode->bf < 0)<br /> {<br /> pNode->bf = 0;<br /> return false;<br /> }<br /> else if (pNode->bf == 0)<br /> {<br /> pNode->bf = 1;<br /> return true;<br /> }<br /> else<br /> {<br /> if (pRightId->bf > 0)<br /> {<br /> pNode = SingleRotateRight(pNode); // single RR turn<br /> }<br /> else<br /> {<br /> pNode = DoubleRotateRight(pNode); // double RL turn<br /> }<br /> return false;<br /> }<br /> } </p> <p> // Node appears in the middle of the primary key points.<br /> int l = 1, r = n-1;<br /> while (l < r)<br /> {<br /> int i = (l + r) >> 1;<br /> ElementType itemkey = pNode->item[i];<br /> nDiff = keycompare(key, itemkey);<br /> if (nDiff > 0)<br /> {<br /> l = i + 1;<br /> }<br /> else<br /> {<br /> r = i;<br /> if (nDiff == 0)<br /> {<br /> break;<br /> }<br /> }<br /> }</p> <p> // Insert before item[r]<br /> if (n != pageSize)<br /> {<br /> for (int i = n; i > r; i--)<br /> {<br /> pNode->item[i] = pNode->item[i-1];<br /> }<br /> pNode->item[r] = key;<br /> pNode->nItems += 1;<br /> return false;<br /> }<br /> else<br /> {<br /> ElementType reinsertId;<br /> ElementData reinsertData;<br /> // The right than the left subtree subtree weight, into the left equilibrium.<br /> if (pNode->bf >= 0)<br /> {<br /> // Node in the value of the most left out,<br /> // key inserted into its position in the r-1.<br /> // Value will be inserted into the left of its left subtree.<br /> reinsertId = pNode->item[0];<br /> reinsertData = pNode->data[0];<br /> for (int i = 1; i < r; i++)<br /> {<br /> pNode->item[i-1] = pNode->item[i];<br /> pNode->data[i-1] = pNode->data[i];<br /> }<br /> pNode->item[r-1] = key;<br /> pNode->data[r-1] = data;</p> <p> return _insert(pNode, reinsertId, reinsertData);<br /> }<br /> else // The left than the right subtree subtree re-insert the right balance.<br /> {<br /> // Node in the value of the most right out,<br /> // key inserted into the location of its r.<br /> // The right value will be inserted to its right subtree.<br /> reinsertId = pNode->item[n-1];<br /> reinsertData = pNode->data[n-1];<br /> for (int i = n-1; i > r; i--)<br /> {<br /> pNode->item[i] = pNode->item[i-1];<br /> pNode->data[i] = pNode->data[i-1];<br /> }<br /> pNode->item[r] = key;<br /> pNode->data[r] = data;</p> <p> return _insert(pNode, reinsertId, reinsertData);<br /> }<br /> }<br /> } </p> <p>void CTtree::Clear()<br /> {<br /> _earse(root);<br /> }</p> <p>void CTtree::_earse(TTREENODE *pNode)<br /> {<br /> if (pNode == NULL)<br /> {<br /> return;<br /> }</p> <p> _earse(pNode->left);</p> <p> _earse(pNode->right);</p> <p> FreeNode(pNode);<br /> }</p> <p>void CTtree::Delete(ElementType key)<br /> {<br /> TTREENODE *pNode = root;<br /> int h = remove(pNode, key);<br /> assert(h >= 0);<br /> if (pNode != root)<br /> {<br /> root = pNode;<br /> }<br /> }</p> <p>int CTtree::BalanceLeftBranch(TTREENODE *&pNode)<br /> {<br /> if (pNode->bf < 0)<br /> {<br /> pNode->bf = 0;<br /> return 1;<br /> }<br /> else if (pNode->bf == 0)<br /> {<br /> pNode->bf = 1;<br /> return 0;<br /> }<br /> else<br /> {<br /> TTREENODE *pRightId = pNode->right;<br /> if (pRightId->bf >= 0)<br /> {<br /> pNode = SingleRotateRight(pNode); // single RR turn<br /> if (pRightId->bf == 0)<br /> {<br /> pNode->bf = 1;<br /> pRightId->bf = -1;<br /> return 0;<br /> }<br /> else<br /> {<br /> pNode->bf = 0;<br /> pRightId->bf = 0;<br /> return 1;<br /> }<br /> }<br /> else<br /> {<br /> pNode = DoubleRotateRight(pNode); // double RL turn<br /> return 1;<br /> }<br /> }<br /> }</p> <p>int CTtree::BalanceRightBranch(TTREENODE *&pNode)<br /> {<br /> if (pNode->bf > 0)<br /> {<br /> pNode->bf = 0;<br /> return 1;<br /> }<br /> else if (pNode->bf == 0)<br /> {<br /> pNode->bf = -1;<br /> return 0;<br /> }<br /> else<br /> {<br /> TTREENODE * pLeftId = pNode->left;<br /> if (pLeftId->bf <= 0)<br /> {<br /> pNode = SingleRotateLeft(pNode); // single LL turn<br /> if (pLeftId->bf == 0)<br /> {<br /> pNode->bf = -1;<br /> pLeftId->bf = 1;<br /> return 0;<br /> }<br /> else<br /> {<br /> pNode->bf = 0;<br /> pLeftId->bf = 0;<br /> return 1;<br /> }<br /> }<br /> else<br /> {<br /> pNode = DoubleRotateLeft(pNode); // double LR turn<br /> return 1;<br /> }<br /> }<br /> return 0;<br /> }</p> <p>int CTtree::remove(TTREENODE *&pNode, ElementType key)<br /> {<br /> int n = pNode->nItems;<br /> ElementType keymin = pNode->item[0];<br /> ElementType keymax = pNode->item[n > 0 ? n - 1 : 0];<br /> int nDiff = keycompare(key, keymin);<br /> if (nDiff <= 0)<br /> {<br /> TTREENODE *pLeftId = pNode->left;<br /> if (pLeftId != 0)<br /> {<br /> TTREENODE *pChildId = pLeftId;<br /> int h = remove(pChildId, key);<br /> if (pChildId != pLeftId)<br /> {<br /> pNode->left = pChildId;<br /> }<br /> if (h > 0)<br /> {<br /> return BalanceLeftBranch(pNode);<br /> }<br /> else if (h == 0)<br /> {<br /> return 0;<br /> }<br /> }<br /> assert (nDiff == 0);<br /> }<br /> nDiff = keycompare(key, keymax);<br /> if (nDiff <= 0)<br /> {<br /> for (int i = 0; i < n; i++)<br /> {<br /> if (pNode->item[i] == key)<br /> {<br /> if (n == 1)<br /> {<br /> if (pNode->right == 0)<br /> {<br /> TTREENODE *pTempNode = pNode->left;<br /> FreeNode(pNode);<br /> pNode = pTempNode;<br /> return 1;<br /> }<br /> else if (pNode->left == 0)<br /> {<br /> TTREENODE *pTempNode = pNode->right;<br /> FreeNode(pNode);<br /> pNode = pTempNode;<br /> return 1;<br /> }<br /> }<br /> TTREENODE *pLeftId = pNode->left, *pRightId = pNode->right;<br /> if (n <= minItems)<br /> {<br /> if (pLeftId != 0 && pNode->bf <= 0)<br /> {<br /> while (pLeftId->right != 0)<br /> {<br /> pLeftId = pLeftId->right;<br /> }<br /> while (--i >= 0)<br /> {<br /> pNode->item[i+1] = pNode->item[i];<br /> pNode->data[i+1] = pNode->data[i];<br /> }<br /> pNode->item[0] = pLeftId->item[pLeftId->nItems-1];<br /> pNode->data[0] = pLeftId->data[pLeftId->nItems-1];<br /> key = pNode->item[0];<br /> TTREENODE *pChildId = pLeftId;<br /> int h = remove(pChildId, pNode->item[0]);<br /> if (pChildId != pLeftId)<br /> {<br /> pNode->left = pChildId;<br /> }<br /> if (h > 0)<br /> {<br /> h = BalanceLeftBranch(pNode);<br /> }<br /> return h;<br /> }<br /> else if (pNode->right != 0)<br /> {<br /> while (pRightId->left != 0)<br /> {<br /> pRightId = pRightId->left;<br /> }<br /> while (++i < n)<br /> {<br /> pNode->item[i-1] = pNode->item[i];<br /> pNode->data[i-1] = pNode->data[i];<br /> }<br /> pNode->item[n-1] = pRightId->item[0];<br /> pNode->data[n-1] = pRightId->data[0];<br /> key = pNode->item[n-1];</p> <p> TTREENODE *pChildId = pRightId;<br /> int h = remove(pChildId, key);<br /> if (pChildId != pRightId)<br /> {<br /> pNode->right = pChildId;<br /> }<br /> if (h > 0)<br /> {<br /> h = BalanceRightBranch(pNode);<br /> }<br /> return h;<br /> }<br /> }<br /> while (++i < n)<br /> {<br /> pNode->item[i-1] = pNode->item[i];<br /> pNode->data[i-1] = pNode->data[i];<br /> }<br /> pNode->nItems -= 1;<br /> return 0;<br /> }<br /> }<br /> }<br /> TTREENODE *pRightId = pNode->right;<br /> if (pRightId != 0)<br /> {<br /> TTREENODE *pChildId = pRightId;<br /> int h = remove(pChildId, key);<br /> if (pChildId != pRightId)<br /> {<br /> pNode->right = pChildId;<br /> }<br /> if (h > 0)<br /> {<br /> return BalanceRightBranch(pNode);<br /> }<br /> else<br /> {<br /> return h;<br /> }<br /> }<br /> return -1;<br /> }</p> <p>bool CTtree::IsEmpty( ) const<br /> {<br /> return root == NULL;<br /> }</p> <p>int CTtree::keycompare(ElementType key1, ElementType key2)<br /> {<br /> int p = key1;<br /> int q = key2;<br /> return p < q ? -1 : p == q ? 0 : 1;<br /> }</p> <p>void CTtree::TraverseTree(TraverseOrder order)<br /> {<br /> switch (order)<br /> {<br /> case PreOrder:<br /> PreOrderTraverse(root);<br /> break;<br /> case InOrder:<br /> InOrderTraverse(root);<br /> break;<br /> case PostOrder:<br /> PostOrderTraverse(root);<br /> break;<br /> case LevelOrder:<br /> LevelOrderTraverse(root);<br /> break;<br /> }<br /> }</p> <p>void CTtree::InOrderTraverse(TTREENODE *pNode) const<br /> {<br /> if (pNode != NULL)<br /> {<br /> InOrderTraverse(pNode->left);<br /> int nSize = pNode->nItems;<br /> for (int i = 0; i < nSize; i++)<br /> {<br /> printf("%02d ", pNode->item[i]);<br /> }<br /> InOrderTraverse(pNode->right);<br /> }<br /> } </p> <p>void CTtree::PostOrderTraverse(TTREENODE *pNode) const<br /> {<br /> if (pNode != NULL)<br /> {<br /> PostOrderTraverse(pNode->left);<br /> PostOrderTraverse(pNode->right);<br /> int nSize = pNode->nItems;<br /> for (int i = 0; i < nSize; i++)<br /> {<br /> printf("%02d ", pNode->item[i]);<br /> }<br /> }<br /> } </p> <p>void CTtree::PreOrderTraverse(TTREENODE *pNode) const<br /> {<br /> if (pNode != NULL)<br /> {<br /> int nSize = pNode->nItems;<br /> for (int i = 0; i < nSize; i++)<br /> {<br /> printf("%02d ", pNode->item[i]);<br /> }<br /> PreOrderTraverse(pNode->left);<br /> PreOrderTraverse(pNode->right);<br /> }<br /> }</p> <p>#include "linkqueue.h"</p> <p>void CTtree::LevelOrderTraverse(TTREENODE *pNode) const<br /> {<br /> if (pNode == NULL)<br /> {<br /> return;<br /> }<br /> // store siblings of each node in a queue so that they are<br /> // visited in order at the next level of the tree<br /> linkedQueue<TTREENODE *> q;<br /> TTREENODE *p;</p> <p> // initialize the queue by inserting the root in the queue<br /> q.push(pNode);<br /> // continue the iterative process until the queue is empty<br /> while (!q.empty())<br /> {<br /> // delete front node from queue and output the node value<br /> p = (TTREENODE *)q.front();<br /> q.pop();</p> <p> int nSize = p->nItems;<br /> for (int i = 0; i < nSize; i++)<br /> {<br /> printf("%02d ", p->item[i]);<br /> }<br /> // if a left child exists, insert it in the queue<br /> if (p->left != NULL)<br /> {<br /> q.push(p->left);<br /> }<br /> // if a right child exists, insert next to its sibling<br /> if (p->right != NULL)<br /> {<br /> q.push(p->right);<br /> }<br /> printf("/n");<br /> }<br /> int n = 0;<br /> }</p> <p>

#ifndef _NODE_H_<br /> #define _NODE_H_</p> <p>#ifndef NULL<br /> #include <cstddef><br /> #endif // NULL</p> <p>// linked list node<br /> template <typename T><br /> class node<br /> {<br /> public:<br /> T nodeValue; // data held by the node<br /> node<T> *next; // next node in the list</p> <p> // default constructor with no initial value<br /> node() : next(NULL)<br /> {}</p> <p> // constructor. initialize nodeValue and next<br /> node(const T& item, node<T> *nextNode = NULL) :<br /> nodeValue(item), next(nextNode)<br /> {}<br /> };</p> <p>#endif // _NODE_H_

#ifndef _LINKEDQUEUE_H_<br /> #define _LINKEDQUEUE_H_</p> <p>#include "node.h" // node class</p> <p>// implements a linked queue<br /> template <typename T><br /> class linkedQueue<br /> {<br /> public:<br /> // Constructor: creates an empty queue.<br /> // Postcondition: qsize = 0, qfront = qback = NULL<br /> linkedQueue();</p> <p> // copy constructor. builds a copy of obj<br /> linkedQueue(const linkedQueue<T>& obj);</p> <p> // destructor. clear the linked list<br /> ~linkedQueue();</p> <p> linkedQueue<T>& operator= (const linkedQueue<T>& rhs);</p> <p> // insert an element at the rear of the queue<br /> // Postcondition: the queue has one more element<br /> void push(const T& item);</p> <p> // remove an element from the front of the queue.<br /> // Precondition: the queue is not empty. if the queue<br /> // is empty, throw an underflowError exception<br /> // Postcondition: the queue has one less element<br /> void pop();</p> <p> // return a reference to the front of the queue.<br /> // Precondition: the queue is not empty. if the queue<br /> // is empty, throw an underflowError exception<br /> T& front();</p> <p> // constant version<br /> const T& front() const; </p> <p> // return the current size of the queue<br /> int size() const;</p> <p> // return true if the queue is empty; otherwise return false<br /> bool empty() const;</p> <p> // clear the list. used by the destructor and assignment<br /> void clear();</p> <p>private:<br /> // the linked list with qfront stores the elements.<br /> // qback points to the rear of the queue<br /> node<T> *qfront, *qback;</p> <p> // number of elements in the queue<br /> int qsize;</p> <p> // copy q so the current list is identical to q<br /> void copy(const linkedQueue<T>& q);</p> <p> // allocate a node with value item and pointer value NULL<br /> // and return a pointer to it. if memory allocation fails,<br /> // throw the memoryAllocationError exception<br /> node<T> *getNode(const T& item);<br /> };</p> <p>template <typename T><br /> void linkedQueue<T>::copy(const linkedQueue<T>& q)<br /> {<br /> // qback moves through the list we are building and<br /> // winds up at the rear of our new list. p<br /> // moves through the list we are copying<br /> node<T> *newNode, *p = q.qfront;</p> <p> // initially, the list is empty<br /> qfront = qback = NULL;</p> <p> // nothing to do if p is NULL<br /> if (p != NULL)<br /> {<br /> // create the first node in the queue and assign<br /> // its addres to qback<br /> qfront = qback = getNode(p->nodeValue);</p> <p> // move forward in the list we are copying<br /> p = p->next;</p> <p> // copy remaining items<br /> while(p != NULL)<br /> {<br /> // insert new node at the back<br /> newNode = getNode(p->nodeValue);<br /> qback->next = newNode;</p> <p> // qback is the new node<br /> qback = newNode;</p> <p> // move to the next node of the list we are copying<br /> p = p->next;<br /> }<br /> }</p> <p> // the size of the new list is the size of q<br /> qsize = q.qsize;<br /> }</p> <p>template <typename T><br /> void linkedQueue<T>::clear()<br /> {<br /> node<T> *curr = qfront, *p;</p> <p> // delete nodes until we arrive at the end of the list<br /> while (curr != NULL)<br /> {<br /> // save curr in p and move curr forward<br /> // to the next list node<br /> p = curr;<br /> curr = curr->next;</p> <p> // delete node p<br /> delete p;<br /> }</p> <p> // specify an emtpy list<br /> qfront = qback = NULL;<br /> qsize = 0;<br /> }</p> <p>template <typename T><br /> node<T> *linkedQueue<T>::getNode(const T& item)<br /> {<br /> // allocate a new node<br /> node<T> *newNode = new node<T> (item);<br /> if (newNode == NULL)<br /> {<br /> assert(newNode == NULL);<br /> }<br /> return newNode;<br /> }</p> <p>// create the empty list qfront = qback = NULL and qsize = 0<br /> template <typename T><br /> linkedQueue<T>::linkedQueue(): qfront(NULL), qback(NULL), qsize(0)<br /> {}</p> <p>template <typename T><br /> linkedQueue<T>::linkedQueue(const linkedQueue<T>& obj)<br /> {<br /> // call copy() and pass the pointer to the front of<br /> // the linked list in obj<br /> copy(obj);<br /> }</p> <p>template <typename T><br /> linkedQueue<T>::~linkedQueue()<br /> {<br /> // call clear()<br /> clear();<br /> }</p> <p>template <typename T><br /> linkedQueue<T>& linkedQueue<T>::operator= (const linkedQueue<T>& rhs)<br /> {<br /> // delete the current list<br /> clear();</p> <p> // make the current object a copy of rhs<br /> copy(rhs);</p> <p> return *this;<br /> }</p> <p>// insert item into the queue by inserting it at<br /> // the back of the list<br /> template <typename T><br /> void linkedQueue<T>::push(const T& item)<br /> {<br /> // allocate space for the new node<br /> node<T> *newNode = getNode(item);</p> <p> // if the queue is empty, insert the new element at the front of<br /> // the list and update both qfront and qback<br /> if (qfront == NULL)<br /> {<br /> qfront = newNode;<br /> qback = newNode;<br /> }<br /> // in a non-empty list, insert new element at back and update qback<br /> else<br /> {<br /> qback->next = newNode;<br /> qback = newNode;<br /> }</p> <p> // increment the queue size<br /> qsize++;<br /> }</p> <p>// remove the item at the front of the queue by erasing<br /> // the first element in the linked list<br /> template <typename T><br /> void linkedQueue<T>::pop()<br /> {<br /> // if the queue is empty, assert<br /> if (qsize == 0)<br /> {<br /> assert(qsize == 0);<br /> }</p> <p> // save the location of the front of the queue<br /> node<T> *p = qfront;</p> <p> // move the front forward one node<br /> qfront= qfront->next;</p> <p> // if the queue is now empty, set qback to NULL<br /> if (qfront == NULL)<br /> qback = NULL;</p> <p> // delete the node<br /> delete p;</p> <p> // decrement the queue size<br /> qsize--;<br /> }</p> <p>template <typename T><br /> T& linkedQueue<T>::front()<br /> {<br /> // if the queue is empty, assert<br /> if (qsize == 0)<br /> {<br /> assert(qsize == 0);<br /> }<br /> // return the value at the front<br /> return qfront->nodeValue;<br /> }</p> <p>template <typename T><br /> const T& linkedQueue<T>::front() const<br /> {<br /> // if the queue is empty, assert<br /> if (qsize == 0)<br /> {<br /> assert(qsize == 0);<br /> }<br /> // return the value at the front<br /> return qfront->nodeValue;<br /> }</p> <p>template <typename T><br /> int linkedQueue<T>::size() const<br /> {<br /> return qsize;<br /> }</p> <p>template <typename T><br /> bool linkedQueue<T>::empty() const<br /> {<br /> return qsize == 0;<br /> }</p> <p>#endif // _LINKEDQUEUE_H_<br />

#include "Ttree.h"<br /> #define _countof(array) (sizeof(array)/sizeof(*array))</p> <p>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}; </p> <p>int main( void )<br /> {<br /> CTtree tree;<br /> int nSize = _countof(a);<br /> for(int i = 0; i < nSize; i++ )<br /> {<br /> ElementType key = a[i];<br /> ElementData data = i;<br /> tree.Insert(key, data);<br /> }<br /> tree.TraverseTree(LevelOrder);<br /> ElementType datakey = 90;<br /> int nDepth = tree.Depth();<br /> ElementData dataindex = tree.Find(datakey);<br /> const TTREENODE *pNode = tree.GetMinNode();<br /> datakey = 7;<br /> tree.Delete(datakey);<br /> return 0;<br /> }