python常用算法(5)——树,二叉树与AVL树(二)

简介: python常用算法(5)——树,二叉树与AVL树

python常用算法(5)——树,二叉树与AVL树(一)https://developer.aliyun.com/article/1542698

4.4  二叉搜索树的查询操作

   从根节点开始查找,待查找的值是否与根节点的值相同,若相同则返回True;否则,判断待寻找的值是否比根节点的值小,若是则进入根节点左子树进行查找,否则进入右子树进行查找。该操作使用递归实现。

  代码如下:

def query(self, node, val):
    if not node:
        return None
    if node.data < val:
        return self.query(node.rchild, val)
    elif node.data > val:
        return self.query(node.lchild, val)
    else:
        return node
4.5  二叉树的查询操作——找最大值(最小值)

  查找最小值:从根节点开始,沿着左子树一直往下,直到找到最后一个左子树节点,按照定义可知,该节点一定是该二叉搜索树中的最小值节点。

  程序代码如下:

def findMin(self, root):
    '''查找二叉搜索树中最小值点'''
    if root.left:
        return self.findMin(root.left)
    else:
        return root

  查找最大值:从根节点开始,沿着右子树一直往下,知道找到最后一个右子树节点,按照定义可知,该节点一定是该二叉搜索树中的最大值节点。

  程序代码如下:

def findMax(self, root):
    '''查找二叉搜索树中最大值点'''
    if root.right:
        return self.findMax(root.right)
    else:
        return root
4.6  二叉搜索树的删除操作

  对二叉搜索树节点的删除操作分为以下三种情况

  1,如果要删除的节点是叶子节点:直接删除

  2,如果要删除的节点只有一个孩子:将此节点的父亲与孩子连接,然后删除该节点(注意:该待删节点可能只有左子树或者右子树)

  3,如果要删除的节点有两个孩子:将其右子树的最小节点(该节点最多有一个右孩子)删除,并替换当前节点

  代码如下:

# _*_coding:utf-8_*_
import random
 
 
class BiTreeNode:
    def __init__(self, data):
        self.data = data
        self.lchild = None  # 左孩子
        self.rchild = None  # 右孩子
        self.parent = None
 
 
class BST:
    def __init__(self, li=None):
        self.root = None
        if li:
            for val in li:
                self.insert_no_rec(val)
 
 
    def __remove_node_1(self, node):
        # 第一种情况:node是叶子节点
        if not node.parent:
            self.root = None
        if node == node.parent.lchild:  # node是他父亲的左孩子
            node.parent.lchild = None
            node.parent = None  # 可以不写
        else:  # node是他父亲的右孩子
            node.parent.rchild = None
 
    def __remove_node_21(self, node):
        # 情况2.1:node只有一个孩子,且为左孩子
        if not node.parent:  # 根节点
            self.root = node.lchild
            node.lchild.parent = None
        elif node == node.parent.lchild:  # node是它父亲的左孩子
            node.parent.lchild = node.lchild
            node.lchild.parent = node.parent
        else:  # node 是它父亲的右孩子
            node.parent.rchild = node.lchild
            node.lchild.parent = node.parent
 
    def __remove_node_22(self, node):
        # 情况2.2:node只有一个孩子,且为右孩子
        if not node.parent:
            self.root = node.rchild
        elif node == node.parent.lchild:
            node.parent.lchild = node.rchild
            node.rchild.parent = node.parent
        else:
            node.parent.rchild = node.rchild
            node.rchild.parent = node.parent
    def delete(self, val):
        if self.root:  # 不是空树
            node = self.query_no_rec(val)
            if not node:  # 不存在
                return False
            if not node.lchild and not node.rchild:  # 1,叶子节点
                self.__remove_node_1(node)
            elif not node.rchild:  # 2.1 只有一个左孩子
                self.__remove_node_21(node)
            elif not node.lchild:  # 2.2 只有一个右孩子
                self.__remove_node_22(node)
            else:
                # 3,两个孩纸都有
                min_node = node.rchild
                while min_node.lchild:  # 有左孩子
                    min_node = min_node.lchild
                node.data = min_node.data
                # 删除min_node
                if min_node.rchild:
                    self.__remove_node_22(min_node)
                else:
                    self.__remove_node_1(min_node)
