技术标签: 算法 python python数据结构 数据结构
二叉搜索树事一颗二叉树且满足性质:设x是二叉搜索树的一个节点,如果y是x左子树的一个节点,那么y.key <= x.key,如果y是x右子树的一个节点,那么y.key >= x.key。通俗的讲就是,树中每一个节点的左子树里面的所有节点都比该节点小,但是该节点的右子树里面的所有节点都比该节点大(简称:左小右大)。
二叉搜索树完全代码:
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_sec(val)
def insert(self,node,val): # 使用递归的方式插入
if not node : # 如果要插入的节点node为空,就创建一个节点,内容是val,其实这个是递归的终止条件,在最后的时候把我们要插入的值先变成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)
return node # 一般不考虑相等的情况
def insert_no_sec(self,val): # 不使用递归的方式插入
p = self.root
if not p: # 是否为空,空则创建一个node节点
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: # 终止条件,找不到就返回None
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):
# 情况1:node是叶子节点
if not node.parent:
self.root = None
if node == node.parent.lchild:
node.parent.lchild = None
else:
node.parent.rchild = None
def __remove__node_21(self,node):
# 情况2:node只有一个左孩子
if not node.parent:
self.root = node.lchild
node.lchild.parent = None
elif node == node.parent.lchild:
node.parent.lchild = node.lchild
node.lchild.parent = node.parent
else:
node.parent.rchild = node.lchild
node.lchild.parent = node.parent
def __remove__node__22(self,node):
# 情况3: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: # 两个孩子都有
min_node = node.rchild
while min_node.lchild:
min_node = min_node.lchild
node.data = 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)
# 主函数
tree = BST([5,6,3,4,2,1,7,8])
# 插入
tree.pre_order(tree.root)
print("")
tree.in_order(tree.root) # 从小到大排序
print("")
tree.post_order(tree.root)
print("")
# 查询
import random
li = list(range(0,500,2))
random.shuffle(li)
tree = BST(li)
print(tree.query_no_rec(102).data)
tree = BST([5,6,3,4,2,1,7,8])
tree.in_order(tree.root)
print("")
tree.delete(3)
tree.in_order(tree.root)
# 输出
5,3,2,1,4,6,7,8,
1,2,3,4,5,6,7,8,
1,2,4,3,8,7,6,5,
102
1,2,3,4,5,6,7,8,
1,2,4,5,6,7,8,
我们通过自行画图可以画出二叉搜索树的结构,如下:
我们从输出中也可以发现,二叉搜索树的中序遍历得到的是从小到大的排序。
除了我们通过输入列表画图可以得到上面的图之外,我们还可以通过输出的三种排序方式,自行画出上图,这又是另外的一个考点。
如果是已经拥有的树,则根据二叉搜索树的逻辑去进行比较插入:比节点的值大,就往右子树的方向去查找;比节点的值小就往左子树的方向去查找。
def insert(self,node,val): # 使用递归的方式插入
if not node : # 如果要插入的节点node为空,就创建一个节点,内容是val,其实这个是递归的终止条件,在最后的时候把我们要插入的值先变成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)
return node # 一般不考虑相等的情况
def insert_no_sec(self,val): # 不使用递归的方式插入
p = self.root
if not p: # 是否为空,空则创建一个node节点
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: # 终止条件,找不到就返回None
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
二叉搜索树删除情况有三种:
1、删除的节点是叶子节点。我们直接delete;
2、删除的节点不是叶子节点,且只有一个孩子节点。我们把节点的父节点和孩子节点连接到一起,再把该节点delete;
3、删除的节点不是叶子节点,且有两个孩子节点。我们有两种方式去实现,第一种是将该节点delete,再找到左子树中最大的节点,将其进行替换;第二种是将该节点delete,再从右子树找到最小的节点,替换当前节点。(我们这里使用第二种情况)
def __remove__node_1(self,node):
# 情况1:node是叶子节点
if not node.parent: # 判断是否为根节点
self.root = None
if node == node.parent.lchild: # 如果是左孩子就删除为None
node.parent.lchild = None
else: # 如果是右孩子就删除为None
node.parent.rchild = None
def __remove__node_21(self,node):
# 情况2:node只有一个左孩子
if not node.parent: # 判断是否为根节点
self.root = node.lchild
node.lchild.parent = None
elif node == node.parent.lchild: # 如果是父节点的左孩子,将父亲与孩子节点联系到一起
node.parent.lchild = node.lchild
node.lchild.parent = node.parent
else: # 如果是父节点的右孩子,将父亲与孩子节点联系到一起
node.parent.rchild = node.lchild
node.lchild.parent = node.parent
def __remove__node__22(self,node):
# 情况3: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: # 两个孩子都有
# 情况4(第三种可能)
min_node = node.rchild # 使用右孩子节点
while min_node.lchild: # 存在左孩子节点的话
min_node = min_node.lchild
node.data = min_node.lchild
node.data = min_node.data
# 删除min_node,因为最小的树就是被删除节点的右孩子节点一直寻找左孩子,到达最底部的左孩子就是右子树最小的值,这个时候一定只有两种情况,1是这个节点是叶子节点,2是这个节点存在一个右孩子。
if min_node.rchild:
self.__remove__node__22(min_node)
else:
self.__remove__node_1(min_node)
文章浏览阅读3.8k次。1、将下载好的萤石js插件,添加到SoringBoot项目中。位置可参考下图所示。(容易出错的地方,在将js插件在html页面引入时,发生路径错误的问题)所以如果对页面中引入js的路径不清楚,可参考下图所示存放路径。2、将ezuikit.js引入到demo-live.html中。(可直接将如下代码复制到你创建的html页面中)<!DOCTYPE html><html lan..._ezuikit 测试的url
文章浏览阅读322次。第二步,在弹出的对话框选择,设备驱动—>PLC—>莫迪康—>ModbusRTU—>COM,根据配置软件选择的协议选期期,这里以此为例,然后点击“下一步”。第四步,把使用虚拟串口打勾(GPRS设备),根据需要选择要生成虚拟口,这里以选择KVCOM1为例,然后点击“下一步”设备ID即Modbus地址(1-255) 使用DTU时,为下485接口上的设备地址。第六步,Modbus的从机地址,与配置软件相同,这里以1为例,点击“下一步“第五步,Modbus的从机地址,与配置软件相同,这里以1为例,点击“下一步“_组态王ua
文章浏览阅读9.4k次,点赞22次,收藏19次。安装npm相当于安装node.js,Node.js已自带npm,安装Node.js时会一起安装,npm的作用就是对Node.js依赖的包进行管理,也可以理解为用来安装/卸载Node.js需要装的东西_npm安装配置
文章浏览阅读748次,点赞21次,收藏26次。大家好,小编来为大家解答以下问题,python基础训练100题,python入门100例题,现在让我们一起来看看吧!宝子们还在新手村练级的时候,不单要吸入基础知识,夯实自己的理论基础,还要去实际操作练练手啊!由于文章篇幅限制,不可能将100道题全部呈现在此除了这些,下面还有我整理好的基础入门学习资料,视频和讲解文案都很齐全,用来入门绝对靠谱,需要的自提。保证100%免费这不,贴心的我爆肝给大家整理了这份今天给大家分享100道Python练习题。大家一定要给我三连啊~
文章浏览阅读1k次。 为了在 Linux ( Ubuntu) 上安装sublime,一般大家都会选择常见的教程或是 sublime 官网教程,然而在国内这种方法可能失效。为此,需要用安装包安装。以下就是使用官网安装包安装的教程。打开 sublime 官网后,点击右上角 download, 或是直接访问点击打开链接,即可看到各个平台上的安装包。选择 Linux 64 位版并下载。下载后,打开终端,进入安装..._ubuntu 安装sumlime text打不开
文章浏览阅读563次,点赞13次,收藏6次。CrossOver24是一款类虚拟机软件,专为macOS和Linux用户设计。它的核心技术是Wine,这是一种在Linux和macOS等非Windows操作系统上运行Windows应用程序的开源软件。通过CrossOver24,用户可以在不购买Windows授权或使用传统虚拟机的情况下,直接在Mac或Linux系统上运行Windows软件和游戏。该软件还提供了丰富的功能,如自动配置、无缝集成和实时传输等,以实现高效的跨平台操作体验。
文章浏览阅读1.7k次。一个用聊天的方式让ChatGPT帮我写的线程安全的环形List_为什么gpt一写list就卡
文章浏览阅读336次。我们在前面的文章里曾写过Web应用中乱码产生的原因和处理方式,旧文回顾:深度揭秘乱码问题背后的原因及解决方式其中我们提到可以通过Filter的方式来设置请求和响应的encoding,来解..._filterconfig selectencoding
文章浏览阅读651次。转自:http://www.jb51.net/article/36480.htmencodeURI和decodeURI是成对来使用的,因为浏览器的地址栏有中文字符的话,可以会出现不可预期的错误,所以可以encodeURI把非英文字符转化为英文编码,decodeURI可以用来把字符还原回来_js encodeur decodeurl
文章浏览阅读1.9w次,点赞6次,收藏3次。前言在日常的Android开发当中,我们肯定要打包apk。但是今天我打包的时候遇到一个很奇怪的问题Android The destination folder does not exist or is not writeable,大意是目标文件夹不存在或不可写。出现问题的原因以及解决办法上面有说报错的中文大意是:目标文件夹不存在或不可写。其实问题就在我们的打包界面当中图中标红的Desti..._the destination folder does not exist or is not writeable
文章浏览阅读94次。一、配置代码编辑区的样式 <1>打开Eclipse,Help —> Install NewSoftware,界面如下: <2>点击add...,按下图所示操作: name:随意填写,Location:http://eclipse-color-th..._ecplise高大上设置
文章浏览阅读2.8k次。一,下载mysql:http://dev.mysql.com/downloads/mysql/; 打开页面之后,在Select Platform:下选择linux Generic,如果没有出现Linux的选项,请换一个浏览器试试。我用的谷歌版本不可以,换一个别的浏览器就行了,如果还是不行,需要换一个翻墙的浏览器。 二,下载完后解压缩并放到安装文件夹下: 1、MySQL-client-5.6.2_linux mysql 安装 mysql-5.6.24-1.linux_glibc2.5.x86_64.rpm-bundle