如何在Python中实现二进制搜索树？

如何在Python中实现二进制搜索树？

这是二进制插入的快速示例：

class Node:    def __init__(self, val):        self.l_child = None        self.r_child = None        self.data = valdef binary_insert(root, node):    if root is None:        root = node    else:        if root.data > node.data: if root.l_child is None:     root.l_child = node else:     binary_insert(root.l_child, node)        else: if root.r_child is None:     root.r_child = node else:     binary_insert(root.r_child, node)def in_order_print(root):    if not root:        return    in_order_print(root.l_child)    print root.data    in_order_print(root.r_child)def pre_order_print(root):    if not root:        return print root.data    pre_order_print(root.l_child)    pre_order_print(root.r_child)

---

r = Node(3)binary_insert(r, Node(7))binary_insert(r, Node(1))binary_insert(r, Node(5))

---

     3    /    1   7      /     5

---

print "in order:"in_order_print(r)print "pre order"pre_order_print(r)in order:1357pre order3175