猫史档案馆

【作品展示】

 

【作品介绍】

二叉树

 

【作品源代码】

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

    def __str__(self):
        return str(self.item)

class Tree(object):
    def __init__(self):

        self.root = Node("root")
    
    def add(self, item):
        node = Node(item)
        if self.root is None:
            self.root = node
        else:
            q = [self.root]

            while True:
                pop_node = q.pop(0)
                if pop_node.left is None:
                    pop_node.left = node
                    return
                elif pop_node.right is None:
                    pop_node.right = node
                    return
                else:
                    q.append(pop_node.left)
                    q.append(pop_node.right)



    def get_parent(self, item):


        
        if self.root.item == item:
            return None
        tmp = [self.root]
        while tmp:
            pop_node = tmp.pop(0)
            if pop_node.left and pop_node.left.item == item:
                return pop_node
            if pop_node.right and pop_node.right.item == item:
                return pop_node
            if pop_node.left is not None:
                tmp.append(pop_node.left)
            if pop_node.right is not None:
                tmp.append(pop_node.right)
        return None

    def delete(self, item):
        if self.root is None:
            return False

        parent = self.get_parent(item)
        if parent:
            del_node = parent.left if parent.left.item == item else parent.right
            if del_node.left is None:
                if parent.left.item == item:
                    parent.left = del_node.right
                else:
                    parent.right = del_node.right
                del del_node
                return True
            elif del_node.right is None:
                if parent.left.item == item:
                    parent.left = del_node.left
                else:
                    parent.right = del_node.left
                del del_node
                return True
            else:
                tmp_pre = del_node
                tmp_next = del_node.right
                if tmp_next.left is None:
                    tmp_pre.right = tmp_next.right
                    tmp_next.left = del_node.left
                    tmp_next.right = del_node.right

                else:
                    while tmp_next.left:
                        tmp_pre = tmp_next
                        tmp_next = tmp_next.left
                    tmp_pre.left = tmp_next.right
                    tmp_next.left = del_node.left
                    tmp_next.right = del_node.right
                if parent.left.item == item:
                    parent.left = tmp_next
                else:
                    parent.right = tmp_next
                del del_node
                return True
        else:
            return False

    def traverse(self):
        if self.root is None:
            return None
        q = [self.root]
        res = [self.root.item]
        while q != []:
            pop_node = q.pop(0)
            if pop_node.left is not None:
                q.append(pop_node.left)
                res.append(pop_node.left.item)

            if pop_node.right is not None:
                q.append(pop_node.right)
                res.append(pop_node.right.item)
        return res

    def preorder(self, root):
        if root is None:
            return []
        result = [root.item]
        left_item = self.preorder(root.left)
        right_intem = self.preorder(root.right)
        return result + left_item + right_intem

    def inorder(self, root):
        if root is None:
            return []
        result = [root.item]
        left_item = self.inorder(root.left)
        right_intem = self.inorder(root.right)
        return left_item + result + right_intem
    
    def postorder(self, root):
        if root is None:
            return []
        result = [root.item]
        left_item = self.postorder(root.left)
        right_intem = self.postorder(root.right)
        return left_item + right_intem + result
if __name__ == "__main__":
    t = Tree()
    for i in range(10):
        t.add(i)
    print("层序遍历", t.traverse())
    print("先序遍历", t.preorder(t.root))
    print("中序遍历", t.inorder(t.root))
    print("后序遍历", t.postorder(t.root))

    for i in range(10):
        print(i, "的父亲", t.get_parent(i))

    for i in range(0, 15, 3):
        print(f"删除 {i}", '成功' if t.delete(i) else '失败')
        print("层序遍历", t.traverse())
        print("先序遍历", t.preorder(t.root))
        print("中序遍历", t.inorder(t.root))
        print("后序遍历", t.postorder(t.root))

 

【提示】

部分含有Python第三方库相关内容的作品，在海龟编辑器网页端无法运行哦！如遇到这种情况，可以打开下面的链接，下载海龟编辑器客户端：

https://python.codemao.cn