您现在的位置是:网站首页> 内容页

【算法】【python实现】二叉搜索树插入、删除、查找

  • 优发官方网站
  • 2019-01-10
  • 496人已阅读
简介二叉搜索树 定义:如果一颗二叉树的每个节点对应一个关键码值,且关键码值的组织是有顺序的,例如左子节点值小于父节点值,父节点值小于右子节点值,则这棵二叉树是一棵二叉搜索树。 类(Tree

二叉搜索树

 

定义:如果一颗二叉树的每个节点对应一个关键码值,且关键码值的组织是有顺序的,例如左子节点值小于父节点值,父节点值小于右子节点值,则这棵二叉树是一棵二叉搜索树。

 

类(TreeNode):定义二叉搜索树各个节点

在该类中,分别存放节点本身的值,以及其左子节点,右子节点,父节点的值。

 

class TreeNode(object): def __init__(selfval): self.value = val #存值 self.left = None #存本节点的左子节点 self.right = None #存本节点的右子节点 self.father = None #存本节点的父节点

  

类(BST):定义二叉搜索树的各种功能方法

此类用于存放定义二叉树的插入,删除,搜索等方法。

class BST(object): def __init__(selfnodeList): self.root = None for node in nodeList: self.bfs_insert(node)

注:self.bfs_insert(node)中的bfs_insert方法在后面实现。放在构造函数中的目的是将一个列表生成一个二叉搜索树列表。

 

方法(bfs_insert):实现插入功能

 第一步:将根节点(self.root)设置成当前位置节点(cur),即从根节点开始遍历。根节点的父节点(father)初始设置为None。 

 

def bfs_insert(selfnode): cur = self.root #设置当前节点为根节点 father = None #设置根节点的父节点为None

  

第二步:查找可以插入的位置

 

1. 当前位置节点(cur)的值与待插入节点(node)的值相等,返回-1(代表无法进行插入操作)。并将父节点(father)值修改为当前位置节点(cur),代表该节点已经遍历完成。

 

if cur.value == node.value: return -1father = cur

  

2.当前位置节点(cur)的值大于待插入节点(node)的值时,表示待插入节点(node)需继续在当前位置节点的左子树中继续查找。故把当前位置节点(cur)的左节点赋值给当前位置节点(cur),作为下一个要访问的节点对象。

 

if node.value < cur.value: cur = cur.left

  

 

 

 

 

3.当前位置节点(cur)的值小于待插入节点(node)的值时,表示待插入节点(node)需继续在当前位置节点的右子树中继续查找。故把当前位置节点(cur)的右节点赋值给当前位置节点(cur),作为下一个要访问的节点对象。

 

if node.value > cur.value: cur = cur.right

  

 

 

 

 

第三步:找到插入位置后,将其设置为待插入值(node)的父节点

 

node.father = father

  

第四步:插入操作

 

1.父节点的值为空(即要插入的是个空二叉树),将待插入节点(node)赋值给根节点(root)。

 

if father == None: self.root = node

  

2.待插入节点(node)的值小于父节点(father)的值,将其放到父节点的左子节点

 

if node.value <father.value: father.left = node

 

 

 

3.待插入节点(node)的值大于父节点(father)的值,将其放到父节点的右子节点

 

if node.value >father.value: father.right = node

 

 

插入功能代码汇总:

def insert(selfnode): father = None cur = self.root while cur != None: if cur.value == node.value: return -1 father = cur if node.value < cur.value: cur = cur.left else: cur = cur.right node.father = father if father == None: self.root = node elif node.value < father.value: father.left = node else: father.right = node

  

 

方法(bfs):生成二叉搜索树列表

利用队列先进先出的特性,将一个二叉搜索树存放到列表中。

 

def bfs(self): if self.root == None: return None retList = [] q = queue.Queue() q.put(self.root) while q.empty() is not True: node = q.get() retList.append(node.value) if node.left != None: q.put(node.left) if node.right != None: q.put(node.right) return retList

 

示例:针对如下二叉搜索树,遍历存放到一个列表过程

 

 

ps:蓝色:二叉树列表 retList    橙色:队列 q

 

方法(bfs_search):实现查找功能

第一步:将根节点(self.root)设置成当前位置节点(cur),即从根节点开始遍历。

 

def search(selfvalue): cur = self.root

 

如果cur值不为None,执行第二步。否则执行第三步

 

第二步:对比要查找的值(value)与当前位置节点(cur)的值的大小

 

1. 如果当前位置节点(cur)的值等于要查找的值(value),返回当前位置节点(cur)。

 

if cur.value == value: return cur

 

 

 

2. 如果当前位置节点(cur)的值小于要查找的值(value),返回当前位置节点(cur)。

 

if cur.value < value: cur = cur.right

 

 

 

 

 

 

3. 如果当前位置节点(cur)的值小于要查找的值(value),返回当前位置节点(cur)。

 

if cur.value > value: cur = cur.left

 

 

 

 

 

第三步:如果cur的值为None,返回空。即查找的二叉搜索树为空树。

 

return None

 

查找功能代码汇总:

def search(selfvalue): cur = self.root while cur != None: if cur.value == value: return cur elif cur.value < value: cur = cur.right else: cur = cur.left return None

  

方法(bfs_delete):实现删除功能

第一步:将待删除节点(node)的父节点赋值给father变量。

 

def delete(selfnode): father = node.father

  

第二步:判断待删除节点(node)的左子树是否为空

 

1. 待删除节点(node)的左子树为空

if node.left == None:

 

a)     待删除节点(node)为根节点

 

