首页 > 编程 > Python > 正文

[硕.Love Python] BinarySearchTree(二叉搜索树)

2019-11-11 03:13:10
字体:
来源:转载
供稿:网友
class Node(object):    __slots__ = ['left''right''data']     def __init__(self, data, left=None, right=None):        self.data = data        self.left = left        self.right = right     def __str__(self):        sl = '%s <-' % self.left if self.left else ''        sr = '-> %s' % self.right if self.right else ''        return '[%s Node(%s) %s]' % (sl, self.data, sr) class BinarySearchTree(object):    def __init__(self):        self.root = None     def insert(self, data):        node, parent = self.search(data, True)        if node:            raise ValueError('"%s" has been in tree.' % data)         node = Node(data)        if parent is None:            self.root = node        elif data < parent.data:            parent.left = node        else:            parent.right = node      def search(self, data, retParent=False):        parent = None        node = self.root         while node and node.data != data:            parent = node            if data < node.data:                node = node.left            else:                node = node.right         return (node, parent) if retParent else node     def delete(self, data):        self._deleteNode(*self.search(data, True))     def _findBiggest(self, node):        parent = None        while node.right:            parent = node            node = node.right        return node, parent     def _deleteNode(self, node, parent):        if node is None:            return          if node.left and node.right:            tmp, tmpParent = self._findBiggest(node.left)            if tmpParent is not None:                tmpParent.right = tmp.left                tmp.left = node.left             tmp.right = node.right        else:            tmp = node.left or node.right         if parent is None:            self.root = tmp        elif parent.left is node:            parent.left = tmp        else:            parent.right = tmp         if __name__ == '__main__':    bst = BinarySearchTree()    while True:        cmd = (raw_input('$ ')).strip().split()        if cmd[0== 'i':            bst.insert(int(cmd[1]))            PRint bst.root        elif cmd[0== 'd':            bst.delete(int(cmd[1]))            print bst.root

刘硕老师Python精品课程:

《Python高级编程技巧实战》:

http://coding.imooc.com/class/62.html

 

《Python算法实战视频课程》:

http://edu.csdn.net/combo/detail/174

 

《Python科学计算—NumPy实战课程》:

http://edu.51cto.com/course/course_id-5046.html

 

熊猫TV直播间:

http://www.panda.tv/671023


发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表