4.7  二叉搜索树的打印操作

  实现二叉搜索树的前序遍历,中序遍历,后序遍历,并打印出来。其中中序遍历打印出来的数列是按照递增顺序排列。

  程序的代码如下:

def printTree(self, root):
    # 打印二叉搜索树(中序打印,有序数列—)
    if root == None:
        return 
    self.printTree(root.left)
    print(root.val, end=',')
    self.printTree(root.right)
4.8  二叉树的插入,查询,删除,打印完整代码

  代码如下:

# _*_coding:utf-8_*_
import random
 
 
class BiTreeNode:
    def __init__(self, data):
        self.data = data
        self.lchild = None  # 左孩子
        self.rchild = None  # 右孩子
        self.parent = None
 
 
class BST:
    def __init__(self, li=None):
        self.root = None
        if li:
            for val in li:
                self.insert_no_rec(val)
 
    def insert(self, node, val):
        if not node:
            node = BiTreeNode(val)
        elif val < node.data:
            node.lchild = self.insert(node.lchild, val)
            node.lchild.parent = node
        elif val > node.data:
            node.rchild = self.insert(node.rchild, val)
            node.rchild.parent = node
        return node
    def insert_no_rec(self, val):
        p = self.root
        if not p:  # 空树
            self.root = BiTreeNode(val)
            return
        while True:
            if val < p.data:
                if p.lchild:
                    p = p.lchild
                else:  # 左孩子不存在
                    p.lchild = BiTreeNode(val)
                    p.lchild.parent = p
                    return
            elif val > p.data:
                if p.rchild:
                    p = p.rchild
                else:
                    p.rchild = BiTreeNode(val)
                    p.rchild.parent = p
                    return
            else:
                return
 
    def query(self, node, val):
        if not node:
            return None
        if node.data < val:
            return self.query(node.rchild, val)
        elif node.data > val:
            return self.query(node.lchild, val)
        else:
            return node
    def query_no_rec(self, val):
        p = self.root
        while p:
            if p.data < val:
                p = p.rchild
            elif p.data > val:
                p = p.lchild
            else:
                return p
        return None
    def pre_order(self, root):
        if root:
            print(root.data, end=',')
            self.pre_order(root.lchild)
            self.pre_order(root.rchild)
    def in_order(self, root):
        if root:
            self.in_order(root.lchild)
            print(root.data, end=',')
            self.in_order(root.rchild)
    def post_order(self, root):
        if root:
            self.post_order(root.lchild)
            self.post_order(root.rchild)
            print(root.data, end=',')
    def __remove_node_1(self, node):
        # 第一种情况:node是叶子节点
        if not node.parent:
            self.root = None
        if node == node.parent.lchild:  # node是他父亲的左孩子
            node.parent.lchild = None
            node.parent = None  # 可以不写
        else:  # node是他父亲的右孩子
            node.parent.rchild = None
 
    def __remove_node_21(self, node):
        # 情况2.1:node只有一个孩子,且为左孩子
        if not node.parent:  # 根节点
            self.root = node.lchild
            node.lchild.parent = None
        elif node == node.parent.lchild:  # node是它父亲的左孩子
            node.parent.lchild = node.lchild
            node.lchild.parent = node.parent
        else:  # node 是它父亲的右孩子
            node.parent.rchild = node.lchild
            node.lchild.parent = node.parent
 
    def __remove_node_22(self, node):
        # 情况2.2:node只有一个孩子,且为右孩子
        if not node.parent:
            self.root = node.rchild
        elif node == node.parent.lchild:
            node.parent.lchild = node.rchild
            node.rchild.parent = node.parent
        else:
            node.parent.rchild = node.rchild
            node.rchild.parent = node.parent
    def delete(self, val):
        if self.root:  # 不是空树
            node = self.query_no_rec(val)
            if not node:  # 不存在
                return False
            if not node.lchild and not node.rchild:  # 1,叶子节点
                self.__remove_node_1(node)
            elif not node.rchild:  # 2.1 只有一个左孩子
                self.__remove_node_21(node)
            elif not node.lchild:  # 2.2 只有一个右孩子
                self.__remove_node_22(node)
            else:
                # 3,两个孩纸都有
                min_node = node.rchild
                while min_node.lchild:  # 有左孩子
                    min_node = min_node.lchild
                node.data = min_node.data
                # 删除min_node
                if min_node.rchild:
                    self.__remove_node_22(min_node)
                else:
                    self.__remove_node_1(min_node)
 
 
    def printTree(self, root):
        # 打印二叉搜索树(中序打印,有序数列—)
        if root == None:
            return
        self.printTree(root.left)
        print(root.val, end=',')
        self.printTree(root.right)
 
