用Python实现数据结构之二叉搜索树 -清零世界

概述

<div class="markdown-here-wrapper" data-md-url="https://i.cnblogs.com/EditPosts.aspx?opt=1">
<h1 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 24px; border-bottom: 2px solid #aaaaaa;">二叉搜索树
二叉搜索树是一种特殊的二叉树，它的特点是：

一个图例：

搜索树的这种关系，我们可以用它来实现有序映射

搜索树的特性，采用中序遍历的方式可以使得遍历结果是按照从小到大的顺序排列的。了解中序遍历可以参考

 :
    
<span class="hljs-keyword" style="font-weight: bold;"&gt;if</span> right(p) <span class="hljs-keyword" style="font-weight: bold;"&gt;is</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;not</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;None</span>:
    walk = right(p)
    <span class="hljs-keyword" style="font-weight: bold;"&gt;while</span> left(right(p)) <span class="hljs-keyword" style="font-weight: bold;"&gt;is</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;not</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;None</span>:  <span class="hljs-comment" style="color: #738191;"&gt;# 找最左</span>
        walk = left(walk)
    <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> walk
<span class="hljs-keyword" style="font-weight: bold;"&gt;else</span>:
    walk = p
    ancestor = parent(walk)
    <span class="hljs-keyword" style="font-weight: bold;"&gt;while</span> ancestor <span class="hljs-keyword" style="font-weight: bold;"&gt;is</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;not</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;None</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;and</span> walk == right(ancestor):  <span class="hljs-comment" style="color: #738191;"&gt;# 当walk是左孩子时或walk是根节点时停止</span>
        walk = ancestor
        ancestor = parent(walk)
    <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> ancestor

<span class="hljs-keyword" style="font-weight: bold;"&gt;if</span> right(p) <span class="hljs-keyword" style="font-weight: bold;"&gt;is</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;not</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;None</span>:
    walk = right(p)
    <span class="hljs-keyword" style="font-weight: bold;"&gt;while</span> left(right(p)) <span class="hljs-keyword" style="font-weight: bold;"&gt;is</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;not</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;None</span>:  <span class="hljs-comment" style="color: #738191;"&gt;# 找最左</span>
        walk = left(walk)
    <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> walk
<span class="hljs-keyword" style="font-weight: bold;"&gt;else</span>:
    walk = p
    ancestor = parent(walk)
    <span class="hljs-keyword" style="font-weight: bold;"&gt;while</span> ancestor <span class="hljs-keyword" style="font-weight: bold;"&gt;is</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;not</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;None</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;and</span> walk == right(ancestor):  <span class="hljs-comment" style="color: #738191;"&gt;# 当walk是左孩子时或walk是根节点时停止</span>
        walk = ancestor
        ancestor = parent(walk)
    <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> ancestor

<span class="hljs-keyword" style="font-weight: bold;"&gt;if</span> right(p) <span class="hljs-keyword" style="font-weight: bold;"&gt;is</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;not</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;None</span>:
    walk = right(p)
    <span class="hljs-keyword" style="font-weight: bold;"&gt;while</span> left(right(p)) <span class="hljs-keyword" style="font-weight: bold;"&gt;is</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;not</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;None</span>:  <span class="hljs-comment" style="color: #738191;"&gt;# 找最左</span>
        walk = left(walk)
    <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> walk
<span class="hljs-keyword" style="font-weight: bold;"&gt;else</span>:
    walk = p
    ancestor = parent(walk)
    <span class="hljs-keyword" style="font-weight: bold;"&gt;while</span> ancestor <span class="hljs-keyword" style="font-weight: bold;"&gt;is</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;not</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;None</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;and</span> walk == right(ancestor):  <span class="hljs-comment" style="color: #738191;"&gt;# 当walk是左孩子时或walk是根节点时停止</span>
        walk = ancestor
        ancestor = parent(walk)
    <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> ancestor

 :
    
     k == p.key():
         p
     k < p.key()  T.left(p)   :
         search(T,T.left(p))
     k > p.key()  T.right(p)   :
         search(T,T.right(p))
     p

 :
    
