首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

在Python中删除二叉树节点。为什么是self != parent.left还是parent.right?

在Python中删除二叉树节点时,判断要删除的节点是父节点的左子节点还是右子节点,可以通过比较节点对象的引用来确定。通常情况下,我们会使用self != parent.leftself != parent.right来判断。

这是因为在二叉树中,每个节点都有一个指向父节点的引用,通常称为parent。当我们要删除一个节点时,需要首先找到该节点在树中的位置,并且知道它的父节点是谁。

假设要删除的节点是self,我们需要判断它是父节点的左子节点还是右子节点。如果self等于parent.left,则说明self是父节点的左子节点;如果self等于parent.right,则说明self是父节点的右子节点。

这样的判断是为了确定要删除的节点在树中的位置,以便在删除节点后,正确地调整树的结构。

以下是一个示例代码,演示了如何在Python中删除二叉树节点:

代码语言:txt
复制
class TreeNode:
    def __init__(self, val=0, left=None, right=None, parent=None):
        self.val = val
        self.left = left
        self.right = right
        self.parent = parent

def delete_node(node):
    parent = node.parent

    if parent is None:
        # 如果要删除的节点是根节点,则直接将根节点置为None
        node = None
    elif node == parent.left:
        # 如果要删除的节点是父节点的左子节点
        parent.left = None
    elif node == parent.right:
        # 如果要删除的节点是父节点的右子节点
        parent.right = None

    # 其他删除操作,例如释放节点内存等

# 示例用法
root = TreeNode(1)
left_child = TreeNode(2, parent=root)
right_child = TreeNode(3, parent=root)
root.left = left_child
root.right = right_child

delete_node(left_child)

在上述示例中,我们定义了一个TreeNode类来表示二叉树的节点。每个节点包含一个val值、左子节点left、右子节点right和父节点parent

delete_node函数用于删除节点。首先获取要删除节点的父节点parent,然后根据selfparent.leftparent.right的比较结果,判断要删除的节点是父节点的左子节点还是右子节点,并进行相应的删除操作。

请注意,上述示例仅演示了删除节点的基本操作,并未涉及到具体的云计算、IT互联网领域的知识。如果需要进一步了解与云计算相关的内容,可以参考腾讯云的相关产品和文档。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

Python 实现二叉树的增、删、查

