二叉树添加删除节点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对象引用方式实现指针结构的创建。