<span class="hljs-class"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;class</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;_item</span><span class="hljs-params"&gt;()</span>:</span>

    <span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;__init__</span><span class="hljs-params"&gt;(self,key,value)</span>:</span>
        self.key = key
        self.value = value

    <span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;__eq__</span><span class="hljs-params"&gt;(self,other)</span>:</span>
        <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> self.key == other.key

    <span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;__ne__</span><span class="hljs-params"&gt;(self,other)</span>:</span>
        <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> self.key != other.key

    <span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;__lt__</span><span class="hljs-params"&gt;(self,other)</span>:</span>
        <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> self.key < other.key

<span class="hljs-class"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;class</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;Position</span><span class="hljs-params"&gt;(BinaryTree.Position)</span>:</span>

    <span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;key</span><span class="hljs-params"&gt;(self)</span>:</span>
        <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> self.element().key

    <span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;value</span><span class="hljs-params"&gt;(self)</span>:</span>
        <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> self.element().value

<span class="hljs-class"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;class</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;_item</span><span class="hljs-params"&gt;()</span>:</span>

    <span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;__init__</span><span class="hljs-params"&gt;(self,key,value)</span>:</span>
        self.key = key
        self.value = value

    <span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;__eq__</span><span class="hljs-params"&gt;(self,other)</span>:</span>
        <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> self.key == other.key

    <span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;__ne__</span><span class="hljs-params"&gt;(self,other)</span>:</span>
        <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> self.key != other.key

    <span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;__lt__</span><span class="hljs-params"&gt;(self,other)</span>:</span>
        <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> self.key < other.key

<span class="hljs-class"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;class</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;Position</span><span class="hljs-params"&gt;(BinaryTree.Position)</span>:</span>

    <span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;key</span><span class="hljs-params"&gt;(self)</span>:</span>
        <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> self.element().key

    <span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;value</span><span class="hljs-params"&gt;(self)</span>:</span>
        <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> self.element().value

<span class="hljs-class"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;class</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;_item</span><span class="hljs-params"&gt;()</span>:</span>

    <span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;__init__</span><span class="hljs-params"&gt;(self,key,value)</span>:</span>
        self.key = key
        self.value = value

    <span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;__eq__</span><span class="hljs-params"&gt;(self,other)</span>:</span>
        <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> self.key == other.key

    <span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;__ne__</span><span class="hljs-params"&gt;(self,other)</span>:</span>
        <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> self.key != other.key

    <span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;__lt__</span><span class="hljs-params"&gt;(self,other)</span>:</span>
        <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> self.key < other.key

