BST

BinTreeを使ってそーと。quicksortを逆にやっているのと同じになるらしい。面白い。
やってみる in python

class Node(object):
        def __init__(self, value, left=None, right=None):
                self.value = value
                self.left = left
                self.right = right

class binarytree(object):
        def __init__(self):
                self.root = None

        def _insert_inner(self, node, value):
                if node is None:
                        return Node(value)
                elif node.value == value:
                        return node
                elif node.value > value:
                        node.left = self._insert_inner(node.left, value)
                else:
                        node.right = self._insert_inner(node.right, value)
                return node

        def insert(self, value):
                self.root = self._insert_inner(self.root, value)

        def _traverse_inner(self, node, ret):
                if node is None: return ret
                self._traverse_inner(node.left, ret)
                ret.append(node.value)
                self._traverse_inner(node.right, ret)
                return ret

        def traverse(self):
                return self._traverse_inner(self.root, [])

if __name__ == "__main__":
        n = binarytree()

        for x in [3,1,8,2,6,7,5]:
                n.insert(x)

        print n.traverse()

sikibu:~ kuro$ python tree.py 
[1, 2, 3, 5, 6, 7, 8]

追記：
traverseのとこ、print はだせぇと言われたので、変更した。