二叉树添加删除节点Python

一棵二叉树,每一个节点都有左子树和右子树,二叉树的操作都可以递归的调用子树来完成。在C中有指针的概念,子树用指针实现,函数用指针作为参数。但是,Python采用对象引用,对空对象赋值,只在函数作用范围内有效,并不会生成一个新节点。如果是删除过程,那么仅传递的变量被指向空,也不会改变树的链式结构。

二叉树添加删除节点

  • 问题说明,添加节点伪代码:
node = root
insert(node)
def insert(node):
     if node == None:
        node = Node(key,value) 
        ## node赋值后不再代表父节点的子节点,而是指向一个新的对象
        ## 插入失败
    else:
        node = node.chlid
        insert(node)
  • 问题说明,删除节点说明
node = root
delete(node)
def delete(node,key):
    if node.key == key:
        node == None
        ## node 指向None常量,而原节点不变
        ## 删除失败
    else:
        node = node.child
        delete(node)

用函数返回值,解决以上问题。注意以下递归调用的函数都return node

插入节点

    def insert(self,key,value):
        self.root = self._insert(self.root,key,value)
    def _insert(self,node,key,value):
        if(node==None):
            self.count= self.count+1
            node = Node(key,value)
            return node
        elif(node.key > key):
            node.lnode = self._insert(node.lnode,key,value)
            return node
        else:
            node.rnode = self._insert(node.rnode,key,value)
            return node

删除节点

def removekey(self,key):
    #self.root=self._removekey(self.root,key)
    self.root = self._remove(self.root,key)
def _remove(self,node,key):
    if(node.key == key):        
        if(node.rnode!= None):
            node.rnode,key,value = self.delmin(node.rnode)
            newnode = Node(key,value)
            newnode.rnode = node.rnode
            newnode.lnode = node.lnode
            return newnode
        elif(node.lnode!=None):
            node.lnode,key,value = self.delmax(node.lnode)
            newnode = Node(key,value)
            newnode.rnode = node.rnode
            newnode.lnode = node.rnode
            return newnode
        else:
            self.count = self.count -1
            return None
    elif(node.key > key):
        node.lnode = self._remove(node.lnode,key)
        return node
    else:
        node.rnode = self._remove(node.rnode,key)
        return node

删除节点算法

  1. 如果左子树不为空,用左子树最大值替换该节点,并删除左子树中最大值节点。
  2. 如果右子树不为空,用右子树最小值替换该节点,并删除右子树中最小值节点。
  3. 如果左右子树都为空,直接删除该节点。

此算法默认优先删除左子树,会造成二叉树不平衡

def delmin(self,node):
    if(node.lnode == None):
        self.count = self.count-1
        return node.rnode,node.key,node.value
    else:
        node.lnode,key,value = self.delmin(node.lnode)
        return node,key,value
def delmax(self,node):
    if(node.rnode == None):
        self.count = self.count-1
        return node.lnode,node.key,node.value
    else:
        node.rnode,key,value= self.delmax(node.rnode)
        return node,key,value

总结:

采用递归调用实现二叉树添加、删除节点。文章采用Python对象引用方式实现指针结构的创建。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏武培轩的专栏

剑指Offer-第一个只出现一次的字符位置

题目描述 在一个字符串(1<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置 思路 思路一: 使用整型数组对出现次数进行...

3879
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-18(02)总结Map,HashMap,HashMap与Hashtable区别,Collections工具类

(8)Hashtable和HashMap的区别? package cn.itcast_07; import java.util.Hashtable; /* *...

3005
来自专栏mathor

堆及其相关应用

 提到堆就不得不说到二叉树这个结构,堆就是一颗完全二叉树,什么叫完全二叉树,用一句话来概括就是:设二叉树的深度为h,除第h层外,其它各层的结点数都达到最大个数,...

962
来自专栏LinkedBear的个人空间

唠唠SE的集合-03——List接口 原

有序的 collection(也称为序列)。此接口的用户可以对列表中每个元素的插入位置进行精确地控制。

833
来自专栏用户3030674的专栏

java类集框架(ArrayList,LinkedList,Vector区别)

主要分三类:集合(set)、列表(List)、映射(Map) 1.集合:没有重复对象,没有特定排序方式 2.列表:对象按索引位置排序,可以有重复对象 3.映射...

2052
来自专栏小筱月

java map遍历、排序,根据value获取key

若要取 map 中 value 的最大值 或 与之对应的 key(整型或浮点型):可利用list

5832
来自专栏书山有路勤为径

逆序数(二叉查找树)

已知数组nums,求新数组count,count[i]代表了在nums[i]右侧且比nums[i]小的元素个数。 例如: nums = [5,2,6,1],...

713
来自专栏专注 Java 基础分享

从源码看集合ArrayList

     可能大家都知道,java中的ArrayList类,是一个泛型集合类,可以存储指定类型的数据集合,也知道可以使用get(index)方法通过索引来获...

1896
来自专栏陈树义

3.Java集合总结系列:Set接口及其实现

一、Set接口 Set 接口与 List 接口相比没有那么多操作方法,比如: 1、List 接口能直接设置或获取某个元素的值,而Set接口不能。 2、List ...

3975
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题17合并两个排序的链表

本题的详细解析均在代码注释中: /** * 题目:输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。 * @author 大闲人...

3987

扫码关注云+社区

领取腾讯云代金券