节点

Node

节点包括：

key
value
left : 指向左子节点
right：指向右子节点
size：子节点的数量 + 1 （自己）

size

size 的值是要包括自身在内的，想象只有一个节点时，size 的大小是 1

只有一个节点

代码

#!/usr/bin/python3

class BinarySearchTree:
    class Node:
        def __init__(self, key, value, size):
            self.key = key
            self.value = value
            self.size = size
            self.left = None
            self.right = None

    def __init__(self):
        self.root = None

    def get_size(self): # 供外部调用
        return get_size_inside(self.root)

    def get_size_inside(self, node):
        if node == None:
            return 0
        else:
            return node.size

    def get(self, key): # 因为 python 不支持重载，所以在外部调用该方法；该方法调用真正进行递归查找的 get_recursion()
        return self.get_recursion(self.root, key)

    def get_recursion(self, node, key):
        if node == None:
            return None, 0
        elif key == node.key:
            return node.value, node.size
        elif key < node.key:
            return self.get_recursion(node.left, key)
        elif key > node.key:
            return self.get_recursion(node.right, key)

    def put(self, key, value):
        self.root = self.put_recursion(self.root, key, value)

    def put_recursion(self, node, key, value):
        '''递归到一个空位，插入新节点；沿路返回修改各节点的 size 值(+1)'''
        if node == None:
            return self.Node(key, value, 1)
        elif key == node.key:
            node.value = value  # 替换值而已，不应把size + 1 ；所以要用下面 (# 更新 size) 的方法；而不是沿路返回都 +1
        elif key < node.key:
            node.left = self.put_recursion(node.left, key, value)
        elif key > node.key:
            node.right = self.put_recursion(node.right, key, value)

        node.size = self.get_size_inside(node.left) + self.get_size_inside(node.right) + 1 # 更新 size

        return node


if __name__ == '__main__':

    bst = BinarySearchTree()

    # 读取输入
    while True:
        key = input('key: ').strip()
        if key == '':
            break
        value = input('value: ').strip()
        bst.put(key, value)

    print('-' * 30)

    # 从链表中获取值
    while True:
        key = input('key: ').strip()
        if key == '':
            break
        print('value: {}, size: {}'.format(*bst.get(key)))