<span class="hljs-class"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;class</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;Position</span><span class="hljs-params"&gt;(BinaryTree.Position)</span>:</span>

    <span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;key</span><span class="hljs-params"&gt;(self)</span>:</span>
        <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> self.element().key

    <span class="hljs-function"&gt;<span class="hljs-keyword" style="font-weight: bold;"&gt;def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;"&gt;value</span><span class="hljs-params"&gt;(self)</span>:</span>
        <span class="hljs-keyword" style="font-weight: bold;"&gt;return</span> self.element().value

 :
    搜索算法"""
     k == p.key():
         p
     k < p.key():
         self.left(p)   :
             self._subtree_search(self.left(p),k)
    :
         self.right(p)   :
             self._subtree_search(self.right(p),k)
     p
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def <span class="hljs-title" style="font-weight: bold; color: #0048ab;">_subtree_first_position<span class="hljs-params">(self,p):

<span class="hljs-string" style="color: #0048ab;">"""返回树的最左节点"""

walk = p

<span class="hljs-keyword" style="font-weight: bold;">while self.left(walk) <span class="hljs-keyword" style="font-weight: bold;">is <span class="hljs-keyword" style="font-weight: bold;">not <span class="hljs-keyword" style="font-weight: bold;">None:

walk = self.left(walk)

<span class="hljs-keyword" style="font-weight: bold;">return walk
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def <span class="hljs-title" style="font-weight: bold; color: #0048ab;">_subtree_last_position<span class="hljs-params">(self,p):

<span class="hljs-string" style="color: #0048ab;">"""返回树的最右节点"""

walk = p

<span class="hljs-keyword" style="font-weight: bold;">while self.right(walk) <span class="hljs-keyword" style="font-weight: bold;">is <span class="hljs-keyword" style="font-weight: bold;">not <span class="hljs-keyword" style="font-weight: bold;">None:

walk = self.right(walk)

<span class="hljs-keyword" style="font-weight: bold;">return walk

def _subtree_first_position(self,p):
"""返回树的最左节点"""
walk = p
while self.left(walk) is not None:
walk = self.left(walk)
return walk

def _subtree_last_position(self,p): """返回树的最右节点""" walk = p while self.right(walk) is not None: walk = self.right(walk) return walk

 :
     self._subtree_first_position(
        self.root())  len(self) >   
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def <span class="hljs-title" style="font-weight: bold; color: #0048ab;">last<span class="hljs-params">(self):

<span class="hljs-keyword" style="font-weight: bold;">return self._subtree_last_position(

self.root()) <span class="hljs-keyword" style="font-weight: bold;">if len(self) > <span class="hljs-number">0 <span class="hljs-keyword" style="font-weight: bold;">else <span class="hljs-keyword" style="font-weight: bold;">None
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def <span class="hljs-title" style="font-weight: bold; color: #0048ab;">before<span class="hljs-params">(self,p):

<span class="hljs-string" style="color: #0048ab;">"""前驱位置"""

<span class="hljs-keyword" style="font-weight: bold;">if self.left(p):

<span class="hljs-keyword" style="font-weight: bold;">return self._subtree_last_position(self.left(p))

<span class="hljs-keyword" style="font-weight: bold;">else:

walk = p

above = self.parent(walk)

<span class="hljs-keyword" style="font-weight: bold;">while above <span class="hljs-keyword" style="font-weight: bold;">is <span class="hljs-keyword" style="font-weight: bold;">not <span class="hljs-keyword" style="font-weight: bold;">None <span class="hljs-keyword" style="font-weight: bold;">and walk == self.left(above):

walk = above

above = self.parent(walk)

<span class="hljs-keyword" style="font-weight: bold;">return above
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def <span class="hljs-title" style="font-weight: bold; color: #0048ab;">after<span class="hljs-params">(self,p):

<span class="hljs-string" style="color: #0048ab;">"""后继位置"""

<span class="hljs-keyword" style="font-weight: bold;">if self.right(p):

<span class="hljs-keyword" style="font-weight: bold;">return self._subtree_first_position(self.right(p))

<span class="hljs-keyword" style="font-weight: bold;">else:

walk = p

above = self.parent(walk)

<span class="hljs-keyword" style="font-weight: bold;">while above <span class="hljs-keyword" style="font-weight: bold;">is <span class="hljs-keyword" style="font-weight: bold;">not <span class="hljs-keyword" style="font-weight: bold;">None <span class="hljs-keyword" style="font-weight: bold;">and walk == self.right(above):

walk = above

above = self.parent(walk)

<span class="hljs-keyword" style="font-weight: bold;">return above
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def <span class="hljs-title" style="font-weight: bold; color: #0048ab;">find_position<span class="hljs-params">(self,k):

<span class="hljs-keyword" style="font-weight: bold;">if self.is_empty():

<span class="hljs-keyword" style="font-weight: bold;">return <span class="hljs-keyword" style="font-weight: bold;">None

<span class="hljs-keyword" style="font-weight: bold;">else:

p = self._subtree_search(self.root(),k)

<span class="hljs-keyword" style="font-weight: bold;">return p

def last(self):
return self._subtree_last_position(
self.root()) if len(self) > 0 else None

def before(self,p):
"""前驱位置"""
if self.left(p):
return self._subtree_last_position(self.left(p))
else:
walk = p
above = self.parent(walk)
while above is not None and walk == self.left(above):
walk = above
above = self.parent(walk)
return above

def after(self,p):
"""后继位置"""
if self.right(p):
return self._subtree_first_position(self.right(p))
else:
walk = p
above = self.parent(walk)
while above is not None and walk == self.right(above):
walk = above
above = self.parent(walk)
return above

def find_position(self,k): if self.is_empty(): return None else: p = self._subtree_search(self.root(),k) return p

 :
     self.is_empty():
         KeyError(+repr(k))
    :
        p = self._subtree_search(self.root(),k)
         k!=p.key():
             KeyError( + repr(k))
         p.value()
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def <span class="hljs-title" style="font-weight: bold; color: #0048ab;">setitem<span class="hljs-params">(self,k,v):

<span class="hljs-keyword" style="font-weight: bold;">if self.is_empty():

leaf = self.add_root(self._Item(k,v))

<span class="hljs-keyword" style="font-weight: bold;">else:

p = self._subtree_search(self.root(),k)

<span class="hljs-keyword" style="font-weight: bold;">if p.key() == k:

p.element().value = v

<span class="hljs-keyword" style="font-weight: bold;">return

<span class="hljs-keyword" style="font-weight: bold;">else:

item = self._Item(k,v)

<span class="hljs-keyword" style="font-weight: bold;">if p.key() < k:

leaf = self.add_right(p,item)

<span class="hljs-keyword" style="font-weight: bold;">else:

leaf = self.add_left(p,item)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def <span class="hljs-title" style="font-weight: bold; color: #0048ab;">iter<span class="hljs-params">(self):

p = self.first()

<span class="hljs-keyword" style="font-weight: bold;">while p <span class="hljs-keyword" style="font-weight: bold;">is <span class="hljs-keyword" style="font-weight: bold;">not <span class="hljs-keyword" style="font-weight: bold;">None:

<span class="hljs-keyword" style="font-weight: bold;">yield p.key()

p = self.after(p)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def <span class="hljs-title" style="font-weight: bold; color: #0048ab;">mapdelete<span class="hljs-params">(self,p):

<span class="hljs-keyword" style="font-weight: bold;">if self.left(p) <span class="hljs-keyword" style="font-weight: bold;">and self.right(p):      <span class="hljs-comment" style="color: #738191;">#两个孩子都有的时候

replacement = self._subtree_last_position(self.left(p)) <span class="hljs-comment" style="color: #738191;">#用左子树最右位置代替

self.replace(p,replacement.element())

p = replacement

self.delete(p)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def <span class="hljs-title" style="font-weight: bold; color: #0048ab;">delitem<span class="hljs-params">(self,k):

<span class="hljs-keyword" style="font-weight: bold;">if <span class="hljs-keyword" style="font-weight: bold;">not self.is_empty():

p = self._subtree_search(self.root(),k)

<span class="hljs-keyword" style="font-weight: bold;">if k == p.key():

self.mapdelete(p)

<span class="hljs-keyword" style="font-weight: bold;">return

<span class="hljs-keyword" style="font-weight: bold;">raise KeyError(<span class="hljs-string" style="color: #0048ab;">'Key Error' + repr(k))

def setitem(self,k,v):
if self.is_empty():
leaf = self.add_root(self._Item(k,v))
else:
p = self._subtree_search(self.root(),k)
if p.key() == k:
p.element().value = v
return
else:
item = self._Item(k,v)
if p.key() < k:
leaf = self.add_right(p,item)
else:
leaf = self.add_left(p,item)

def iter(self):
p = self.first()
while p is not None:
yield p.key()
p = self.after(p)

def mapdelete(self,p):
if self.left(p) and self.right(p): #两个孩子都有的时候
replacement = self._subtree_last_position(self.left(p)) #用左子树最右位置代替
self.replace(p,replacement.element())
p = replacement
self.delete(p)

def delitem(self,k): if not self.is_empty(): p = self._subtree_search(self.root(),k) if k == p.key(): self.mapdelete(p) return raise KeyError('Key Error' + repr(k))

 :
    元组"""
     self.is_empty():
         
    :
        p = self.first()
        (p.key(),p.value())
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def <span class="hljs-title" style="font-weight: bold; color: #0048ab;">find_ge<span class="hljs-params">(self,k):

