【零基础】学python数据结构与算法笔记11

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

文章目录

前言

学习python数据结构与算法学习常用的算法
b站学习链接

65.树的概念

之前讲推排序时学过这个树的概念
【零基础】学python数据结构与算法笔记4
这个树我单拎出来一个节点就是一个树B是一个子树EIJPQ也是一个子树。

在这里插入图片描述

66.树的实例模拟文件系统

模拟linux系统里的文件系统
Linux 文件与目录管理
命令mkdir
ls
cd
先建立树的一个节点
然后用树实现文件系统一个文件夹下有几个文件夹。
在这里插入图片描述
进入usr文件夹下下有python一个子文件夹

在这里插入图片描述
…/ 返回上一级根目录[var/, bin/, usr/]
在这里插入图片描述

67.二叉树的概念

二叉树链式存储将二叉树的节点定义为一个对象节点之间通过类似链表的链接方式来连接。
之前堆排序里讲的是完全二叉树只有右边少数这里讲的不是完全二叉树。
比方说这样一颗树
在这里插入图片描述
只有左孩子和右孩子如下定义找根节点的左孩子的右孩子的数据为C
在这里插入图片描述

68.二叉树的遍历

二叉树遍历方式有4种
前序遍历EACBDGF
中序遍历ABCDEGF
后序遍历BDCAFGE
层次遍历EAGCFBD

在这里插入图片描述
前序遍历
是写打印根节点再打印左孩子再打印右孩子吗用递归写出

在这里插入图片描述
先是根节点E,再是左节点A,A没有左节点然后右节点C,然后左节点B,右节点D,左树遍历完了然后右树先是G没有左节点最后右节点F。
在这里插入图片描述
中序遍历
先是左孩子再是根节点再是右孩子根节点在中间和前序遍历只是顺序不同

在这里插入图片描述
先是左孩子A然后看CBD这个树的左孩子是B,然后根节点C,然后右节点D,再是整个树的根节点E,最后右节点G,再是F

在这里插入图片描述
后序遍历
先是左孩子然后右孩子最后根节点。

在这里插入图片描述
先看左孩子这一侧ACBD子树再看BCD子树先是左孩子B,再是右孩子D,最后根节点C,然后ACBD的根节点A,看GF树左孩子没有右孩子F,根节点G,最后大树的根节点E。

在这里插入图片描述
这三种面试的时候经常会考还会考一种知道前序排序和中序排序画树和后序排序还有知道中序排序和后序排序画树和前序排序。

层次排序
按照一层一层打印不是二叉树也可以按照此方法
思路如下使用队列先进队根节点然后出根节点如果有左孩子或者右孩子就进队然后再出此时的根节点进左右孩子直到队出完就遍历完了。就和之前学的广度优先搜索差不多。【零基础】学python数据结构与算法笔记9中的队列实现迷宫问题
在这里插入图片描述

69.二叉搜索树的概念。

二叉搜索树是一颗二叉树且满足性质设x是二叉树的一个节点。如果y是x左子树的一个节点那么y.key<=x.key;如果y是x右子树的一个节点那么y.key>=x.key。
二叉搜索树的操作查询、插入、删除
在这里插入图片描述
比方说查11先看1711比17小看17的左子树511比5大看5的右子树是11找到。
比方说插入32先看1732比17大看右子树36比36小看29比29大所以在29的右子树上。
查询和插入都是折半的操作所以大概是logn,删除操作比较复杂待会说。

70.二叉搜索树插入

根据刚刚所说写出二叉搜索树的插入

#二叉搜索树
class BiTreeNode:
    def __init__(self,data):
        self.data = data
        self.lchild = None #左孩子
        self.rchild = None #右孩子
        self.parent = None  
class BST:#binary search tree
    def __init__(self,li= None):
        self.root = None
        if li:
            for val in li:
                self.insert_no_rec(val)
                #self.root = self.insert(self.root,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 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=',')