今天的我们的目标使用 Python 来实现一棵二叉树。 二叉查找树、平衡二叉查找树、红黑树、递归树后面也会实现,请保持关注。...二叉树即可以使用链式存储,也可以使用数组来存储,而完全二叉树使用数据存最省内存的一种结构。 接下来我们使用 Python 实现链式存储的二叉树。...如果父节点不为空, 判断 item 的左右子树,如果左子树为空,那么判断 item 节点的左孩子,还是右孩子,如果左孩子,将父节点的左指针指向 item 的右子树,反之将父节点的右指针指向 item...的右子树,如果右子树为空,那么判断 item 节点的左孩子,还是右孩子,如果左孩子,将父节点的左指针指向 item 的左子树,反之将父节点的右指针指向 item 的左子树,如果左右子树均不为空,..., item): ''' 从二叉树删除一个元素 先获取 待删除节点 item 的父节点 如果父节点不为空, 判断

1.2K10

七十六、 数据结构二叉树及其代码实现

上图中,编号1普通二叉树,编号2又是满二叉树,编号2又是完全二叉树。 满二叉树一棵二叉树。如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。...序遍历就是从二叉树的根结点出发,当第二次到达结点时就输出结点数据,按照先向左向右的方向访问。 后序遍历就是从二叉树的根结点出发,当第三次到达结点时就输出结点数据,按照先向左向右的方向访问。...item 的左右子树 如果左子树为空,那么判断 item 节点的左孩子,还是右孩子,如果左孩子,将父节点的左指针指向 item 的右子树,反之将父节点的右指针指向 item...的右子树 如果右子树为空,那么判断 item 节点的左孩子,还是右孩子,如果左孩子,将父节点的左指针指向 item 的左子树,反之将父节点的右指针指向 item 的左子树...: [2, 7, 8, 'root', 4, 1, 5] 后序遍历: [7, 2, 8, 4, 5, 1, 'root'] Binarytree一个Python库,它通过一个简单的API生成二叉树

41010
  • 详细理解平衡二叉树AVL与Python

    ’skii和Landis 满足高度平衡属性的二叉树就是AVL树 高度平衡属性:对于树的每一个位置p,p的孩子的高度最多相差1 很显然前言中的第一个图并不满足高度平衡属性,第二个满足的。...保持二叉树的高度平衡属性 要保持高度平衡属性的原因破坏了高度平衡属性 破坏的方式有两种:添加节点删除节点 添加节点如图: ?...删除10的时候也会破坏高度平衡属性 最后,不论添加节点还是删除节点,都会使树变成非高度平衡的状态,这种非高度平衡的状态有4种: 1.LL ?...RL同样LR的相反模式,先将22、25、30、40这棵子树进行LL旋转,再将整棵树进行RR旋转 理解了avl保持平衡从方式后,就可以用代码来实现了 Python实现 我们使用AVL对上一篇文章的有序映射进行优化..._rebalanced_delete(parent) 实现4种平衡策略时,一定要记着将整棵树的根节点更新,不然遍历的时候,根节点指的就不是真正的根节点了。 ​

    60920

    二叉树搜索树面试题,你知道吗?

    原文出处:码出高效面试的程序媛 - 励志分享一万道面试题的程序媛 二叉树,搜索二叉树算法面试的必面题。聊聊面试点: 一、树 & 二叉树 树的组成为节点和边,节点用来储存元素。...节点组成为根节点、父节点和子节点。 如图:树深 length 为 4;根节点的值为 5 ;父子节点关系:值为 8 和 值为 3 的节点 理解了树,那什么二叉树?...二叉树的场景很多,比如用来表示算术表达式等等。 如图:值为 1 或者 8 的节点节点;值为 2 或 3 的节点节点; 二、二叉搜索树 BST 上面理解了二叉树,那么搜索二叉树就好理解了。...root = null; } // 左子树 if (isLeftChild == true) { parent.left = null; }...二叉树 的,后面面试点 搜索二叉树 的。

    18620

    二叉排序树(BST)

    二叉排序树(Binary Sort Tree) 前言: 二叉排序树二叉树十分重要的一种,又称二叉查找树(Binary Search Tree),亦称二叉搜索树。数据结构的一类。...node; }else{ this.right.add(node); } } } //序遍历二叉树...,并且left 和 right 都不为空 处理这三种情况之前,先再Node节点增添方法,用来查询要删除的目标节点targetNode 以及targetNode的父节点 parent节点 代码如下:...步骤:【 找到目标节点targetNode 及其它的父节点 parent 确定targetNodeparent的left节点 还是right 节点 parent.left = null 或 parent.right...targetNodeparent的左节点;—–>parent.left = targetNode.right; ​ targetNode 有右节点 ,targetNodeparent的右节点;—–

    8010

    【数据结构】关于二叉搜索树,你知道如何实现增删模拟吗???(超详解)

    ️1.二叉搜索树 1.1概念: 二叉搜索树又称二叉排序树,它或者一棵空树,或者具有以下性质的二叉树: • 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 • 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值...• 它的左右子树也分别为二叉搜索树 1.2二叉树图片: 如上图,二叉搜索树的左子树都满足小于根结点的值,而右子树都满足大于根结点的值;并且序遍历时可以发现数据一个由小到大排列的数据。 ️...4.二叉搜索树的删除模拟 4.1思路分析 删除的过程我们要讨论如下几点情况: 设待删除结点为 cur, 待删除结点的双亲结点为 parent 1.当 cur.left == null时:...= null时: 需要使用替换法进行删除,即在它的右子树寻找序下的第一个结点(关键码最小),用 它 的值填补到被删除节点中,再来处理该结点的删除问题 4.2画图演示 4.3...进行删除操作的时候,如果删除结点的左右树都不为空,那么此时我们要进行找到替罪羊的方法,找到左边或者右边的其中之一的替罪羊,但是由于改变节点,需要管理其子结点,所以这里的删除并不是真正意义上的删除,其实是赋值替罪羊的值过后

    6810

    经典算法之二叉搜索树

    二叉树(Binary Tree) 二叉树(Binary Tree)一种特殊的树类型,其每个节点最多只能有两个子节点。...(delete) 删除节点二叉搜索树,最复杂的一种操作,但是也不是特别难,我们分类讨论: 1、要删除节点有零个孩子,即叶子节点 ?...如图所示,只需要将parent.left(或者parent.right)设置为null,然后Java垃圾自动回收机制会自动删除current节点。 2.要删除节点有一个孩子 ?...如图所示,只需要将parent.left(或者parent.right)设置为curren.right(或者current.left)即可。 ?...3、要删除节点有两个孩子 这种情况比较复杂,首先我们引入后继节点的概念,如果将一棵二叉树按照序周游的方式输出,则任一节点的下一个节点就是该节点的后继节点

    74031

    【Java】基础篇-排序二叉树

    技术变,年龄变,但唯一不变的还是我们的核心技术:Linux、C、TCP\IP这些,不管上层建筑如何变化,都只是底层基础上封装。...{ //设置为左子节点 parent.left = newNode; } } 删除 排序二叉树删除要稍...= null && node.right == null) { //被删除节点节点的左节点 if (node == parent.left) { //父节点的左子节点就是当前节点的左子节点...AVL 算法插入和删除节点时,会根据一次或者多次旋转来重新平衡树。当然我们这篇的例子没有写重要的保持平衡算法,只是给大家先回忆一下。之后会在专门的数据结构篇给大家讲解。...比如,最短路径 3 -> 1 的 2 最长路径3 -> 9 -> 15 ->16 的4 。正好2倍。 染色 & 旋转 我们这里只说下红黑树的核心-旋转操作 还是如图 ?

    74030

    二叉排序(查找)树(Java实现)

    其定义为:二叉排序树或者一棵空树,或者具有如下性质的二叉树。...删除只有一颗子树的节点: 1、需要先找到要删除节点targetNode 2、找到targetNode的父节点parent 3、确定targetNode的子节点左子节点还是右子节点 4、targetNode...parent的左子节点还是右子节点 5、如果targetNode有左子节点 5.1、如果targetNodeparent的左子节点 parent.left = targetNode.left;...,将最小(大)节点的值保存该变量 4、删除该最小节点 5、targetNode.value = temp 二叉排序树的特性 根据二叉排序树的定义(左子树小于根节点,右子树大于根节点),根据二叉树序遍历的定义...== null && targetNode.right == null) { //判断删除节点节点的左子节点还是右子节点 if(parent.left

    35830

    据结构与算法(十) AVL树

    平衡二叉树来源 二叉搜索树的复杂度分析 和高度有关 O(h) = O(logn) 最坏复杂度从小到大添加节点 (和链表差不多) O(h) = O(n) 如何二叉搜索树退化成链表??...让添加删除搜索的复杂度维持logn 平衡(Balance) 当节点固定时,左右字数高度就越接近,这颗二叉树就越平衡 理想平衡 最理想的平衡,例如 完全二叉树,满二叉树 如何改进二叉搜索树 因为无法改变添加删除顺序...(用户操作决定),所以每次操作之后,让二叉树达到平衡状态。...、HashMap、HashSet•Linux 的进程调度•Ngix的timer 一般称他们为:自平衡的二叉搜索树(Self-Balance Binary Search Tree) AVL树 介绍: 最早发明的自平衡二叉树之一...解决方式: 删除后进行平衡操作 删除 让父节点恢复失衡后,可能导致更高节点的祖先接点失衡(最多需要log(n)次调整) 添加: 添加会导致所有祖先节点都失衡 处理:只要让最低失衡节点回复平衡,整棵树就恢复平衡

    57120

    【图解数据结构】二叉查找树

    我们都知道二叉查找树的结点可分为:没有子节点节点,带有一个子节点节点 ,带有两个子节点节点 。那么可以将二叉查找树的删除节点操作简单拆分一下,以便于我们的理解。如下图: ?...代码实现: //要删除的结点带有一个子节点节点的处理 //首先判断子结点左子节点还是右子节点,然后再判断当前节点左子节点还是右子节点 else if (current.Right == null...这里我们需要了解一下后继节点的定义。 一个节点的后继节点指,这个节点序遍历序列的下一个节点。相应的,前驱节点指这个节点序遍历序列的上一个节点。...举个例子,下图中的二叉树序遍历序列为: DBEAFCG,则A的后继节点为F,A的前驱节点为E。 ?...因为 successor.Right节点39,所以节点40的左子节点变成了节点39。其它操作和上一种情况完全相同。 完成删除节点后的搜索二叉树变为: ?

    50720

    Python实现数据结构之树

    树 树由根结点和若干颗子树构成的。树由一个集合以及该集合上定义的一种关系构成的。集合的元素称为树的结点,所定义的关系称为父子关系。父子关系树的结点之间建立了一个层次结构。...这个内嵌类目前也是抽象类,具体方法都没有实现,但使用它的目的已经有了,就是将树节点进行封装,那为什么要封装节点呢?...,以右孩子为根节点形成的树叫做右子树 如果除了最下面的一层节点,其余节点组成的一颗满二叉树,并且最下面的这层节点遵循从左到右依次添加的顺序,那么这个树就叫做完全二叉树 非空完全二叉树,外部节点数...但是我们还需要掌握一个算法,就是树的遍历算法 树的遍历 树的遍历一般有先序遍历,后序遍历,广度优先遍历(层序遍历),对于二叉树还有序遍历 先序遍历 先序遍历按照根节点->从左到右的孩子节点的顺序遍历...总而言之,代码理解的难度还是由于递归算法造成的,一个复杂的递归终归还是不是那么容易就能看出来的。 后序遍历 后序遍历按照先从左到右孩子节点->根节点,如图: ?

    1.1K20

    数据结构与算法(十五):二叉排序树

    /右子节点是否存在,存在就继续递归遍历左/右树直到找到插入位置,否则直接插入 节点添加方法: /** * 添加节点 * @param parent 父节点 * @param node 要添加的节点...3.1删除节点叶子结点 即方法deleteLeafNode() 找到要删除节点,并判断其左右子节点是否都为空 若都为空,再找到其父节点,然后判断要删除节点节点的左子节点还是右子节点 /**...parent) { //判断目标节点节点节点还是节点 if (parent.right !...; } } 3.2删除节点有一课子树 即方法deleteOneBranchNode() 找到目标节点,判断目标节点有的那颗子树左子树还是右子树 判断目标节点是否为根节点,如果就直接将根节点替换为目标节点的子节点...deleteLeafNode(int val, BinarySortTreeNode parent) { //判断目标节点节点节点还是节点 if (parent.right

    57910

    《Java初阶数据结构》----10.<Map和Set---TreeSet和TreeMap&HashSet和HashMap >

    一、二叉搜索树(二叉排序树) 二叉搜索树又称二叉排序树,它或者一棵空树,或者具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值...我们可以看出查找的效率很高的  1.2二叉树的插入 注:二叉搜索树的插入只会插入进叶子节点。...1.3二叉树删除(难点) 设待删除结点为 cur, 待删除结点的双亲结点为 parent。...分以下三种情况进行删除 1. cur.left == null 1. cur root,则 root = cur.right 2. cur 不是 root,cur parent.left,则 parent.left...= null 需要使用替换法进行删除,即在它的右子树寻找序下的第一个结点(关键码最小),用它的值填补到被 删除节点中,再来处理该结点的删除问题 public void remove(

    8810

    二叉排序树(BST)优秀树结构的基石

    的 父结点 parent 确定 targetNode parent 的左子结点 还是右子结点 根据前面的情况来对应删除 左子结点 parent.left = null 右子结点 parent.right...的子结点左子结点还是右子结点 targetNode parent 的左子结点还是右子结点 如果 targetNode 有左子结点 如果 targetNode parent 的左子结点...parent.left = targetNode.left; 如果 targetNode parent 的右子结点 parent.right = targetNode.left; 如果 targetNode...有右子结点 如果 targetNode parent 的左子结点 parent.left = targetNode.right 如果 targetNode parent 的右子结点 parent.right...== null && targetNode.right == null) { // 判断targetNode节点的左子节点还是右子节点

    18830

    【数据结构】二叉搜索树的功能实现详解

    二叉搜索树二叉搜索树又称二叉排序树,它或者一棵空树,或者具有以下性质的二叉树:若它的左子树不为空,则左子树上所有节点的值都小于根节点的值若它的右子树不为空,则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树图片其中序遍历一颗有序的树查找二叉搜索树的查找效率非常高因为二叉搜索树的左边都比我小...parent.left = cur.left; } else { // 2.3 要删除的 cur parent 的右节点 parent.right...要删除节点的左右孩子都不为空需要使用 替换法 进行删除它的右子树寻找一个最小的节点,用它的值填补到被删除节点中,再来处理该结点的删除问题因为要删除节点 cur 左边都比它小,右边都比它大,所以就在...(既然此节点最小的,就不可能还有左子树,因为左子树肯定比此节点小)图片在它的左子树寻找一个最大的节点,用它的值填补到被删除节点中,再来处理该结点的删除问题此时这个最大值一定是左树的最右边,意味着它肯定没有右子树所以找到最小值的特征...== null 的时候,t 就是最小值tp 用来定位 t 的父节点的,方便后续对节点进行删除(因为节点删除都要依靠删除节点的父节点进行“改变连接对象”)没找到最小节点之前,tp 和 t 一起进行移动

    10410

    数据结构之AVL树的 “奥秘“

    二叉树查询性能分析: 插入和删除操作都必须先查找,查找效率代表了二叉搜索树各个操作的性能 对有n个结点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索二叉搜索树树平均查找长度结点的深度的函数...二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于顺 序表搜索元素,效率低下。...= null) { //先看curparent的左边还是右边 if (cur == parent.right) { //...(了解): 1、找到需要删除节点 2、按照搜索树的删除规则删除节点--参考Map和Set及哈希--的奥秘(详解)-CSDN博客中二叉搜索树的删除 3、更新平衡因子,如果出现了不平衡,进行旋转...但是如果要对AVL树做一些结构修改的操作,性能非常低下,比如:插入时要 维护其绝对平衡,旋转的次数比较多,更差的删除时,有可能一直要让旋转持续到根的位置。

    10010
    领券