<span class="hljs-string" style="color: #0048ab;">"""找第一个大于等于k的键值元组"""

<span class="hljs-keyword" style="font-weight: bold;">if self.is_empty():

<span class="hljs-keyword" style="font-weight: bold;">return <span class="hljs-keyword" style="font-weight: bold;">None

<span class="hljs-keyword" style="font-weight: bold;">else:

p = self.find_position(k)

<span class="hljs-keyword" style="font-weight: bold;">if p.key() < k:

p = self.after(p)

<span class="hljs-keyword" style="font-weight: bold;">return (p.key(),p.value()) <span class="hljs-keyword" style="font-weight: bold;">if p <span class="hljs-keyword" style="font-weight: bold;">is <span class="hljs-keyword" style="font-weight: bold;">not <span class="hljs-keyword" style="font-weight: bold;">None <span class="hljs-keyword" style="font-weight: bold;">else <span class="hljs-keyword" style="font-weight: bold;">None
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def <span class="hljs-title" style="font-weight: bold; color: #0048ab;">find_range<span class="hljs-params">(self,start,stop):
<span class="hljs-keyword" style="font-weight: bold;"&gt;if</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;not</span> self.is_empty():
    <span class="hljs-keyword" style="font-weight: bold;"&gt;if</span> start <span class="hljs-keyword" style="font-weight: bold;"&gt;is</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;None</span>:
        p = self.first()
    <span class="hljs-keyword" style="font-weight: bold;"&gt;else</span>:
        p = self.find_position(start)
        <span class="hljs-keyword" style="font-weight: bold;"&gt;if</span> p.key() < start:
            p = self.after(p)
    <span class="hljs-keyword" style="font-weight: bold;"&gt;while</span> p <span class="hljs-keyword" style="font-weight: bold;"&gt;is</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;not</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;None</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;and</span> (stop <span class="hljs-keyword" style="font-weight: bold;"&gt;is</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;None</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;or</span> p.key() < stop):
        <span class="hljs-keyword" style="font-weight: bold;"&gt;yield</span> (p.key(),p.value())
        p = self.after(p)

