精华内容
下载资源
问答
  • 二叉排序树 python实现

    千次阅读 2018-03-14 19:00:00
    class BTNode: def __init__(self, data, left, right): self.data = data self.left = left self.right = right class BTree: def __init__(self, root): ...
    class BTNode:
        def __init__(self, data, left, right):
            self.data = data
            self.left = left
            self.right = right
    
    
    class BTree:
        def __init__(self, root):
            self.root = root;
    
        def insert(self, value):
            self.insertNode(value, self.root)
    
        def insertNode(self, data, btnode):
            if btnode == None:
                btnode = BTNode(data, None, None)
            elif data < btnode.data:
                if btnode.left == None:
                    btnode.left = BTNode(data, None, None)
                    return
    
                self.insertNode(data, btnode.left)
            elif data > btnode.data:
                if btnode.right == None:
                    btnode.right = BTNode(data, None, None)
                    return
    
                self.insertNode(data, btnode.right)
    
        def printBTreeImpl(self, btnode):
            if btnode == None:
                return
    
            self.printBTreeImpl(btnode.left)
            print(btnode.data)
            self.printBTreeImpl(btnode.right)
    
        def printBTree(self):
            self.printBTreeImpl(self.root)
    
    
    if __name__ == '__main__':
    
        root = BTNode(2, None, None)
        btree = BTree(root)
        for i in [5, 8, 3, 1, 4, 9, 0, 7]:
            btree.insert(i)
    
        btree.printBTree()
    
    展开全文
  • Python实现二叉排序树/二叉查找树/二叉搜索树的遍历、查找、删除结点

    基本概述

    • 如何更加高效的完成对数据的查询和添加操作,例如↓↓↓
      在这里插入图片描述
    • 之前解决方案的优缺点
      在这里插入图片描述
    • 树结构解决方案:二叉排序树
      在这里插入图片描述

    二叉排序树的创建和遍历

    class TreeNode(object):
        def __init__(self, val):
            self.val = val
            self.left = None
            self.right = None
            
    class BinarySortTree(object):
        def __init__(self):
            self.root = None
    
        # 添加结点
        def add(self, val):  
            node = TreeNode(val)
            if self.root is None:
                self.root = node
                return
            queue = [self.root]
            while queue:
                temp_node = queue.pop(0)
                # 判断传入结点的值和当前子树结点的值关系
                if node.val < temp_node.val:
                    if temp_node.left is None:
                        temp_node.left = node
                        return
                    else:
                        queue.append(temp_node.left)
                if node.val >= temp_node.val:
                    if temp_node.right is None:
                        temp_node.right = node
                        return
                    else:
                        queue.append(temp_node.right)
    
        # 中序遍历
        def in_order(self, node):
            if node is None:
                return
            self.in_order(node.left)
            print(node.val, end=" ")
            self.in_order(node.right)
    
    
    if __name__ == '__main__':
        t = BinarySortTree()
        note_array = [7, 3, 10, 12, 5, 1, 9]
        for item in note_array:
            t.add(item)
        t.in_order(t.root)
    '''输出结果
    1,3,5,7,9,10,12
    刚好是升序
    '''
    

    二叉排序树的删除

    删除时会遇到的情况

    • 要处理的各种情况
      在这里插入图片描述

    • 第一种情况:删除叶子结点
      在这里插入图片描述

    • 第二种情况:删除只有一棵子树的结点
      在这里插入图片描述

    • 第三种情况:删除有两课子树的结点
      在这里插入图片描述
      (1)上图为,target_node的右子树只有一个结点,那它就是最小的
      在这里插入图片描述
      (2)下图,假设当target_node的右子树,还有一个11,那么11就是最小的,需要把11的值放到target_node的位置
      在这里插入图片描述

    先实现查找要删除的结点

    '''上面代码一样,先省略'''
        def search(self, node, val):
            '''
            :param node: 传入根结点
            :param val: 传入要查找的值
            :return: 找到返回该node,没找到返回None
            '''    
            if node is None:
                return None
            if node.val == val:
                return node
            if val < node.val:
                return self.search(node.left, val)
            else:
                return self.search(node.right, val)
                
    if __name__ == '__main__':
        t = BinarySortTree()
        note_array = [7, 3, 10, 12, 5, 1, 9]
        for item in note_array:
            t.add(item)
        search_node =t.search(t.root, 3) # 3
        if search_node: # 只为测试用
        	print(search_node.val)
        else:
        	print(search_node)
    

    查找要删除节点的父结点

    '''上面代码一样,先省略'''
        # 查找结点的父结点
        def parent(self, node, val):
            '''
            :param node: 传入根结点
            :param val: 传入要找的父结点的值
            :return: 如果找到返回该父结点,如果没有返回None
            '''
            if node is None:  # 如果要找的值遍历完二叉树还不存在,由此退出并返回None
                return None
            if self.root.val == val:  # 根结点没有父结点
                return None
            # 如果当前结点的左子结点或者右子结点存在,并且值就是要找的,直接返回它的父结点
            if (node.left and node.left.val == val) or (node.right and node.right.val == val):
                return node
            else:
                # 如果要找的结点值小于父结点且它的左子结点存在,向左递归
                if val < node.val and node.left:
                    return self.parent(node.left, val)
                # 如果要找的结点值大于父结点且它的右子结点存在,向左递归
                elif node.val < val and node.right:
                    return self.parent(node.right, val)
    
    
    if __name__ == '__main__':
        t = BinarySortTree()
        note_array = [7, 3, 10, 12, 5, 1, 9]
        for item in note_array:
            t.add(item)
        # t.in_order(t.root)
        # print(t.search(t.root, 3))
        parent_node = t.parent(t.root, 1)  # 3
        if parent_node: # 只为输出测试
            print(parent_node.val)
        else:
            print(parent_node)
    

    完整实现二叉排序树的删除结点操作

    class TreeNode(object):
        def __init__(self, val):
            self.val = val
            self.left = None
            self.right = None
    
    
    class BinarySortTree(object):
        def __init__(self):
            self.root = None
    
        # 添加结点
        def add(self, val):  
            node = TreeNode(val)
            if self.root is None:
                self.root = node
                return
            queue = [self.root]
            while queue:
                temp_node = queue.pop(0)
                # 判断传入结点的值和当前子树结点的值关系
                if node.val < temp_node.val:
                    if temp_node.left is None:
                        temp_node.left = node
                        return
                    else:
                        queue.append(temp_node.left)
                if node.val >= temp_node.val:
                    if temp_node.right is None:
                        temp_node.right = node
                        return
                    else:
                        queue.append(temp_node.right)
    
        # 中序遍历
        def in_order(self, node):
            if node is None:
                return
            self.in_order(node.left)
            print(node.val, end=" ")
            self.in_order(node.right)
    
        # 删除节点
        def del_node(self, node, val):
            '''
            :param node: 传入根结点
            :param val: 传入要删除结点的值
            :return:
            '''
            if node is None:
                return
            # 先去找到要删除的结点
            target_node = self.search(node, val)
            if target_node is None:  # 如果没有找到要删除的结点
                return
            # 如果发现当前这棵二叉排序树只有一个结点
            if node.left is None and node.right is None:
                self.root = None # 根结点直接置空
                return
            # 去找到target_node的父结点
            parent = self.parent(node, val)
            # 删除的结点是叶子结点
            if target_node.left is None and target_node.right is None:
                # 判断target_node 是父结点的左子结点,还是右子结点
                if parent.left and parent.left.val == val:  # target_node 是左子结点
                    parent.left = None
                elif parent.right and parent.right.val == val:  # target_node 是右子结点
                    parent.right = None
            elif target_node.left and target_node.right:  # 删除有两颗子树的结点
                min_val = self.del_right_tree_min(target_node.right)
                target_node.val = min_val
            else:  # 删除只有一颗子树的结点
                if target_node.left:  # 如果要删除的结点target_node有左子结点
                    if parent: # 如果target_node有父结点
                        if parent.left.val == val:  # target_node是parent左子结点
                            parent.left = target_node.left
                        else:  # parent.right.val == val,即是target_node是parent右子结点
                            parent.right = target_node.left
                    else:
                        self.root = target_node.left
                else:  # 如果要删除的结点target_node有右子结点
                    if parent: # 如果target_node有父结点
                        if parent.left.val == val:
                            parent.left = target_node.right
                        else:  # parent.right.val == val,即是target_node是parent右子结点
                            parent.right = target_node.right
                    else:
                        self.root = target_node.right
    
        # 查找结点
        def search(self, node, val):
            '''
            :param node: 传入根结点
            :param val: 传入要查找的值
            :return: 找到返回该值,没找到返回None
            '''
            if node is None:
                return None
            if node.val == val:
                return node
            if val < node.val:
                return self.search(node.left, val)
            else:
                return self.search(node.right, val)
    
        # 查找结点的父结点
        def parent(self, node, val):
            '''
            :param node: 传入根结点
            :param val: 传入要找的父结点的值
            :return: 如果找到返回该父结点,如果没有返回None
            '''
            if node is None:  # 如果要找的值遍历完二叉树还不存在,由此退出并返回None
                return None
            if self.root.val == val:  # 根结点没有父结点
                return None
            # 如果当前结点的左子结点或者右子结点存在,并且值就是要要找的,直接返回它的父结点
            if (node.left and node.left.val == val) or (node.right and node.right.val == val):
                return node
            else:
                # 如果要找的结点值小于父结点且它的左子结点存在,向左递归
                if val < node.val and node.left:
                    return self.parent(node.left, val)
                # 如果要找的结点值大于父结点且它的右子结点存在,向左递归
                elif node.val < val and node.right:
                    return self.parent(node.right, val)
    
        def del_right_tree_min(self, node):
        	# 从target_node的右子树出发,查找它的左边最小结点,并返回删除结点的值
        	# 作用1:返回以node为根结点的二叉排序树的最小结点
        	# 作用2:删除 node 为根结点的二叉排序树的最小结点
            temp_node = node
            # 循环的查找左结点,直到找到最小值
            while temp_node.left:
                temp_node = temp_node.left
            # 这时 target就指向了最小结点
            # 调用删除方法,删除最小结点
            self.del_node(self.root, temp_node.val) # 注意传入的还是跟结点,从根结点开始查找
            return temp_node.val
    
    
    if __name__ == '__main__':
        t = BinarySortTree()
        note_array = [7, 3, 10, 12, 5, 1, 9, 2]
        for item in note_array:
            t.add(item)
        '''# 测试:删除叶子结点
        t.del_node(t.root, 2)
        t.del_node(t.root, 5)
        t.del_node(t.root, 9)
        t.del_node(t.root, 12)
        t.in_order(t.root) # 1 3 7 10
        '''
    
        '''# 测试:删除只有一颗子树的结点
        t.del_node(t.root, 1)
        t.in_order(t.root) # 2 3 5 7 9 10 12 
        '''
        # 测试:删除有两颗子树的结点
        # t.del_node(t.root, 7)
        # t.in_order(t.root) # 1 2 3 5 9 10 12
        # t.del_node(t.root, 10)
        # t.in_order(t.root)  # 1 2 3 5 7 9 12
        # t.in_order(t.root)
    
        # 连续删除任意结点测试:
        t.del_node(t.root, 2)
        t.del_node(t.root, 5)
        t.del_node(t.root, 9)
        t.del_node(t.root, 12)
        t.del_node(t.root, 7)
        # t.del_node(t.root, 3)
        # t.del_node(t.root, 10)
        # t.del_node(t.root, 1)
        t.in_order(t.root)
    

    在这里插入图片描述

    展开全文
  • 二叉排序树1、定义2、性质3、操作3.1 查找 1、定义 \quad \quad二叉排序树又称二叉搜索树、二叉查找树。 \quad \quad二叉排序树或是空树,或是满足以下性质的二叉树: (1)若其左子树非空,则左子树上所有结点的值...

    引言

    • 如何更加高效的完成对数据的查询和添加操作,例如↓↓↓

      给你一个数列 (7, 3, 10, 12, 5, 1, 9),要求能够高效的完成对数据的查询和添加。

    • 已有解决方案的优缺点

    在这里插入图片描述

    • 树结构解决方案:
      二叉排序树

    1、定义

    \quad \quad 二叉排序树又称二叉搜索树、二叉查找树。

    \quad \quad 二叉排序树或是空树,或是满足以下性质的二叉树:

    (1)若其左子树非空,则左子树上所有结点的值小于根结点的值;

    (2)若其右子树非空,则右子树上所有结点的值均大于等于根结点的值;

    (3)其左右子树本身又各是一棵二叉排序树

    \quad \quad 总结起来就是根据结点的值有:左子树<根结点<右子树

    \quad \quad 如下图就是一棵二叉排序树:
    在这里插入图片描述
    \quad \quad 它的中序遍历:8、10、11、12、13、15、16、17、18、19、22、25,刚好是排好序的。

    2、性质

    \quad \quad 中序遍历非空的二叉排序树所得到的数据元素序列是一个按关键字排列的递增有序序列。

    3、操作

    3.1 查找

    【算法思想】——递归

    • 若二叉排序树为空,则查找失败,返回空指针
    • 若二叉排序树非空,将给定值与根结点值比较:
      • 若查找的关键字等于根结点,则查找成功,返回根结点地址

      • 否则

        • 若小于根结点,则进一步查其左子树
        • 若大于根结点,则进一步查其右子树

    【代码实现】

    def BST_serach(root, value):
        if not root: # 遇到空节点,未找到
            return False
        if root.value == value: # 找到
            return True
        elif value < root.value: # 若值小于根节点值,继续从左子树中查找
            return BST_serach(root.left, value)
        else: # 否则,该值大于根节点的值,从右子树中查找
            return BST_serach(root.right, value)
    
    

    \quad \quad 二叉排序树上查找某关键字等于给定值的结点过程,其实就是走了一条从根到该结点的路径:

    • 比较的关键次数=此结点所在曾次数
    • 最多的比较次数=树的深度

    \quad \quad 含有n个结点的二叉排序树的平均查找长度ASL和树的形态有关

    在这里插入图片描述
    如何提高形态不均衡的二叉排序树的查找效率?
    平衡化处理,尽量让二叉树的形状均衡,转换成平衡二叉树。

    3.2 插入

    \quad \quad 从根结点开始逐个与关键字进行比较,遇键值较大者就向左,遇键值较小者就向右,一直到尾端,记为插入点。
    【算法思想】—递归

    • 若二叉排序树为空,则插入结点作为根结点插入到空树中;

    • 否则,继续在左、右树上查找

      • 树中已有,不再插入

      • 树中没有

        • 查找直至某个叶子节点的左子树或右子树为空为止,则插入结点应为该叶子结点的左孩子或右孩子。

    【代码实现】

    def BST_insert(root, value):
        if not root: # 遇到空节点,即为插入位置
            root = Node(value)
            return
        if root.value == value: # 若该值已存在于二叉树中,插入失败
            print("Existed!!!")
            return
        elif value < root.value: # 若值小于根节点值,继续从左子树中查找插入位置
            if not root.left: # 如果根结点没有左子树,则插入到左子树中
                root.left = Node(value)
                return
            BST_insert(root.left, value)
            # 注:以上四句不可用 return self.BST_insert(root.right, value)代替,
            # 会出现节点无法插入的问题
        else: # 否则,该值大于根节点的值,从右子树中查找插入位置
            if not root.right:
                root.right = Node(value)
                return
            BST_insert(root.right, value)
    
    

    \quad \quad 插入的元素一定在叶结点上。

    3.3 生成

    \quad \quad 从空树出发,经过一系列的查找、插入操作之后,可生成一棵二叉排序树。

    例:设查找的关键字序列为{45,24,53,45,24,12,37,93}

    在这里插入图片描述
    \quad \quad 容易看出,每次插入新的结点都是二叉排序树上的叶子结点,则在插入时,不必移动其他结点,只需改动某个结点的指针,由空变为非空即可。结点的插入操作与二叉排序树的定义紧密相关,即左<根<右,新插入一个关键字时,从根结点开始比较,直到找到合适的插入位置为止。还有一种情况就是一个序列中可能有两个相同的关键字,对于这种情况,向树中插入关键字时遇到相同关键字时,什么都不做,不进行重复插入操作。

    【代码实现】
    方法一:连续使用插入的方法生成二叉排序树

    #调用上面的插入函数创建二叉排序树
    def createTree(NodeList):
        """创建二叉排序树, NodeList为待插入数据的列表"""
        T = None
        for i in range(len(NodeList)):
            T = BST_insert(T, NodeList[i])
        return T
    

    方法二:使用添加节点的方法创建二叉排序树

    # 添加结点
    def add(self, val):  
        node = TreeNode(val)
        if self.root is None:
            self.root = node
            return
        queue = [self.root]
        while queue:
            temp_node = queue.pop(0)
            # 判断传入结点的值和当前子树结点的值关系
            if node.val < temp_node.val:
                if temp_node.left is None:
                    temp_node.left = node
                    return
                else:
                    queue.append(temp_node.left)
            if node.val >= temp_node.val:
                if temp_node.right is None:
                    temp_node.right = node
                    return
                else:
                    queue.append(temp_node.right)
    

    \quad \quad 一个无序序列可通过构造二叉排序树而变成一个有序序列。构造树的过程就是对无序序列进行排序的过程。

    注意:关键字的输入顺序不同,生成的二叉排序树形态不同。

    在这里插入图片描述

    3.4 删除

    \quad \quad 从二叉排序树中删除一个结点,不能把以该结点为根的子树都删去,只能删除该结点,并且还应保证删除后所得的二叉树仍然满足二叉排序树的性质不变。

    \quad \quad 由于中序遍历二叉排序树可以得到一个递增有序的序列。那么,在二叉排序树中删去一个结点相当于删去有序序列中的一个结点。

    • 将因删除结点而断开的二叉链表重新连接起来;

    • 防止重新链接后树的高度增加。

    删除方法考虑以下几个情况:

    1、 删除节点为叶子节点
    \quad \quad 删除的节点没有左子树也没有右子树,也就是删除的节点为叶子节点。有两种情况:
     1. 该叶子节点为二叉排序树的根结点,也就是二叉排序树中只有一个结点,只需要将root的指针置为空即可
     2. 该叶子节点有父节点,将父节点的连接该删除节点的指针置为空即可。

    思路
    (1) 需求先去找到要删除的结点 targetNode
    (2) 找到targetNode 的 父结点 parent
    (3) 确定 targetNode 是 parent的左子结点 还是右子结点
    (4) 根据前面的情况来对应删除
    左子结点 parent.left = null
    右子结点 parent.right = null;

    2、删除的节点只有左子树或者只有右子树

    \quad \quad 删除节点后,将父节点指针指向子树即可

    • 若结点T的左子树为空,则用T的右子树替代T,即为删除了T结点

    • 若结点T的右子树为空,则用T的左子树替代T,即为删除了T结点

    思路:

    (1) 需求先去找到要删除的结点 targetNode
    (2) 找到targetNode 的 父结点 parent
    (3) 确定targetNode 的子结点是左子结点还是右子结点
    (4) targetNode 是 parent 的左子结点还是右子结点
    (5) 如果targetNode 有左子结点
    5. 1 如果 targetNode 是 parent 的左子结点
    parent.left = targetNode.left;
    5.2 如果 targetNode 是 parent 的右子结点
    parent.right = targetNode.left;
    (6) 如果targetNode 有右子结点
    6.1 如果 targetNode 是 parent 的左子结点
    parent.left = targetNode.right;
    6.2 如果 targetNode 是 parent 的右子结点
    parent.right = targetNode.right

    3、删除的节点同时存在左右子树
    \quad \quad 如果同时存在左右子树,则可以将二叉排序树进行中序遍历,取将要被删除的节点的前驱或者后继节点替代这个被删除的节点的位置。【前驱是左子树中最大的结点;后继是右子树中最小的结点】

    思路
    (1) 需求先去找到要删除的结点 targetNode
    (2) 找到targetNode 的 父结点 parent
    (3) 从targetNode 的右子树找到最小的结点
    (4) 用一个临时变量,将 最小结点的值保存 temp = 11
    (5) 删除该最小结点
    (6) targetNode.value = temp

    在这里插入图片描述
    【代码实现】

    class TreeNode(object):
        def __init__(self, val):
            self.val = val
            self.left = None
            self.right = None
    
    
    class BinarySortTree(object):
        def __init__(self):
            self.root = None
    
        # 添加结点
        def add(self, val):  
            node = TreeNode(val)
            if self.root is None:
                self.root = node
                return
            queue = [self.root]
            while queue:
                temp_node = queue.pop(0)
                # 判断传入结点的值和当前子树结点的值关系
                if node.val < temp_node.val:
                    if temp_node.left is None:
                        temp_node.left = node
                        return
                    else:
                        queue.append(temp_node.left)
                if node.val >= temp_node.val:
                    if temp_node.right is None:
                        temp_node.right = node
                        return
                    else:
                        queue.append(temp_node.right)
    
        # 中序遍历
        def in_order(self, node):
            if node is None:
                return
            self.in_order(node.left)
            print(node.val, end=" ")
            self.in_order(node.right)
    
        # 删除节点
        def del_node(self, node, val):
            '''
            :param node: 传入根结点
            :param val: 传入要删除结点的值
            :return:
            '''
            if node is None:
                return
            # 先去找到要删除的结点
            target_node = self.search(node, val)
            if target_node is None:  # 如果没有找到要删除的结点
                return
            # 如果发现当前这棵二叉排序树只有一个结点
            if node.left is None and node.right is None:
                self.root = None # 根结点直接置空
                return
            # 去找到target_node的父结点
            parent = self.parent(node, val)
            
            # 删除的结点是叶子结点
            if target_node.left is None and target_node.right is None:
                # 判断target_node 是父结点的左子结点,还是右子结点
                if parent.left and parent.left.val == val:  # target_node 是左子结点
                    parent.left = None
                elif parent.right and parent.right.val == val:  # target_node 是右子结点
                    parent.right = None
            elif target_node.left and target_node.right:  # 删除有两颗子树的结点
                min_val = self.del_right_tree_min(target_node.right)
                target_node.val = min_val
            
            # 删除只有一颗子树的结点
            else:  
                if target_node.left:  # 如果要删除的结点target_node有左子结点
                    if parent: # 如果target_node有父结点
                        if parent.left.val == val:  # target_node是parent左子结点
                            parent.left = target_node.left
                        else:  # parent.right.val == val,即是target_node是parent右子结点
                            parent.right = target_node.left
                    else:
                        self.root = target_node.left
                else:  # 如果要删除的结点target_node有右子结点
                    if parent: # 如果target_node有父结点
                        if parent.left.val == val:
                            parent.left = target_node.right
                        else:  # parent.right.val == val,即是target_node是parent右子结点
                            parent.right = target_node.right
                    else:
                        self.root = target_node.right
    
        # 查找结点
        
        def search(self, node, val):
            '''
            :param node: 传入根结点
            :param val: 传入要查找的值
            :return: 找到返回该值,没找到返回None
            '''
            if node is None:
                return None
            if node.val == val:
                return node
            if val < node.val:
                return self.search(node.left, val)
            else:
                return self.search(node.right, val)
    
        
    
        # 查找结点的父结点
        def parent(self, node, val):
            '''
            :param node: 传入根结点
            :param val: 传入要找的父结点的值
            :return: 如果找到返回该父结点,如果没有返回None
            '''
            if node is None:  # 如果要找的值遍历完二叉树还不存在,由此退出并返回None
                return None
            if self.root.val == val:  # 根结点没有父结点
                return None
            # 如果当前结点的左子结点或者右子结点存在,并且值就是要要找的,直接返回它的父结点
            if (node.left and node.left.val == val) or (node.right and node.right.val == val):
                return node
            else:
                # 如果要找的结点值小于父结点且它的左子结点存在,向左递归
                if val < node.val and node.left:
                    return self.parent(node.left, val)
                # 如果要找的结点值大于父结点且它的右子结点存在,向左递归
                elif node.val < val and node.right:
                    return self.parent(node.right, val)
    
        def del_right_tree_min(self, node):
        	# 从target_node的右子树出发,查找它的左边最小结点,并返回删除结点的值
        	# 作用1:返回以node为根结点的二叉排序树的最小结点
        	# 作用2:删除 node 为根结点的二叉排序树的最小结点
            temp_node = node
            # 循环的查找左结点,直到找到最小值
            while temp_node.left:
                temp_node = temp_node.left
            # 这时 target就指向了最小结点
            # 调用删除方法,删除最小结点
            self.del_node(self.root, temp_node.val) # 注意传入的还是跟结点,从根结点开始查找
            return temp_node.val
    
    
    if __name__ == '__main__':
        t = BinarySortTree()
        note_array = [7, 3, 10, 12, 5, 1, 9, 2]
        for item in note_array:
            t.add(item)
        '''# 测试:删除叶子结点
        t.del_node(t.root, 2)
        t.del_node(t.root, 5)
        t.del_node(t.root, 9)
        t.del_node(t.root, 12)
        t.in_order(t.root) # 1 3 7 10
        '''
    
        '''# 测试:删除只有一颗子树的结点
        t.del_node(t.root, 1)
        t.in_order(t.root) # 2 3 5 7 9 10 12 
        '''
        # 测试:删除有两颗子树的结点
        # t.del_node(t.root, 7)
        # t.in_order(t.root) # 1 2 3 5 9 10 12
        # t.del_node(t.root, 10)
        # t.in_order(t.root)  # 1 2 3 5 7 9 12
        # t.in_order(t.root)
    
        # 连续删除任意结点测试:
        t.del_node(t.root, 2)
        t.del_node(t.root, 5)
        t.del_node(t.root, 9)
        t.del_node(t.root, 12)
        t.del_node(t.root, 7)
        # t.del_node(t.root, 3)
        # t.del_node(t.root, 10)
        # t.del_node(t.root, 1)
        t.in_order(t.root)
    
    
    展开全文
  • 兄弟萌,话不多说,show me the code! from chapter8.Assoc import Assoc from stack_queue.code... """二叉排序树的检索算法""" bt = btree while bt != None: entry = bt.data if key < entry.key: bt = b.

    兄弟萌,话不多说,show  me the code!

    Assoc类:

    class Assoc:
        def __init__(self,key,value):
            self.key = key
            self.value = value
    
        def __lt__(self, other):
            """有时有些操作需要考虑排序"""
            return self.key < other.key
    
        def __le__(self, other):
            return self.key < other.key or self.key == other.key
    
        def __str__(self):
            """定义字符串表示形式便于输出和交互"""
            return f"Assoc({self.key},{self.value})"
    
    
    
    
    

     

    SStack类:

    """栈的顺序表实现"""
    
    class StackUnderflow(ValueError): # 栈下溢(空栈访问)
        pass
    
    class SStack(): # 基于顺序表技术实现的栈类
        def __init__(self): # 用list对象 _elems存储栈中元素
            self._elems = [] # 所有栈操作都映射到list操作
    
        def is_empty(self):
            return self._elems == []
    
        def top(self): # 查看栈顶元素
            if self._elems == []:
                raise StackUnderflow("in SStack.top()")
    
            return self._elems[-1]
    
        def push(self,elem):
            self._elems.append(elem)
    
        def pop(self): # 弹出栈顶元素
            if self._elems == []:
                raise StackUnderflow("in SStack.pop()")
    
            return self._elems.pop()

     

    from chapter8.Assoc import Assoc
    from stack_queue.code import SStack
    
    def btSearch(btree,key):
        """二叉排序树的检索算法"""
        bt = btree
        while bt != None:
            entry = bt.data
            if key < entry.key:
                bt = bt.left
            elif key > entry.key:
                bt = bt.right
            else: # key == entry.key
                return entry.value # 返回关键码的关联值
        # 走完整棵树仍没有找到
        return None
    
    class BinTNode:
        """树节点类"""
        def __init__(self,dat,left=None,right=None):
            self.data = dat
            self.left = left
            self.right = right
    
    class DictBinTree:
        """字典二叉排序树类"""
        def __init__(self):
            self._root = None
    
        def isEmpty(self):
            """判断是否为空"""
            return self._root is None
    
        def search(self,key):
            """检索"""
            bt = self._root
            while bt != None:
                entry = bt.data
                if key < entry.key:
                    bt = bt.left
                elif key > entry.key:
                    bt = bt.right
                else:  # key == entry.key
                    return entry.value  # 返回关键码的关联值
            # 走完整棵树仍没有找到
            return None
    
        def insert(self,key,value):
            bt = self._root
            if bt == None:
                """如果树为空,直接建立一个新关键码和关联值的树根节点"""
                self._root = BinTNode(Assoc(key,value))
                return
            """否则搜索新节点的插入位置,沿子节点关系向下"""
            while True:
                entry = bt.data
                if key < entry.key:
                    """遇到应该走左子树"""
                    if bt.left == None:
                        """而左子树为空"""
                        bt.left = BinTNode(Assoc(key,value))
                        return
                    bt = bt.left
                elif key > entry.key:
                    """遇到应该走右子树"""
                    if bt.right == None:
                        """而右子树为空"""
                        bt.right = BinTNode(Assoc(key,value))
                        return
                    return bt.right
                else:
                    """碰到值相等"""
                    bt.data.value = value
                    return
    
        def values(self):
            """中序遍历,值生成迭代器"""
            t,s = self._root,SStack()
            while t != None or not s.is_empty():
                while t != None:
                    s.push(t)
                    t = t.left
                t = s.pop()
                yield t.data.key, t.data.value
                t = t.right
    
        def delete(self,key):
            """删除节点,保证树的结构不变"""
            p,q = None, self._root # 维持p为q的父节点 ,从树根开始找q
            while q != None and q.data.key != key:
                p = q # 维持p为q的父节点
                if key < q.data.key:
                    q = q.left
                else:
                    q = q.right
                if q is None:
                    return # 树中没有关键码key
    
                """到这里q引用要删除节点,p是其父节点或None(这时q是根节点)"""
                if q.left == None:
                    """q没有左子节点"""
                    if p == None:
                        """q是根节点,直接修改root"""
                        self._root = q.right
                    elif q == p.left:
                        p.left = q.right
                    else:
                        p.right = q.right
                    return
    
                r = q.left
                while r.right != None:
                    r = r.right
                r.right = q.right
                if p == None:
                    """q是根节点,修改_root"""
                    self._root = q.left
                elif p.left == q:
                    p.left = q.left
                else:
                    p.right =q.left
    
        def print(self):
            for k,v in self.entries():
                print(k,v)
    
    
    def buildDictBinTree(entries):
        dic = DictBinTree()
        for k,v in entries:
            dic.insert(k,v)
        return dic
    
    
    class DictOptBinTree(DictBinTree):
        def __init__(self,seq):
            DictBinTree.__init__(self)
            data = sorted(seq)
            self._root = DictOptBinTree.buildOBT(data,0,len(data)-1)
    
        @staticmethod
        def buildOBT(data,start,end):
            if start > end:
                return None
            mid = (end+start)//2
            left = DictOptBinTree.buildOBT(data,start,mid-1)
            right = DictOptBinTree.buildOBT(data,mid+1,end)
            return BinTNode(Assoc(*data[mid],left,right))
    

     

    展开全文
  • 首先要知道什么是排序二叉树,二叉排序树是这样定义的,二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:  (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;  (2)若右子树不空,则右...
  • Python实现二叉排序树

    2020-06-15 13:20:30
    二、二叉排序树Python实现 二叉排序树的插入 插入: 从根结点开始逐个与关键字进行比较,小于根结点去左边,大于根结点去右边,碰到子树为空的情况指向关键字。 二叉排序树的查找 查找: 对比节点的值和关
  • 文章目录二叉排序树1. 二叉排序树2. 平衡二叉排序树 二叉排序树 1. 二叉排序树 二叉排序树的检索 def bt_search(btree, key): bt = btree: while bt: if key < bt.val: bt = bt.left elif key > bt.val: ...
  • 二叉排序树,又叫做二叉搜索树或者二叉查找树,它具有以下性质: 若左子树不为空,则左子树上所有节点的值均小于或等于它的根节点的值。 若右子树不为空,则右子树上所有节点的值均大于或等于它的根节点的值。 左、...
  • 二叉排序树(BST) 特点:左节点的值小于根节点的值,右节点的值大于根节点的值;并且在左右子树中也遵循同样的规律。 二叉排序树(BST)的中序遍历是一个顺序序列。 直接判断法:直接判断法关键在于不能只判断左右根...
  • 什么是二叉排序树?         二叉排序树是这样一棵二叉树,若左子树不空,则左子树上所有结点均小于根结点,若右子树不空,则右子树上所有结点均大于根结点其左、右子树也是二叉排序树。(或为...
  • 二叉查找树python

    2018-08-20 22:58:42
    二叉查找树(Binary Search Tree),又称为二叉搜索树、二叉排序树。其或者是一棵空树;或者是具有以下性质的二叉树: 若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值 若右子树不空,则右子树上...
  • 定义: 二叉排序树或者是空树,或者满足以下性质 若它的左子树不空,则左子树上所有节点的值均小于根节点的值 若它的右子树不空,则右子树上所有节点的值均大于根节点的值 左右子树又各是一颗二叉排序树 注: 二叉...
  • 二叉查找树python实现

    千次阅读 2017-10-01 09:29:22
    二叉查找树python实现
  • 一开始学二叉排序树时,最好奇的就是这个树一开始怎么建立起来的,一定得有一个排序好的数组,才能让树达到平衡,否则可能造成链表树 py版: class Node: def __init__(self,val): self.val=val self.left=...
  • 二叉排序树(C与Python分别实现)

    千次阅读 2014-11-01 11:32:49
    1. 什么是二叉排序树二叉排序树是一种特殊的二叉树,可以是一棵空树,也可以是具有下列性质的二叉树: 1. 若左子树不为空,那么左子树所有结点的值都小于它的根结点的值。 2. 若右子树不为空,那么右子树所有...
  • Python描述数据结构之二叉排序树

    多人点赞 2020-08-28 23:38:12
    本篇章主要介绍二叉树的应用之一------二叉排序树,包括二叉排序树的定义、查找、插入、构造、删除及查找效率分析。
  • 平衡二叉排序树又称AVL树。 一棵平衡二叉排序树或者是空树,或者是具有下列性质的二叉排序树: 左子树与右子树的高度之差的绝对值小于等于1; 左子树和右子树也是平衡二叉排序树。 引入平衡二叉排序树的目的,是...
  • 1、二叉排序树(Binary Sort Tree)性质: 或是一颗空树,或是具有如下性质的二叉树: (1) 若它的左子树不空,则 左子树 上所有结点的值 均小于 它的根结点的值; (2) 若它的右子树不空,则 右子树 上所有结点的值 ...
  • 题目:给定一个序列,判断其是不是一颗二叉排序树的后序遍历结果 分析:首先要知道什么是排序二叉树,二叉排序树是这样定义的,二叉排序树或者是一棵空树,或者是具有下列性质的二叉树: (1)若左子树不空,则左...
  • 二叉排序树,又称二叉查找树,或二叉搜索树。二叉排序树或者为空,或者具有以下性质:如果其左子树不空,那么其左子树上所有结点的值均小于其根结点的值。如果其右子树不空,那么其右子树上所有结点的值均大于其根...
  • 二叉搜索的性质是:任何一个节点的左子树中的所有节点值都小于该节点值,其右子中所有节点值都大于当前节点值(必须满足,节点值相等也不行)。二叉搜索的中序遍历结果是一个升序序列。 1.首先对二叉搜索...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,922
精华内容 2,368
关键字:

二叉排序树python

python 订阅