一棵二叉树,每一个节点都有左子树和右子树,二叉树的操作都可以递归的调用子树来完成。在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)
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
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对象引用方式实现指针结构的创建。