二叉搜索树， 它的性质是左边节点都小于根节点，右边的都大于根节点。 而且一般来说它是不存在重复元素的。
| 19 | |
| 20 | |
| 21 | class binarySearchTree(object): |
| 22 | """ |
| 23 | 二叉搜索树， |
| 24 | 它的性质是左边节点都小于根节点，右边的都大于根节点。 |
| 25 | 而且一般来说它是不存在重复元素的。 |
| 26 | |
| 27 | """ |
| 28 | |
| 29 | def __init__(self, root): |
| 30 | if isinstance(root, TreeNode): |
| 31 | print(1) |
| 32 | self.root = root |
| 33 | else: |
| 34 | self.root = TreeNode(root) |
| 35 | |
| 36 | def add(self, value): |
| 37 | # 从顶点开始遍历，找寻其合适的位置。 |
| 38 | root = self.root |
| 39 | while 1: |
| 40 | if root.val < value: |
| 41 | if root.right is None: |
| 42 | if self.search(value): |
| 43 | break |
| 44 | root.right = TreeNode(value) |
| 45 | break |
| 46 | else: |
| 47 | root = root.right |
| 48 | continue |
| 49 | |
| 50 | if root.val > value: |
| 51 | if root.left is None: |
| 52 | if self.search(value): |
| 53 | break |
| 54 | root.left = TreeNode(value) |
| 55 | break |
| 56 | else: |
| 57 | root = root.left |
| 58 | continue |
| 59 | |
| 60 | if root.val == value: |
| 61 | break |
| 62 | |
| 63 | def search(self, value): |
| 64 | # 查找一个值是否存在于这颗树中。 |
| 65 | return self._search(self.root, value) |
| 66 | |
| 67 | def _search(self, root, value): |
| 68 | if root.val == value: |
| 69 | return True |
| 70 | |
| 71 | if root.right: |
| 72 | if root.val < value: |
| 73 | return self._search(root.right, value) |
| 74 | |
| 75 | if root.left: |
| 76 | if root.val > value: |
| 77 | return self._search(root.left, value) |
| 78 |