# 删除
tree = BST([1, 4, 2, 5, 3, 8, 6, 9, 7])
tree.in_order(tree.root)
print(" ")
tree.delete(4)
tree.delete(1)
tree.delete(8)
tree.in_order(tree.root)
 
'''
# 插入操作
tree = BST([4,6,7,9,2,1,3,5,8])
tree.pre_order(tree.root)
print(" ")
tree.in_order(tree.root)
print(" ")
tree.post_order(tree.root)
print(" ")
'''
4, 2, 1, 3, 6, 5, 7, 9, 8,
1, 2, 3, 4, 5, 6, 7, 8, 9,
1, 3, 2, 5, 8, 9, 7, 6, 4,
'''
# 查询操作
li = list(range(0, 500, 2))
random.shuffle(li)
tree = BST(li)
print(tree.query_no_rec(4).data)
# 4
'''
4.9  二叉搜索树的效率

  平均情况下,二叉搜索树进行搜索的时间复杂度为O(nlgn)

  最坏情况下,二叉搜索树可能非常偏斜,如下图所示:

解决方案

  1. 随机化传入
  2. AVL树

python常用算法(5)——树,二叉树与AVL树(三)https://developer.aliyun.com/article/1542700

相关文章
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
|
4天前
|
搜索推荐 C++ Python
Python排序算法大PK:归并VS快速,谁才是你的效率之选?
【7月更文挑战第13天】归并排序** 使用分治法,稳定且平均时间复杂度O(n log n),适合保持元素顺序和并行处理。
13 5
|
5天前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
【7月更文挑战第12天】归并排序是高效稳定的排序算法,采用分治策略。Python 实现包括递归地分割数组及合并已排序部分。示例代码展示了如何将 `[12, 11, 13, 5, 6]` 分割并归并成有序数组 `[5, 6, 11, 12, 13]`。虽然 $O(n log n)$ 时间复杂度优秀,但需额外空间,适合大规模数据排序。对于小规模数据,可考虑其他算法。**
25 4
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
|
4天前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
10 1
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现GBDT(梯度提升树)分类模型(GradientBoostingClassifier算法)并应用网格搜索算法寻找最优参数项目实战
Python实现GBDT(梯度提升树)分类模型(GradientBoostingClassifier算法)并应用网格搜索算法寻找最优参数项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现WOA智能鲸鱼优化算法优化支持向量机回归模型(LinearSVR算法)项目实战
Python实现WOA智能鲸鱼优化算法优化支持向量机回归模型(LinearSVR算法)项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现SSA智能麻雀搜索算法优化支持向量机回归模型(SVR算法)项目实战
Python实现SSA智能麻雀搜索算法优化支持向量机回归模型(SVR算法)项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现SSA智能麻雀搜索算法优化支持向量机分类模型(SVC算法)项目实战
Python实现SSA智能麻雀搜索算法优化支持向量机分类模型(SVC算法)项目实战