将待删除节点(node)的右子节点置为新的根节点(root),且其如果为非空,将其父节点(node.right.father)赋值为空。

 

if father == None: self.root = node.right if node.right != None: node.right.father = None

 

 

 

 

b)     待删除节点(node)为其父节点的左子节点

 

待删除节点(node)的右子节点(node.right)取代其原来的位置,成为其父节点新的左子节点(father.left)。且其右子节点(node.right)不为空,将待删除节点(node)的父节点赋值给它的父节点(node.right.father)

 

if father.left == node: father.left = node.right if node.right != None: node.right.father = father

 

 

 

 

c)     待删除节点(node)为其父节点的右子节点

 

待删除节点(node)的右子节点(node.right)取代其原来的位置,成为其父节点新的右子节点(father.right)。且其右子节点(node.right)不为空,将待删除节点(node)的父节点赋值给它的父节点(node.right.father)

 

if father.right == node: father.right = node.right if node.right != None: node.right.father = father

 

 

 

2. 待删除节点(node)的左子树不为空

 

第一步:将待删除节点(node)的右子树挂到其左子树最后一层的右子节点下

 

a)     将待删除节点的左子节点(node.left)存到临时变量tmpNode中

 

tmpNode = node.left

 

 

b)     递归找到node.left的最后一层右子节点

 

while tmpNode.right != None: tmpNode = tmpNode.right

 

 

c)     将待删节点的右子树(node.right)挂到node.left的最后一层右子节点下

 

tmpNode.right = node.right

 

d)     将node.right的父节点设置为待删节点左子树中的最后一层的右子节点

 

if node.right != None: node.right.father = tmpNode

 

 

 

第二步:开始删除node

 

1.待删除节点为根节点

 

将待删除节点的左子节点(node.left)设置为根节点(self.root),并将其父节点设置为空。

 

if father == None: self.root = node.left node.left.father = None

  

 

 

 

2.待删除节点为根节点的左子节点

 

待删除节点的左子节点(node.left)取代待删节点的位置,并将其父节点设置为待删除节点的父节点。

 

if father.left == node: father.left = node.left node.left.father = father

 

 

 

3. 待删除节点为根节点的右子节点

 

待删除节点的左子节点(node.left)取代待删节点的位置,并将其父节点设置为待删除节点的父节点

 

if father.right == node: father.right = node.left node.left.father = father

 

 

 

删除功能代码汇总:

def delete(selfnode): father = node.father if node.left == None: if father == None: self.root = node.right if node.right != None: node.right.father = None elif father.left == node: father.left = node.right if node.right != None: node.right.father = father else: father.right = node.right if node.right != None: node.right.father = father return "delete successfully" tmpNode = node.left while tmpNode.right != None: tmpNode = tmpNode.right tmpNode.right = node.right if node.right != None: node.right.father = tmpNode if father == None: self.root = node.left node.left.father = None elif father.left == node: father.left = node.left node.left.father = father else: father.right = node.left node.left.father = father node = None return "delete successfully"

 

综上,二叉搜索树代码

# encoding=utf-8import queueclass TreeNode(object): def __init__(selfval): self.value = val self.left = None self.right = None self.father = Noneclass BST(object): def __init__(selfnodeList): self.root = None for node in nodeList: self.bfs_insert(node) def bfs_insert(selfnode): father = None cur = self.root while cur != None: if cur.value == node.value: return -1 father = cur if node.value < cur.value: cur = cur.left else: cur = cur.right node.father = father if father == None: self.root = node elif node.value < father.value: father.left = node else: father.right = node def bfs(self): if self.root == None: return None retList = [] q = queue.Queue() q.put(self.root) while q.empty() is not True: node = q.get() retList.append(node.value) if node.left != None: q.put(node.left) if node.right != None: q.put(node.right) return retList def bfs_search(selfvalue): cur = self.root while cur != None: if cur.value == value: return cur elif cur.value < value: cur = cur.right else: cur = cur.left return None def bfs_delete(selfnode): father = node.father if node.left == None: if father == None: self.root = node.right if node.right != None: node.right.father = None elif father.left == node: father.left = node.right if node.right != None: node.right.father = father else: father.right = node.right if node.right != None: node.right.father = father return "delete successfully" tmpNode = node.left while tmpNode.right != None: tmpNode = tmpNode.right tmpNode.right = node.right if node.right != None: node.right.father = tmpNode if father == None: self.root = node.left node.left.father = None elif father.left == node: father.left = node.left node.left.father = father else: father.right = node.left node.left.father = father node = None return "delete successfully"if __name__ == "__main__": varList = [243454823453528629] nodeList = [TreeNode(var) for var in varList] bst = BST(nodeList) print (bst.bfs()) node = bst.bfs_search(34) bst.bfs_delete(node) print (bst.bfs())

  

 

文章评论

Top