发现中序遍历是升序的排序因为正好符合二叉搜索树的定义左边最小中间根大右边最大。
在这里插入图片描述

71.二叉搜索树查询

递归算法比不递归的慢也比较难理解。

在这里插入图片描述
递归形式
在这里插入图片描述
非递归形式
在这里插入图片描述
查3就查不到
在这里插入图片描述

72.二叉搜索树删除

分三种情况讨论
1.如果要删除的节点是叶子节点直接删除

在这里插入图片描述
2.如果删除的节点只有一个孩子将此节点的父亲与孩子连接然后删除该节点
在这里插入图片描述
有一个特殊情况假设现在只有17352938四个节点要删除的是这个17这个根那就需要重新更新根节点。
3.如果要删除的节点有两个孩子将其右子树的最小节点该节点最多有一个右孩子删除并替换当前节点。或者说是左子树的最大节点删除并替换

在这里插入图片描述

73.二叉搜索树删除实现

先分情况写__remove_node_1
__remove_node_21
__remove_node_21
第三种写在delete里
第二种实现有点像双链表的删除实现画个图会好理解点。

总的代码如下

#二叉搜索树
class BiTreeNode:
    def __init__(self,data):
        self.data = data
        self.lchild = None #左孩子
        self.rchild = None #右孩子
        self.parent = None  
class BST:#binary search tree
    def __init__(self,li= None):
        self.root = None
        if li:
            for val in li:
                self.insert_no_rec(val)
                #self.root = self.insert(self.root,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:#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: #val大
                p = p.rchild
            elif p.data >val:
                p = p.lchild
            else: #找到了
                return p
        return None#找不到 return None
    def __remove_node_1(self,node): #加两下划线表示是类的内置函数
        #情况1node是叶子节点
        if not node.parent: #如果删除的是根节点
            self.root = None
        if node ==node.parent.lchild:  #node是它父亲的左孩子
            node.parent.lchild  = None #删除左节点
        else:  #右孩子
            node.parent.rchild = None
    def __remove_node_21(self,node):
        #情况2.1node只有一个左孩子
        if not node.parent: #如果删除的node是根节点
            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.2node只有一个右孩子
        if not node.parent: #如果删除的node是根节点
            self.root = node.rchild  #先连到根节点
            node.lchild.parent = None #再把自己删了
        elif node == node.parent.lchild: #如果删除的node是左孩子
            node.parent.lchild = node.rchild #把自己的右孩子连到自己根节点的左孩子上
            node.rchild.parent = node.parent #把自己的根节点连到自己右孩子的父节点上
        else:  #如果删除的node是右孩子
            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 #把数据赋给node
                # 然后删除min_node
                if min_node.rchild: #如果只有一个右孩子
                    self.__remove_node_22(min_node)
                else: #或者没有
                    self.__remove_node_1(min_node)            
    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=',')

最后成功删除
在这里插入图片描述

总结

学习了二叉树和二叉搜索树的基本实现。

文章目录

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
标签: python
返回列表

上一篇：复试算法练习Day07

下一篇：十九、命令模式 ( Command Pattern )

“【零基础】学python数据结构与算法笔记11” 的相关文章

selenium用法详解【从入门到实战】【Python爬虫】【4万字】_selenium实战1年前 (2023-02-02)
如何将列表转换为字符串Python？_将列表转换为字符串1年前 (2023-02-02)
【BSC】使用Python玩转PancakeSwap（入门篇）1年前 (2023-02-02)
Anaconda安装与Python虚拟环境配置保姆级图文教程(附速查字典)1年前 (2023-02-02)
仅需一行Python代码，为图片上版权！1年前 (2023-02-02)
用Python的内置包Tkinter写一个练习系统2.01年前 (2023-02-02)
Python之argparse模块的使用1年前 (2023-02-02)
Python 文本文件处理 投资记录文件格式转换1年前 (2023-02-02)
安装python1年前 (2023-02-02)
Python学习中的六个技巧小结1年前 (2023-02-02)

阿里云国际版