<span class="hljs-keyword" style="font-weight: bold;"&gt;if</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;not</span> self.is_empty():
    <span class="hljs-keyword" style="font-weight: bold;"&gt;if</span> start <span class="hljs-keyword" style="font-weight: bold;"&gt;is</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;None</span>:
        p = self.first()
    <span class="hljs-keyword" style="font-weight: bold;"&gt;else</span>:
        p = self.find_position(start)
        <span class="hljs-keyword" style="font-weight: bold;"&gt;if</span> p.key() < start:
            p = self.after(p)
    <span class="hljs-keyword" style="font-weight: bold;"&gt;while</span> p <span class="hljs-keyword" style="font-weight: bold;"&gt;is</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;not</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;None</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;and</span> (stop <span class="hljs-keyword" style="font-weight: bold;"&gt;is</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;None</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;or</span> p.key() < stop):
        <span class="hljs-keyword" style="font-weight: bold;"&gt;yield</span> (p.key(),p.value())
        p = self.after(p)

def find_ge(self,k):
"""找第一个大于等于k的键值元组"""
if self.is_empty():
return None
else:
p = self.find_position(k)
if p.key() < k:
p = self.after(p)
return (p.key(),p.value()) if p is not None else None

def find_range(self,start,stop):

<span class="hljs-keyword" style="font-weight: bold;"&gt;if</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;not</span> self.is_empty():
    <span class="hljs-keyword" style="font-weight: bold;"&gt;if</span> start <span class="hljs-keyword" style="font-weight: bold;"&gt;is</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;None</span>:
        p = self.first()
    <span class="hljs-keyword" style="font-weight: bold;"&gt;else</span>:
        p = self.find_position(start)
        <span class="hljs-keyword" style="font-weight: bold;"&gt;if</span> p.key() < start:
            p = self.after(p)
    <span class="hljs-keyword" style="font-weight: bold;"&gt;while</span> p <span class="hljs-keyword" style="font-weight: bold;"&gt;is</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;not</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;None</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;and</span> (stop <span class="hljs-keyword" style="font-weight: bold;"&gt;is</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;None</span> <span class="hljs-keyword" style="font-weight: bold;"&gt;or</span> p.key() < stop):
        <span class="hljs-keyword" style="font-weight: bold;"&gt;yield</span> (p.key(),p.value())
        p = self.after(p)

如果您也喜欢它,动动您的小指点个赞吧

用Python实现数据结构之二叉搜索树

概述

分类汇总

您的鼓励是对我最大的支持