数据结构学习-python实现-二叉搜索树--0415

class BinarySearchTree:
    def __init__(self):
        self.root = None
        self.size = 0

    def length(self):
        return self.size

    def __len__(self):
        return self.size

    def __iter__(self):
        return self.root.__iter__()

    def put(self, key, val):  # 插入操作
        if self.root:  # 若已存在根节点，直接插入数据
            self._put(key, val, self.root)
        else:  # 不存在根节点，则插入根节点的值
            self.root = TreeNode(key, val)
        self.size += 1

    def _put(self, key, val, currentnode):
        if key < currentnode.key:  # 若插入值与根节点的值的大小，将插入值链接到左或右子节点
            if currentnode.hasleftchild(): 
                self._put(key, val, currentnode.leftchild)
            else:
                currentnode.leftchild = TreeNode(key, val, parent=currentnode)
        else:
            if currentnode.hasrightchild():
                self._put(key, val, currentnode.rightchild)
            else:
                currentnode.rightchild = TreeNode(key, val, parent=currentnode)

    def __setitem__(self, key, value):
        self.put(key, value)

    def get(self, key):  # 查找方法
        if self.root:
            res = self._get(key, self.root)
            if res:
                return res.payload
            else:
                return None
        else:
            return None

    def _get(self, key, currentnode):  # 查找节点
        if not currentnode:
            return None
        elif currentnode.key == key:
            return currentnode
        elif key < currentnode.key:
            return self._get(key, currentnode.leftchild)  # 递归的查找
        else:
            return self._get(key, currentnode.rightchild)

    def __getitem__(self, key):
        return self.get(key)

    def __contains__(self, key):
        if self._get(key, self.root):
            return True
        else:
            return False

    def delete(self, key):  # 删除节点
        if self.size > 1:
            nodetoremove = self._get(key, self.root)  # 先查找要删除的节点
            print(nodetoremove.payload)
            if nodetoremove:
                self.remove(nodetoremove.key,nodetoremove)  # 找到了就调用remove方法
                self.size -= 1
            else:
                raise KeyError('Error, key not in tree')
        elif self.size == 1 and self.root.key == key:
            self.root = None
            self.size -= 1
        else:
            raise KeyError('Error, key not in tree')

    def remove(self, key, currentnode):
        if currentnode.isleaf():  # 删除节点为叶节点，则将父节点的相应子节点设置为None
            if currentnode == currentnode.parent.leftchild:
                currentnode.parent.leftchild = None
            else:
                currentnode.parent.rightchild = None
        elif currentnode.hasbothchildren():  # 若有两个子节点，则寻找右子节点的最小节点，替换该位置
            succ = currentnode.findsuccessor()
            succ.spliceout()
            currentnode.key = succ.key
            currentnode.payload = succ.payload
        else:
            if currentnode.hasleftchild():
                if currentnode.isleftchild():
                    currentnode.leftchild.parent = currentnode.parent
                    currentnode.parent.leftchild = currentnode.leftchild
                elif currentnode.isrightchild():
                    currentnode.leftchild.parent = currentnode.parent
                    currentnode.parent.rightchild = currentnode.leftchild
                else:
                    currentnode.replacenodedata(currentnode.leftchild.key,currentnode.leftchild.payload,currentnode.leftchild.leftchild,currentnode.leftchild.rightchild)
            else:
                if currentnode.isleftchild():
                    currentnode.rightchild.parent = currentnode.parent
                    currentnode.parent.leftchild = currentnode.rightchild
                elif currentnode.isrightchild():
                    currentnode.rightchild.parent = currentnode.parent
                    currentnode.parent.rightchild = currentnode.rightchild
                else:
                    currentnode.replacenodedata(currentnode.rightchild.key,currentnode.rightchild.payload,currentnode.rightchild.leftchild,currentnode.rightchild.rightchild)

    def __delitem__(self, key):
        self.delete(key)


class TreeNode:
    def __init__(self, key, val, left=None, right=None, parent=None):
        self.key = key
        self.payload = val
        self.leftchild = left
        self.rightchild = right
        self.parent = parent

    def hasleftchild(self):
        return self.leftchild

    def hasrightchild(self):
        return self.rightchild

    def isleftchild(self):
        return self.parent and self.parent.leftchild == self

    def isrightchild(self):
        return  self.parent and self.parent.rightchild == self

    def isroot(self):
        return not self.parent

    def isleaf(self):
        return not (self.rightchild or self.leftchild)

    def hasanychildren(self):
        return self.rightchild or self.leftchild

    def hasbothchildren(self):
        return self.rightchild and self.leftchild

    def replace_node_data(self, key, value, lc, rc):
        self.key = key
        self.payload = value
        self.leftchild = lc
        self.rightchild = rc
        if self.hasleftchild():
            self.leftchild.parent = self
        if self.hasrightchild():
            self.rightchild.parent = self

    def findsuccessor(self):
        succ = None
        if self.hasrightchild():
            succ = self.rightchild.findmin()
        return succ

    def findmin(self):
        current = self
        while current.hasleftchild():
            current = current.leftchild
        return current

    def spliceout(self):
        if self.isleaf():
            if self.isleftchild():
                self.parent.leftchild = None
            else:
                self.parent.rightchild = None
        elif self.hasanychildren():
            if self.isleftchild():
                self.parent.leftchild = self.leftchild  # 它应该没有左子树了，因为是最小值
            else:
                self.parent.rightchild = self.leftchild  # 应该不会出现
            self.leftchild.parent = self.parent  # 大体不会出现
        else:
            if self.isleftchild():
                self.parent.leftchild = self.rightchild  # 将被移走的节点的子树接到起父节点的相应子树上
            else:
                self.parent.rightchild = self.rightchild
            self.rightchild.parent = self.parent

    # def __iter__(self):  # 这个迭代代码始终报错，但是没有迭代的话，就不能for循环内部节点。还没解决这个问题
    #     if self:
    #        if self.hasleftchild():
    #            for elem in self.leftchild:
    #                yield elem
    #         yield self.key
    #         if self.hasrightchild():
    #             for elem in self.rightchild:
    #                 yield elem

if __name__ == "__main__":
    alist = [70, 31, 93, 94, 14, 23, 73]
    bst = BinarySearchTree()
    bst.put(alist[0], 'luffy')
    bst.put(alist[1], 'ace')
    bst.put(alist[2], 'sanji')
    bst.put(alist[3], 'joba')
    bst.put(alist[4], 'flank')
    bst.put(alist[5], 'solo')
    bst.put(alist[6], 'namei')
    print(len(bst))
    # bst.delete(alist[6])
    bst.delete(alist[0])
    # print(bst.root.leftchild.leftchild.rightchild.key)
    print(bst.root.key)