二叉搜索树(二叉排序树)它的每个节点的数据结构为1个父节点指针,1个左孩子指针,1个有孩子指针,还有就是自己的数据部分了,因为只有左右两孩子,所以才叫二叉树,在此基础上,该二叉树还满足另外一个条件:每个结点的左孩子都不大于该结点&&每个结点的右孩子都大于该结点.
二叉搜索树
我们已经知道了在一个集合中获取键值对的两种不同的方法。回忆一下这些集合是如何实现adt（抽象数据类型）map的。我们讨论两种adt map的实现方式，基于列表的二分查找和哈希表。在这一节中，我们将要学习二叉搜索树，这是另一种键指向值的map集合，在这种情况下我们不用考虑元素在树中的实际位置，但要知道使用二叉树来搜索更有效率。
搜索树操作
在我们研究这种实现方式之前，让我们回顾一下adt map提供的接口。我们会注意到，这种接口和python的字典非常相似。
map() 创建了一个新的空map集合。
put(key,val) 在map中增加了一个新的键值对。如果这个键已经在这个map中了，那么就用新的值来代替旧的值。
get(key) 提供一个键，返回map中保存的数据，或者返回none。
del 使用del map[key]这条语句从map中删除键值对。
len() 返回map中保存的键值对的数目
in 如果所给的键在map中，使用key in map这条语句返回true。
搜索树实现
一个二叉搜索树，如果具有左子树中的键值都小于父节点，而右子树中的键值都大于父节点的属性，我们将这种树称为bst搜索树。如之前所述的，当我们实现map时，bst方法将引导我们实现这一点。图 1 展示了二叉搜索树的这一特性，显示的键没有关联任何的值。注意这种属性适用于每个父节点和子节点。所有在左子树的键值都小于根节点的键值，所有右子树的键值都大于根节点的键值。
class binarysearchtree:
def init(self):
self.root = none
self.size = 0
def length(self):
return self.size
def len(self):
return self.size
def iter(self):
return self.root.iter()
treenode类提供了许多辅助函数，使得binarysearchtree类的方法更容易实现过程。如listing 2 所示，一个树节点的结构，是由这些辅助函数实现的。正如你看到的那样，这些辅助函数可以根据自己的位置来划分一个节点作为左或右孩子和该子节点的类型。treenode类非常清楚地跟踪了每个父节点的属性。当我们讨论删除操作的实现时，你将明白为什么这很重要。
对于listing 2 中的treenode实现，另一个有趣的地方是，我们使用python的可选参数。可选的参数很容易让我们在几种不同的情况下创建一个树节点，有时我们想创建一个新的树节点，即使我们已经有了父节点和子节点。与现有的父节点和子节点一样，我们可以通过父节点和子节点作为参数。有时我们也会创建一个包含键值对的树，我们不会传递父节点或子节点的任何参数。在这种情况下，我们将使用可选参数的默认值。
listing 2
class treenode:
def init(self,key,val,left=none,right=none,
parent=none):
self.key = key
self.payload = val
self.leftchild = left
self.rightchild = right
self.parent = parent
def hasleftchild(self):
return self.leftchild
def hasrightchild(self):
return self.rightchild
def isleftchild(self):
return self.parent and self.parent.leftchild == self
def isrightchild(self):
return self.parent and self.parent.rightchild == self
def isroot(self):
return not self.parent
def isleaf(self):
return not (self.rightchild or self.leftchild)
def hasanychildren(self):
return self.rightchild or self.leftchild
def hasbothchildren(self):
return self.rightchild and self.leftchild
def replacenodedata(self,key,value,lc,rc):
self.key = key
self.payload = value
self.leftchild = lc
self.rightchild = rc
if self.hasleftchild():
self.leftchild.parent = self
if self.hasrightchild():
self.rightchild.parent = self
现在，我们拥有了binarysearchtree和treenode类，是时候写一个put方法使我们能够建立二叉搜索树。put方法是binarysearchtree类的一个方法。这个方法将检查这棵树是否已经有根。如果没有，我们将创建一个新的树节点并把它设置为树的根。如果已经有一个根节点，我们就调用它自己，进行递归，用辅助函数_put按下列算法来搜索树：
从树的根节点开始，通过搜索二叉树来比较新的键值和当前节点的键值，如果新的键值小于当前节点，则搜索左子树。如果新的关键大于当前节点，则搜索右子树。
当搜索不到左（或右）子树，我们在树中所处的位置就是设置新节点的位置。向树中添加一个节点，创建一个新的treenode对象并在这个点的上一个节点中插入这个对象。
listing 3 显示了在树中插入新节点的python代码。_put函数要按照上述的步骤编写递归算法。注意，当一个新的子树插入时，当前节点（currentnode）作为父节点传递给新的树。
我们执行插入的一个重要问题是重复的键值不能被正确的处理，我们的树实现了键值的复制，它将在右子树创建一个与原来节点键值相同的新节点。这样做的后果是，新的节点将不会在搜索过程中被发现。我们用一个更好的方式来处理插入重复的键值，旧的值被新键关联的值替换。我们把这个错误的修复，作为练习留给你。
listing 3
def put(self,key,val):
if self.root:
self._put(key,val,self.root)
else:
self.root = treenode(key,val)
self.size = self.size + 1
def _put(self,key,val,currentnode):
if key < currentnode.key:
if currentnode.hasleftchild():
self._put(key,val,currentnode.leftchild)
else:
currentnode.leftchild = treenode(key,val,parent=currentnode)
else:
if currentnode.hasrightchild():
self._put(key,val,currentnode.rightchild)
else:
currentnode.rightchild = treenode(key,val,parent=currentnode)
随着put方法的实现，我们可以很容易地通过setitem方法重载[]作为操作符来调用put方法（参见listing 4）。这使我们能够编写像myziptree[‘plymouth’] = 55446一样的python语句，这看上去就像python的字典。
listing 4
def setitem(self,k,v):
self.put(k,v)
图 2 说明了将新节点插入到一个二叉搜索树的过程。灰色节点显示了插入过程中遍历树节点顺序。
def get(self,key):
if self.root:
res = self._get(key,self.root)
if res:
return res.payload
else:
return none
else:
return none
def _get(self,key,currentnode):
if not currentnode:
return none
elif currentnode.key == key:
return currentnode
elif key < currentnode.key:
return self._get(key,currentnode.leftchild)
else:
return self._get(key,currentnode.rightchild)
def getitem(self,key):
return self.get(key)
使用get，我们可以通过写一个binarysearchtree的contains方法来实现操作，contains方法简单地调用了get方法，如果它有返回值就返回true，如果它是none就返回false。如listing 6 所示。
listing 6
def contains(self,key):
if self._get(key,self.root):
return true
else:
return false
回顾一下contains重载的操作符，这允许我们写这样的语句：
if ‘northfield’ in myziptree:
print(“oom ya ya”)
以上就是python实现二叉搜索树的方法的详细内容，更多请关注 第一php社区 其它相关文章！