首页 » python » 正文

二叉查找树的增加,删除,遍历 python

本文主要使用python实现二叉查找树的如下部分:

  • 二叉查找树构造
  • 二叉查找树插入
  • 二叉查找树遍历
  • 二叉查找树删除

 

二叉查找树是一颗二叉树,并且基本数据结构要求满足如下条件:

  • 所有左接点的值均小于它的根结点
  • 所有的右接点值均大于它的根结点
  • 所有的左右子树均是二叉查找树(每个接点都大于它左侧子树的任意接点,并小于右侧子树的任意接点)

来个栗子:

二叉查找树的构造:

我们想来构造一个树,我们需要3个变量:

  • 左节点
  • 右节点
  • 根节点数据

 

让我们来创建一个值为8的根结点,这个时候,左右节点均是None

root = Node(8)

如下图看到的,我们创建了一个只有一个节点的树

插入方法

我们需要一个方法来插入元素让我们的单个节点的树变的充实起来,这个方法的参数是个数值和某个节点本身(根节点/二叉查找树)


 

插入方法会递归的调用,直到为我们的元素(节点)找到合适的位置

.

让我们来增加3个元素(节点),然后看看我们的插入方法是如何运行的

1 root.insert(3)
2 root.insert(10)
3 root.insert(1)

插入元素3(节点)的过程:

  • 第一步: 根结点调用插入方法,调用时传入的变量为3
  • 第二步:3比8小,而且 根节点8的左节点为None,所以我们直接把3这个节点(3的左右节点均为None),放到8的左节点上

插入元素10(节点)的过程:

  • 根节点调用insert方法,传入变量10
  • 10大于根节点,并且根节点的右分支为None,所以我们把10放到根节点的右分支

插入元素1(节点)的过程:

  • 根节点调用insert方法,传入参数1
  • 1比8小,并且8这个根结点有左侧分值(不为None),所以,根结点的左节点调用insert方法,传入参数1
  • 这个时候,1比3小,并且3没有左分支,我们就把1放到了3的左节点上

现在的结构是:

让我们继续插入新的元素让树更加充实.

1 root.insert(6)
2 root.insert(4)
3 root.insert(7)
4 root.insert(14)
5 root.insert(13)

插入完成后的栗子:

遍历

我们需要一个方法能够帮助我们找到具体的某一个节点,这个方法会接收一个数值,返回这个数值所在的节点,并返回它的父节点(如果不寸再就返回None)


 

我们试着查找下6

1 node, parent = root.lookup(6)

具体的查找过程:

  • 第一步: 传入参数6,默认的parent = None
  • 第二步:6 小于根节点的8
  • 第三步:这个时候,根结点的左节点3,继续调用lookup函数,这个时候的parent就是当前的节点了
  • 第四步:6比3大
  • 第五步:然后3的右节点(孩子),调用lookup
  • 第六步:发现6等于3的右孩子,找到了!

删除方法

删除方法需要传入的参数就是一个节点的值


 

删除的时候有三种情况:

  • 1:被删除的节点没有子节点
  • 2:被删除的节点有一个子节点.
  • 3:被删除的节点有2个子节点

第一种情况是非常简单的,我只需要将这个节点删除,然后将它的父节点相应的子节点置为None即可


 

注:方法children_count()会返回一个节点的子节点的个数

children_count:

举个例子,我们想删除节点1,3的左分支会被设置成None

1 root.delete(1)

让我们来看一下第二种情况,这个时候,我们需要用它的子节点来代替被删除的节点


 

举个例子,我们想删除节点14,这个时候,13会代替14,然后新的13的左右分支会被置为None

1 root.delete(14)

让我们来看一下最后一种可能,就是被删除节点有两个子节点,我们会用其中一个来代被删除的节点,并递归的完成这个过程


 

举例子:我们想要删除3,这个时候我们会递归的去查找右测元素,终于找到4,我们将4替换3,然后将6的子节点值None

1 root.delete(3)

参考地址: http://www.laurentluce.com/posts/binary-search-tree-library-in-python/comment-page-1/

发表评论