开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 游戏 > 模拟服务器 > 查看源码
KBinTree.cpp
资源名称：SwordOnline.rar　[点击查看]
上传用户：dzyhzl
上传日期：2019-04-29
资源大小：56270k
文件大小：9k
源码类别：

模拟服务器

开发平台：

C/C++

KBinTree.cpp：源码内容
  1. #include "KBinTree.h"
  3. KBinTree::KBinTree()
  4. {
  5. m_pTreeRoot = NULL;
  6. }
  8. //---------------------------------------------------------------------------
  9. // 函数: BTSearch
  10. // 功能:
  11. // 参数: TBinTreeNode * pParentTBinTreeNode
  12. // 参数: TBinTreeNode * pTBinTreeNode
  13. // 参数: DWORD nKey
  14. // 参数: BOOL * pResult
  15. // 返回: TBinTreeNode * 
  17. //---------------------------------------------------------------------------
  18. TBinTreeNode * KBinTree::Search(TBinTreeNode * pParentTBinTreeNode, TBinTreeNode * pTBinTreeNode, TBinTreeNode *pKeyNode, BOOL * pResult)
  19. {
  21. if (pTBinTreeNode == NULL || pParentTBinTreeNode == NULL)
  22. {
  23. *pResult = FALSE;
  24. return pParentTBinTreeNode;
  25. }
  28. if (*pKeyNode == *pTBinTreeNode)
  29. {
  30. *pResult = TRUE;
  31. return pTBinTreeNode;
  32. }
  33. else if (*pKeyNode > *pTBinTreeNode)
  34. return Search(pTBinTreeNode, pTBinTreeNode->pRightChild, pKeyNode, pResult);
  35. else
  36. return Search(pTBinTreeNode, pTBinTreeNode->pLeftChild, pKeyNode, pResult);
  38. }
  42. //---------------------------------------------------------------------------
  43. // 函数: BTInsert
  44. // 功能: 以pTScrpt为父，插入以szKey为关键点的结点
  45. // 参数: TBinTreeNode *pTBinTreeNode 
  46. // 参数: char * szKey
  47. // 返回: TBinTreeNode * 返回插入的结点
  48. //---------------------------------------------------------------------------
  49. TBinTreeNode * KBinTree::AddNode(TBinTreeNode *pNewTBinTreeNode, TBinTreeNode *pTBinTreeNode)
  50. {
  52. int nResult = 0;
  53. if (pNewTBinTreeNode == NULL)
  54. return NULL;
  56. pNewTBinTreeNode->pLeftChild = NULL;
  57. pNewTBinTreeNode->pParent = NULL;
  58. pNewTBinTreeNode->pRightChild = NULL;
  61. if (*pNewTBinTreeNode == *pTBinTreeNode)
  62. return NULL;
  64. //根据大小确定左子还是右子
  65. if (nResult = *pNewTBinTreeNode > *pTBinTreeNode)
  66. {
  67. pTBinTreeNode->pRightChild = pNewTBinTreeNode;
  68. pNewTBinTreeNode->pParent = pTBinTreeNode;
  69. }
  70. else 
  71. {
  72. pTBinTreeNode->pLeftChild = pNewTBinTreeNode;
  73. pNewTBinTreeNode->pParent = pTBinTreeNode;
  74. }
  75. return pNewTBinTreeNode;
  77. }
  82. //---------------------------------------------------------------------------
  83. // 函数:  BTDelete
  84. // 功能: 删除结点
  85. // 参数: TBinTreeNode * pTBinTreeNode
  86. // 参数: TBinTreeNode ** ppRootTBinTreeNode
  87. // 返回: TBinTreeNode * 
  88. //---------------------------------------------------------------------------
  89. TBinTreeNode *  KBinTree::RemoveNode(TBinTreeNode * pTBinTreeNode, TBinTreeNode ** ppRootTBinTreeNode)
  90. {
  91. TBinTreeNode * pFindTBinTreeNode;
  92. if (pTBinTreeNode == NULL)
  93. return NULL;
  95. if (pTBinTreeNode->pLeftChild == NULL && pTBinTreeNode->pRightChild == NULL)//该结点没有左右子
  96. {
  97. if (*ppRootTBinTreeNode == pTBinTreeNode)
  98. {
  99. *ppRootTBinTreeNode = NULL;
  100. }
  101. else
  102. {
  103. int nResult ;
  105. if (*pTBinTreeNode < *pTBinTreeNode->pParent)
  106. nResult = -1;
  107. else 
  108. nResult = 1;
  110. if (nResult < 0)//小于,处在父结点左方
  111. pTBinTreeNode->pParent->pLeftChild = NULL;
  112. else
  113. pTBinTreeNode->pParent->pRightChild = NULL;
  115. }
  117. // delete pTBinTreeNode;
  118. pTBinTreeNode = NULL;
  119. return NULL;
  120. }
  122. else if (!(pTBinTreeNode->pLeftChild && pTBinTreeNode->pRightChild))//只有单子时
  123. {
  124. if (pTBinTreeNode == *ppRootTBinTreeNode)
  125. {
  126. if (pTBinTreeNode->pLeftChild)
  127. {
  128. *ppRootTBinTreeNode = pTBinTreeNode->pLeftChild;
  129. pTBinTreeNode->pLeftChild->pParent = NULL;
  130. }
  131. else
  132. {
  133. *ppRootTBinTreeNode = pTBinTreeNode->pRightChild;
  134. pTBinTreeNode->pRightChild->pParent = NULL;
  135. }
  136. // delete pTBinTreeNode;
  137. pTBinTreeNode = NULL;
  138. return NULL;
  139. }
  142. int nResult ;
  144. if (*pTBinTreeNode < *pTBinTreeNode->pParent)
  145. nResult = -1;
  146. else 
  147. nResult = 1;
  149. if (nResult < 0)//在父的左边
  150. {
  152. if (pTBinTreeNode->pLeftChild)//只有左子
  153. {
  154. pTBinTreeNode->pParent->pLeftChild = pTBinTreeNode->pLeftChild;
  155. pTBinTreeNode->pLeftChild->pParent = pTBinTreeNode->pParent;
  156. }
  157. else
  158. {
  159. pTBinTreeNode->pParent->pLeftChild = pTBinTreeNode->pRightChild;
  160. pTBinTreeNode->pRightChild->pParent = pTBinTreeNode->pParent;
  161. }
  163. //delete pTBinTreeNode;
  164. pTBinTreeNode = NULL;
  166. }
  167. else 
  168. {
  169. if (pTBinTreeNode->pLeftChild)//只有左子
  170. {
  171. pTBinTreeNode->pParent->pRightChild = pTBinTreeNode->pLeftChild;
  172. pTBinTreeNode->pLeftChild->pParent = pTBinTreeNode->pParent;
  173. }
  174. else
  175. {
  176. pTBinTreeNode->pParent->pRightChild = pTBinTreeNode->pRightChild;
  177. pTBinTreeNode->pRightChild->pParent = pTBinTreeNode->pParent;
  178. }
  179. //delete pTBinTreeNode;
  180. pTBinTreeNode = NULL;
  182. } 
  185. return NULL;
  187. }  
  188. else//有全子 
  189. {
  192. {
  194. pFindTBinTreeNode = FindLess(pTBinTreeNode->pLeftChild);
  196. if (pFindTBinTreeNode)
  197. {
  199. //第一部分：处理该结点有左子时，对左子进行指向的改变
  200. //该结点仍有左子
  201. if (pFindTBinTreeNode->pLeftChild)
  202. {
  203. //当发现所将要替代的结点正是它的左子时，将原来的关系不将变化；否则按正常思路改变
  204. if (pFindTBinTreeNode != pTBinTreeNode->pLeftChild)
  205. {
  206. pFindTBinTreeNode->pParent->pRightChild = pFindTBinTreeNode->pLeftChild;
  207. pFindTBinTreeNode->pLeftChild->pParent = pFindTBinTreeNode->pParent;
  208. }
  209. }
  210. else
  211. {
  212. if (pFindTBinTreeNode != pTBinTreeNode->pLeftChild)
  213. {
  214. pFindTBinTreeNode->pParent->pRightChild = NULL;
  215. }
  217. }
  219. //第二部分：改变替换结点链结，实现与原结点相同。
  220. //处理当该替换的结点为删除结点的左子的特殊情况
  221. if (pFindTBinTreeNode == pTBinTreeNode->pLeftChild)
  222. {
  223. //其左子不用交代，保持原状
  224. pTBinTreeNode->pRightChild->pParent = pFindTBinTreeNode;
  226. //其左子不用交代,保持原状
  227. pFindTBinTreeNode->pRightChild = pTBinTreeNode->pRightChild;
  228. pFindTBinTreeNode->pParent = pTBinTreeNode->pParent;
  230. }
  231. else
  232. {
  234. pTBinTreeNode->pLeftChild->pParent = pFindTBinTreeNode;
  235. pTBinTreeNode->pRightChild->pParent = pFindTBinTreeNode;
  238. pFindTBinTreeNode->pLeftChild = pTBinTreeNode->pLeftChild ; 
  239. pFindTBinTreeNode->pRightChild = pTBinTreeNode->pRightChild;
  240. pFindTBinTreeNode->pParent = pTBinTreeNode->pParent;
  242. }
  245. //第三部分   删除结点之父结点链结
  247. if (*ppRootTBinTreeNode == pTBinTreeNode)
  248. {
  249. *ppRootTBinTreeNode = pFindTBinTreeNode;
  250. pFindTBinTreeNode->pParent = NULL;
  251. }
  252. else 
  253. {
  255. int nResult ;
  257. if (*pTBinTreeNode < *pTBinTreeNode->pParent)
  258. nResult = -1;
  259. else 
  260. nResult = 1;
  263. if (nResult < 0)//在父的左面
  264. {
  265. pTBinTreeNode->pParent->pLeftChild = pFindTBinTreeNode;
  266. }
  267. else
  268. {
  269. pTBinTreeNode->pParent->pRightChild = pFindTBinTreeNode;
  270. }
  271. }
  274. //delete pTBinTreeNode;
  275. pTBinTreeNode = NULL;
  276. return pFindTBinTreeNode;
  277. }
  278. else
  279. return NULL;
  280. }
  282. }
  285. }
  287. //---------------------------------------------------------------------------
  288. // 函数: BTFindLess
  289. // 功能:
  290. // 参数: TBinTreeNode * pTBinTreeNode
  291. // 返回: TBinTreeNode * 
  292. //---------------------------------------------------------------------------
  293. TBinTreeNode * KBinTree::FindLess(TBinTreeNode * pTBinTreeNode)
  294. {
  295. if (pTBinTreeNode == NULL)
  296. return NULL;
  298. if (pTBinTreeNode->pRightChild == NULL )
  299. return pTBinTreeNode;
  300. else
  301. return FindLess(pTBinTreeNode->pRightChild);
  304. }
  306. //---------------------------------------------------------------------------
  307. // 函数: BTPreorder
  308. // 功能:
  309. // 参数: TBinTreeNode * pTBinTreeNode
  310. // 返回: DWORD  
  311. //---------------------------------------------------------------------------
  312. DWORD  KBinTree::InOrder(TBinTreeNode * pTBinTreeNode)//中序遍历
  313. {
  314. static int Count = 0 ;
  315. if (pTBinTreeNode != NULL)
  316. {
  319. InOrder(pTBinTreeNode->pLeftChild);
  320. // printf("%dn", pTBinTreeNode->nKey);
  321. InOrder(pTBinTreeNode->pRightChild);
  322. Count ++;
  323. }
  324. m_TempCount = Count;
  325. return Count;
  328. }
  330. TBinTreeNode*  KBinTree::Insert(TBinTreeNode *pNewNode)
  331. {
  332. BOOL nResult = 0;
  333. TBinTreeNode * pNode = NULL;
  335. if (m_pTreeRoot == NULL) 
  336. {
  337. TBinTreeNode * pTBinTreeNode = pNewNode;
  338. m_pTreeRoot = pTBinTreeNode;
  339. pTBinTreeNode->pLeftChild = NULL;
  340. pTBinTreeNode->pRightChild = NULL;
  341. pTBinTreeNode->pParent = NULL;
  342. return pTBinTreeNode;
  343. }
  345. pNode = Search(m_pTreeRoot, m_pTreeRoot, pNewNode, &nResult);
  347. if (nResult == 1)
  348. {
  349. return NULL;
  351. }
  352. else if (nResult == 0)
  353. return AddNode(pNewNode, pNode);
  354. else return NULL;
  355. }
  360. BOOL   KBinTree::RemoveKeyNode(TBinTreeNode * pNode)
  361. {
  362. BOOL nResult = FALSE;//查找的结果
  364. TBinTreeNode * pTBinTreeNode = NULL;//查找返回的指针
  366. if (m_pTreeRoot == NULL)
  367. return FALSE;
  369. pTBinTreeNode = Search(m_pTreeRoot, m_pTreeRoot, pNode, &nResult);
  371. if (nResult && pTBinTreeNode) //在链表中找到了该关键字
  372. {
  374. return RemoveThisNode(pTBinTreeNode);
  375. }
  376. else
  377. return FALSE;
  378. return TRUE;
  380. }
  382. BOOL   KBinTree::RemoveThisNode(TBinTreeNode * pNode)
  383. {
  384. if (pNode == NULL)
  385. return FALSE;
  386. if (m_pTreeRoot == NULL)
  387. return FALSE;
  388. TBinTreeNode * pDelNode;
  389. //该结点并不属于表中的结点，则返回FALSE
  390. if (pNode->pLeftChild == NULL&&pNode->pRightChild == NULL && pNode->pParent == NULL && pNode != m_pTreeRoot)
  391. return FALSE;
  392. pDelNode = RemoveNode(pNode, &m_pTreeRoot);
  393. return TRUE;
  394. }
  396. TBinTreeNode * KBinTree::Search(TBinTreeNode * pKeyNode, BOOL * pResult)
  397. {
  398. TBinTreeNode * pNode;
  399. if (m_pTreeRoot == NULL)
  400. return NULL;
  402. pNode = Search(m_pTreeRoot, m_pTreeRoot, pKeyNode, pResult);
  403. return pNode;
  404. }