python二叉查找树

本文阅读 1 分钟
首页 学习,Python笔记 正文
  1. # 构建二叉查找树(非平衡)
  2. class TreeNode:
  3. def __init__(self, key, val, left = None, right = None, parent = None):
  4. self.key = key
  5. self.payload = val
  6. self.leftChild = left
  7. self.rightChild = right
  8. self.parent= parent
  9. def hasLeftChild(self):
  10. return self.leftChild
  11. def hasRightChild(self):
  12. return self.rightChild
  13. def isLeftChild(self):
  14. return self.parent and self.parent.leftChild == self
  15. def isRightChild(self):
  16. return self.parent and self.parent.rightChild == self
  17. def isRoot(self):
  18. return not self.parent
  19. def isLeaf(self):
  20. return not (self.rightChild or self.leftChild)
  21. def hasAnyChildren(self):
  22. return self.rightChild or self.leftChild
  23. def hasBothChildren(self):
  24. return self.rightChild and self.leftChild
  25. def replaceNodeData(self, key, value, lc, rc):
  26. self.key = key
  27. self.payload = value
  28. self.leftChild = lc
  29. self.rightChild = rc
  30. if self.hasLeftChild():
  31. self.leftChild.parent = self
  32. if self.hasRightChild():
  33. self.rightChild.parent = self
  34. class BinarySearchTree:
  35. def __init__(self):
  36. self.root = None
  37. self.size = 0
  38. def length(self):
  39. return self.size
  40. def __len__(self):
  41. return self.size
  42. def __iter__(self):
  43. return self.root.__iter__()
  44. def put(self, key, val):
  45. if self.root:
  46. self._put(key, val, self.root)
  47. else:
  48. self.root = TreeNode(key, val)
  49. self.size = self.size + 1
  50. def _put(self, key, val, currentNode):
  51. if key < currentNode.key:
  52. if currentNode.hasLeftChild():
  53. self._put(key, val, currentNode.leftChild)
  54. else:
  55. currentNode.leftChild = TreeNode(key, val, parent=currentNode)
  56. else:
  57. if currentNode.hasRightChild():
  58. self._put(key, val, currentNode.rightChild)
  59. else:
  60. currentNode.rightChild = TreeNode(key, val, parent=currentNode)
  61. def __setitem__(self, k, v):
  62. self.put(k, v)
  63. def get(self, key):
  64. if self.root:
  65. res = self._get(key, self.root)
  66. if res:
  67. return res.payload
  68. else:
  69. return None
  70. else:
  71. return None
  72. def _get(self, key, currentNode):
  73. if not currentNode:
  74. return None
  75. elif currentNode.key == key:
  76. return currentNode
  77. elif key < currentNode.key:
  78. return self._get(key, currentNode.leftChild)
  79. else:
  80. return self._get(key, currentNode.rightChild)
  81. def __getitem__(self, key):
  82. return self.get(key)
  83. def __contains__(self, key):
  84. if self._get(key, self.root):
  85. return True
  86. else:
  87. return False
  88. def delete(self, key):
  89. if self.size > 1:
  90. nodeToRemove = self._get(key, self.root)
  91. if nodeToRemove:
  92. self.remove(nodeToRemove)
  93. self.size -= 1
  94. else:
  95. raise KeyError('Error, key not in tree')
  96. elif self.size == 1 and self.root.key == key:
  97. self.root = None
  98. self.size = self.size - 1
  99. else:
  100. raise KeyError('Error, key not in tree')
  101. def __delitem__(self, key):
  102. self.delete(key)
  103. def spliceOut(self):
  104. if self.isLeaf():
  105. if self.isLeftChild():
  106. self.parent.leftChild = None
  107. else:
  108. self.parent.rightChild = None
  109. elif self.hasAnyChildren():
  110. if self.hasLeftChild():
  111. if self.isLeftChild():
  112. self.parent.leftChild = self.leftChild
  113. else:
  114. self.parent.rightChild = self.leftChild
  115. self.leftChild.parent = self.parent
  116. else:
  117. if self.isLeftChild():
  118. self.parent.leftChild = self.rightChild
  119. else:
  120. self.parent.rightChild = self.rightChild
  121. self.rightChild.parent = self.parent
  122. def findSuccessor(self):
  123. succ = None
  124. if self.hasRightChild():
  125. succ = self.rightChild.findMin()
  126. else:
  127. if self.parent:
  128. if self.isLeftChild():
  129. succ = self.parent
  130. else:
  131. self.parent.rightChild = None
  132. succ = self.parent.findSuccessor()
  133. self.parent.rightChild = self
  134. return succ
  135. def findMin(self):
  136. current = self
  137. while current.hasLeftChild():
  138. current = current.leftChild
  139. return current
  140. def remove(self, currentNode):
  141. if currentNode.isLeaf(): # leaf
  142. if currentNode == currentNode.parent.leftChild:
  143. currentNode.parent.leftChild = None
  144. else:
  145. currentNode.parent.rightChild = None
  146. elif currentNode.hasBothChildren(): # interior
  147. succ = currentNode.findSuccessor()
  148. succ.spliceOut()
  149. currentNode.key = succ.key
  150. currentNode.payload = succ.payload
  151. else: # this node has one child
  152. if currentNode.hasLeftChild():
  153. if currentNode.isLeftChild():
  154. currentNode.leftChild.parent = currentNode.parent
  155. currentNode.parent.leftChild = currentNode.leftChild
  156. elif currentNode.isRightChild():
  157. currentNode.leftChild.parent = currentNode.parent
  158. currentNode.parent.rightChild = currentNode.leftChild
  159. else:
  160. currentNode.replaceNodeData(currentNode.leftChild.key,
  161. currentNode.leftChild.payload,
  162. currentNode.leftChild.leftChild,
  163. currentNode.leftChild.rightChild)
  164. else:
  165. if currentNode.isLeftChild():
  166. currentNode.rightChild.parent = currentNode.parent
  167. currentNode.parent.leftChild = currentNode.rightChild
  168. elif currentNode.isRightChild():
  169. currentNode.rightChild.parent = currentNode.parent
  170. currentNode.parent.rightChild = currentNode.rightChild
  171. else:
  172. currentNode.replaceNodeData(currentNode.rightChild.key,
  173. currentNode.rightChild.payload,
  174. currentNode.rightChild.leftChild,
  175. currentNode.rightChild.rightChild)
  176. mytree = BinarySearchTree()
  177. mytree[3]="red"
  178. mytree[4]="blue"
  179. mytree[6]="yellow"
  180. mytree[2]="at"
  181. print(mytree[6])
  182. print(mytree[2])
解压密码: detechn或detechn.com

免责声明

本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。

本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。

本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。

python三种方法检测变位词Anagram
« 上一篇 01-21
python构建堆
下一篇 » 01-21

发表评论