| 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 | |
| 10 | def hasLeftChild(self): |
| 11 | return self.leftChild |
| 12 | |
| 13 | def hasRightChild(self): |
| 14 | return self.rightChild |
| 15 | |
| 16 | def isLeftChild(self): |
| 17 | return self.parent and self.parent.leftChild == self |
| 18 | |
| 19 | def isRightChild(self): |
| 20 | return self.parent and self.parent.rightChild == self |
| 21 | |
| 22 | def isRoot(self): |
| 23 | return not self.parent |
| 24 | |
| 25 | def isLeaf(self): |
| 26 | return not (self.rightChild or self.leftChild) |
| 27 | |
| 28 | def hasAnyChildren(self): |
| 29 | return self.rightChild or self.leftChild |
| 30 | |
| 31 | def hasBothChildren(self): |
| 32 | return self.rightChild and self.leftChild |
| 33 | |
| 34 | def replaceNodeData(self, key, value, lc, rc): |
| 35 | self.key = key |
| 36 | self.payload = value |
| 37 | self.leftChild = lc |
| 38 | self.rightChild = rc |
| 39 | if self.hasLeftChild(): |
| 40 | self.leftChild.parent = self |
| 41 | if self.hasRightChild(): |
| 42 | self.rightChild.parent = self |
| 43 | |
| 44 | class BinarySearchTree: |
| 45 | def __init__(self): |