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

发布时间：2020-12-17 00:18:02 所属栏目：Python 来源：网络整理

导读：div class="markdown-here-wrapper" data-md-url="https://i.cnblogs.com/EditPosts.aspx?opt=1"gt; h1 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 24px; border-bottom: 2px solid #aaaaaa;"二叉搜

<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;">二叉搜索树
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">二叉搜索树是一种特殊的二叉树，它的特点是：

<ul style="margin: 1.2em 0px; padding-left: 2em; list-style-type: square; font-size: 16px;">
<li style="margin: 0.5em 0px; font-size: 16px;">
<p style="margin: 0.5em 0px !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">对于任意一个节点p，存储在p的左子树的中的所有节点中的值都小于p中的值

 :
    
<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

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">找前驱同理

<h1 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 24px; border-bottom: 2px solid #aaaaaa;">搜索

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">既然叫做二叉搜索树，那它很重要的一个用途就是搜索，搜索的方式为：

<ul style="margin: 1.2em 0px; padding-left: 2em; list-style-type: square; font-size: 16px;">
<li style="margin: 0.5em 0px; font-size: 16px;">
<p style="margin: 0.5em 0px !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">与根节点比较，如果相等则根节点就是要搜索的位置

 :
    
     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

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">BinaryTree是在之前文章中定义的二叉树类，具体参考<a href="https://www.cnblogs.com/sfencs-hcy/p/10341449.html">用Python实现数据结构之树

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">首先定义了两个内嵌类，一个表示键值项，一个用于封装节点

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">然后定义些非公开方法用于其他方法使用：

 :
    
     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

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">下面是一些公开的访问方法：

 :
     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

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">接下来是映射的核心方法：

 :
     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))

<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">最后是一些有序映射特有的方法：

 :
    
     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)

<div style="height: 0; width: 0; max-height: 0; max-width: 0; overflow: hidden; font-size: 0em; padding: 0; margin: 0;" title="MDH:PHA+IyDkuozlj4nmkJzntKLmoJE8L3A+PHA+5LqM5Y+J5pCc57Si5qCR5piv5LiA56eN54m55q6K
55qE5LqM5Y+J5qCR77yM5a6D55qE54m554K55piv77yaPC9wPjxwPiog5a+55LqO5Lu75oSP5LiA
5Liq6IqC54K5cO+8jOWtmOWCqOWcqHDnmoTlt6blrZDmoJHnmoTkuK3nmoTmiYDmnInoioLngrnk
uK3nmoTlgLzpg73lsI/kuo5w5Lit55qE5YC8PC9wPjxwPiombmJzcDvlr7nkuo7ku7vmhI/kuIDk
uKroioLngrlw77yM5a2Y5YKo5ZyocOeahOWPs+WtkOagkeeahOS4reeahOaJgOacieiKgueCueS4
reeahOWAvOmDveWkp+S6jnDkuK3nmoTlgLw8L3A+PHA+Jm5ic3A7PC9wPjxwPuS4gOS4quWbvuS+
i++8mjwvcD48cD48aW1nIHNyYz0iaHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQ2
OTAxNS8yMDE5MDIvMTQ2OTAxNS0yMDE5MDIwNTE2MTMzMDIzOC0yMDkwODIyNDUyLnBuZyIgYWx0
PSIiIGRhdGEtbWNlLXNyYz0iaHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQ2OTAx
NS8yMDE5MDIvMTQ2OTAxNS0yMDE5MDIwNTE2MTMzMDIzOC0yMDkwODIyNDUyLnBuZyIgd2lkdGg9
IjM1NiIgaGVpZ2h0PSIyNzciPjwvcD48cD48YnI+PC9wPjxwPuWfuuS6juS6jOWPieaQnOe0ouag
keeahOi/meenjeWFs+ezu++8jOaIkeS7rOWPr+S7peeUqOWug+adpeWunueOsOacieW6j+aYoOWw
hDwvcD48cD4jIOmBjeWOhuS6jOWPieaQnOe0ouagkTwvcD48cD7ln7rkuo7kuozlj4nmkJzntKLm
oJHnmoTnibnmgKfvvIzph4fnlKjkuK3luo/pgY3ljobnmoTmlrnlvI/lj6/ku6Xkvb/lvpfpgY3l
jobnu5PmnpzmmK/mjInnhafku47lsI/liLDlpKfnmoTpobrluo/mjpLliJfnmoTjgILkuobop6Pk
uK3luo/pgY3ljoblj6/ku6Xlj4LogIM8YSBpZD0iY2JfcG9zdF90aXRsZV91cmwiIGNsYXNzPSJw
b3N0VGl0bGUyIiBocmVmPSJodHRwczovL3d3dy5jbmJsb2dzLmNvbS9zZmVuY3MtaGN5L3AvMTAz
NDE0NDkuaHRtbCIgdGFyZ2V0PSJfYmxhbmsiIGRhdGEtbWNlLWhyZWY9Imh0dHBzOi8vd3d3LmNu
YmxvZ3MuY29tL3NmZW5jcy1oY3kvcC8xMDM0MTQ0OS5odG1sIj7nlKhQeXRob27lrp7njrDmlbDm
ja7nu5PmnoTkuYvmoJE8L2E+PC9wPjxwPui/memHjOi/mOmcgOimgeaAneiAg+eahOS4gOS4quWG
heWuueaYr+WcqOWfuuS6juS4reW6j+mBjeWOhueahOWJjeaPkOS4i++8jOWmguS9leaxguS4gOS4
quiKgueCueeahOWQjue7p+iKgueCueaIluWJjempseiKgueCueOAgjwvcD48cD7mmL7nhLbov5nl
sLHmmK/msYLmr5Tor6XoioLngrnlpKfnmoTkuIvkuIDkuKroioLngrnmiJbmr5TlroPlsI/nmoTl
iY3kuIDkuKroioLngrnjgILmiJHku6zmi7/msYLlkI7nu6foioLngrnkuLrkvovvvJo8L3A+PHA+
KiDlvZPor6XoioLngrnmnInlj7PlranlrZDml7bvvIzpgqPkuYjlkI7nu6fnu5PngrnlsLHmmK/l
j7PlrZDmoJHkuK3mnIDlt6bovrnnmoToioLngrk8L3A+PHA+KiDlvZPor6XoioLngrnmsqHmnInl
j7PlranlrZDml7bvvIzpgqPkuYjlkI7nu6foioLngrnlsLHmmK/nrKzkuIDkuKrmmK/lt6blranl
rZDnmoTnpZblhYjnmoTniLboioLngrk8L3A+PHA+Jm5ic3A7PC9wPjxwPueul+azleeUqOS8quS7
o+eggeihqOekuuS4uu+8mjwvcD48cD5gYGBweXRob248L3A+PHByZT5kZWYgYWZ0ZXIocCk6PGJy
PiAgICAiIiLlr7vmib7kuozlj4nmkJzntKLmoJHnmoTlkI7nu6foioLngrnnmoTkvKrku6PnoIEi
IiI8YnI+PGJyPiAgICBpZiByaWdodChwKSBpcyBub3QgTm9uZTo8YnI+ICAgICAgICB3YWxrID0g
cmlnaHQocCk8YnI+ICAgICAgICB3aGlsZSBsZWZ0KHJpZ2h0KHApKSBpcyBub3QgTm9uZTogICMg
5om+5pyA5bemPGJyPiAgICAgICAgICAgIHdhbGsgPSBsZWZ0KHdhbGspPGJyPiAgICAgICAgcmV0
dXJuIHdhbGs8YnI+ICAgIGVsc2U6PGJyPiAgICAgICAgd2FsayA9IHA8YnI+ICAgICAgICBhbmNl
c3RvciA9IHBhcmVudCh3YWxrKTxicj4gICAgICAgIHdoaWxlIGFuY2VzdG9yIGlzIG5vdCBOb25l
IGFuZCB3YWxrID09IHJpZ2h0KGFuY2VzdG9yKTogICMg5b2Td2Fsa+aYr+W3puWtqeWtkOaXtuaI
lndhbGvmmK/moLnoioLngrnml7blgZzmraI8YnI+ICAgICAgICAgICAgd2FsayA9IGFuY2VzdG9y
PGJyPiAgICAgICAgICAgIGFuY2VzdG9yID0gcGFyZW50KHdhbGspPGJyPiAgICAgICAgcmV0dXJu
IGFuY2VzdG9yPC9wcmU+PHA+YGBgPC9wPjxwPuaJvuWJjempseWQjOeQhjwvcD48cD4jIOaQnOe0
ojwvcD48cD7ml6LnhLblj6vlgZrkuozlj4nmkJzntKLmoJHvvIzpgqPlroPlvojph43opoHnmoTk
uIDkuKrnlKjpgJTlsLHmmK/mkJzntKLvvIzmkJzntKLnmoTmlrnlvI/kuLrvvJo8L3A+PHA+KiDk
uI7moLnoioLngrnmr5TovoPvvIzlpoLmnpznm7jnrYnliJnmoLnoioLngrnlsLHmmK/opoHmkJzn
tKLnmoTkvY3nva48L3A+PHA+KiDmr5TmoLnoioLngrnlsI/vvIzliJnpgJLlvZLnmoTkuI7lt6bl
ranlrZDmr5TovoM8L3A+PHA+KiDmr5TmoLnoioLngrnlpKfvvIzliJnpgJLlvZLnmoTkuI7mnInl
ranlrZDmr5TovoM8L3A+PHA+KiDlpoLmnpzmnIDlkI7msqHmib7liLDvvIzliJnov5Tlm57mnIDl
kI7kuIDkuKrkuI7kuYvmr5TovoPnmoToioLngrnvvIzmhI/lkbPnnYDlj6/ku6XlnKjov5nkuKro
ioLngrnkvY3nva7mj5LlhaXliJrmiY3mkJzntKLnmoTlgLw8L3A+PHA+Jm5ic3A7PC9wPjxwPueu
l+azleeUqOS8quS7o+eggeihqOekuuS4uu+8mjwvcD48cD5gYGBweXRob248L3A+PHByZT5kZWYg
c2VhcmNoKFQscCxrKTo8YnI+ICAgICIiIuS6jOWPieagkeaQnOe0oueahOS8quS7o+egge+8jGvm
mK/opoHmkJzntKLnmoTlgLwiIiI8YnI+ICAgIGlmIGsgPT0gcC5rZXkoKTo8YnI+ICAgICAgICBy
ZXR1cm4gcDxicj4gICAgZWxpZiBrICZsdDsgcC5rZXkoKSBhbmQgVC5sZWZ0KHApIGlzIG5vdCBO
b25lOjxicj4gICAgICAgIHJldHVybiBzZWFyY2goVCxULmxlZnQocCkpPGJyPiAgICBlbGlmIGsg
Jmd0OyBwLmtleSgpIGFuZCBULnJpZ2h0KHApIGlzIG5vdCBOb25lOjxicj4gICAgICAgIHJldHVy
biBzZWFyY2goVCxULnJpZ2h0KHApKTxicj4gICAgcmV0dXJuIHA8L3ByZT48cD5gYGA8L3A+PHA+
5pCc57Si55qE5pe26Ze05LiO6auY5bqm5pyJ5YWz77yM5pivTyhoKSzkuZ/lsLHmmK/mnIDlnY/n
moTmg4XlhrXkuIvkuLpPKG4pLOacgOWlveeahOaDheWGteS4i+aYr08obG9nKG4pKTwvcD48cD4j
IOaPkuWFpTwvcD48cD7mj5LlhaXnrpfms5XovoPnroDljZXvvIzlroPkvp3otZbkuo7mkJzntKLn
rpfms5XvvIzlsIbmkJzntKLnmoTov5Tlm57nmoTkvY3nva7nmoTlgLzkuI5rZXnov5vooYzmr5To
voPvvIw8L3A+PHA+KiDlpoLmnpznm7jnrYnvvIzliJnlsLHlnKjmraTkvY3nva7kv67mlLk8L3A+
PHA+KiDlpoLmnpzlsI/kuo7ov5Tlm57kvY3nva7nmoTlgLzvvIzliJnmj5LlhaXliLDov5Tlm57k
vY3nva7nmoTlt6blranlrZA8L3A+PHA+KiZuYnNwO+WmguaenOWwj+S6jui/lOWbnuS9jee9ruea
hOWAvO+8jOWImeaPkuWFpeWIsOi/lOWbnuS9jee9rueahOWPs+WtqeWtkDwvcD48cD4mbmJzcDs8
L3A+PHA+IyDliKDpmaQ8L3A+PHA+5Yig6Zmk5pON5L2c6L6D5Li65aSN5p2C77yM5Zug5Li65Yig
6Zmk55qE5L2N572u5Y+v5Lul5piv5Lu75oSP55qE5L2N572u77yM6K6+5Yig6Zmk55qE5L2N572u
5Li6cDwvcD48cD4qIOWmguaenOWIoOmZpOeahOS9jee9ruayoeacieWtqeWtkO+8jOWImeebtOaO
peWIoOS6huWwseihjDwvcD48cD4qIOWmguaenOWIoOmZpOeahOS9jee9ruacieS4gOS4quWtqeWt
kO+8jOWImeWIoOmZpOS5i+WQjuaKiuWug+eahOWtqeWtkOaOpeWIsOWug+WOn+adpeeahOS9jee9
ruS4ijwvcD48cD4qIOWmguaenOWIoOmZpOeahOS9jee9ruacieS4pOS4quWtqeWtkO+8jOWIme+8
mjwvcD48cD4xLuWFiOaJvuWIsOS9jee9rnDnmoTliY3pqbFy77yM5YmN6amx5Zyo5bem5a2Q5qCR
5LitPC9wPjxwPjIu5oqKcOWIoOmZpO+8jOWwhnLku6Pmm79wPC9wPjxwPjMu5oqKcuWOn+adpeea
hOS9jee9ruWIoOmZpDwvcD48cD4mbmJzcDs8L3A+PHA+5L2/55So5YmN6amx55qE5Y6f5Zug5piv
5a6D5b+F54S25q+UcOeahOWPs+WtkOagkeeahOaJgOacieiKgueCueWwj++8jOS5n+W/heeEtuav
lOmZpOS6hnLnmoRw55qE5bem5a2Q5qCR55qE5omA5pyJ6IqC54K55aSnPC9wPjxwPiMgcHl0aG9u
5a6e546wPC9wPjxwPuaIkeS7rOWIqeeUqOS6jOWPieagkeadpeWunueOsOacieW6j+aYoOWwhDwv
cD48cD5gYGBweXRob248L3A+PHByZT5jbGFzcyBPcmRlcmVkTWFwKEJpbmFyeVRyZWUsTXV0YWJs
ZU1hcHBpbmcpOjxicj4gICAgIiIi5L2/55So5LqM5Y+J5pCc57Si5qCR5a6e546w55qE5pyJ5bqP
5pig5bCEIiIiPGJyPiAgICA8YnI+ICAgIGNsYXNzIF9pdGVtKCk6PGJyPiAgICAgICAgPGJyPiAg
ICAgICAgZGVmIF9faW5pdF9fKHNlbGYsIGtleSwgdmFsdWUpOjxicj4gICAgICAgICAgICBzZWxm
LmtleSA9IGtleTxicj4gICAgICAgICAgICBzZWxmLnZhbHVlID0gdmFsdWU8YnI+PGJyPiAgICAg
ICAgZGVmIF9fZXFfXyhzZWxmLCBvdGhlcik6PGJyPiAgICAgICAgICAgIHJldHVybiBzZWxmLmtl
eSA9PSBvdGhlci5rZXk8YnI+PGJyPiAgICAgICAgZGVmIF9fbmVfXyhzZWxmLCBvdGhlcik6PGJy
PiAgICAgICAgICAgIHJldHVybiBzZWxmLmtleSAhPSBvdGhlci5rZXk8YnI+ICAgICAgICA8YnI+
ICAgICAgICBkZWYgX19sdF9fKHNlbGYsIG90aGVyKTo8YnI+ICAgICAgICAgICAgcmV0dXJuIHNl
bGYua2V5ICZsdDsgb3RoZXIua2V5PGJyPiAgICAgICAgPGJyPiAgICBjbGFzcyBQb3NpdGlvbihC
aW5hcnlUcmVlLlBvc2l0aW9uKTo8YnI+ICAgICAgICA8YnI+ICAgICAgICBkZWYga2V5KHNlbGYp
Ojxicj4gICAgICAgICAgICByZXR1cm4gc2VsZi5lbGVtZW50KCkua2V5PGJyPiAgICAgICAgPGJy
PiAgICAgICAgZGVmIHZhbHVlKHNlbGYpOjxicj4gICAgICAgICAgICByZXR1cm4gc2VsZi5lbGVt
ZW50KCkudmFsdWU8L3ByZT48cD5gYGA8L3A+PHA+QmluYXJ5VHJlZeaYr+WcqOS5i+WJjeaWh+er
oOS4reWumuS5ieeahOS6jOWPieagkeexu++8jOWFt+S9k+WPguiAgzxhIGlkPSJjYl9wb3N0X3Rp
dGxlX3VybCIgY2xhc3M9InBvc3RUaXRsZTIiIGhyZWY9Imh0dHBzOi8vd3d3LmNuYmxvZ3MuY29t
L3NmZW5jcy1oY3kvcC8xMDM0MTQ0OS5odG1sIiB0YXJnZXQ9Il9ibGFuayIgZGF0YS1tY2UtaHJl
Zj0iaHR0cHM6Ly93d3cuY25ibG9ncy5jb20vc2ZlbmNzLWhjeS9wLzEwMzQxNDQ5Lmh0bWwiPueU
qFB5dGhvbuWunueOsOaVsOaNrue7k+aehOS5i+agkTwvYT48L3A+PHA+6aaW5YWI5a6a5LmJ5LqG
5Lik5Liq5YaF5bWM57G777yM5LiA5Liq6KGo56S66ZSu5YC86aG577yM5LiA5Liq55So5LqO5bCB
6KOF6IqC54K5PC9wPjxwPueEtuWQjuWumuS5ieS6m+mdnuWFrOW8gOaWueazleeUqOS6juWFtuS7
luaWueazleS9v+eUqO+8mjwvcD48cD5gYGBweXRob248L3A+PHByZT5kZWYgX3N1YnRyZWVfc2Vh
cmNoKHNlbGYsIHAsIGspOjxicj4gICAgIiIi5pCc57Si566X5rOVIiIiPGJyPiAgICBpZiBrID09
IHAua2V5KCk6PGJyPiAgICAgICAgcmV0dXJuIHA8YnI+ICAgIGVsaWYgayAmbHQ7IHAua2V5KCk6
PGJyPiAgICAgICAgaWYgc2VsZi5sZWZ0KHApIGlzIG5vdCBOb25lOjxicj4gICAgICAgICAgICBy
ZXR1cm4gc2VsZi5fc3VidHJlZV9zZWFyY2goc2VsZi5sZWZ0KHApLCBrKTxicj4gICAgZWxzZTo8
YnI+ICAgICAgICBpZiBzZWxmLnJpZ2h0KHApIGlzIG5vdCBOb25lOjxicj4gICAgICAgICAgICBy
ZXR1cm4gc2VsZi5fc3VidHJlZV9zZWFyY2goc2VsZi5yaWdodChwKSwgayk8YnI+ICAgIHJldHVy
biBwPGJyPjxicj5kZWYgX3N1YnRyZWVfZmlyc3RfcG9zaXRpb24oc2VsZiwgcCk6PGJyPiAgICAi
IiLov5Tlm57moJHnmoTmnIDlt6boioLngrkiIiI8YnI+ICAgIHdhbGsgPSBwPGJyPiAgICB3aGls
ZSBzZWxmLmxlZnQod2FsaykgaXMgbm90IE5vbmU6PGJyPiAgICAgICAgd2FsayA9IHNlbGYubGVm
dCh3YWxrKTxicj4gICAgcmV0dXJuIHdhbGs8YnI+PGJyPmRlZiBfc3VidHJlZV9sYXN0X3Bvc2l0
aW9uKHNlbGYsIHApOjxicj4gICAgIiIi6L+U5Zue5qCR55qE5pyA5Y+z6IqC54K5IiIiPGJyPiAg
ICB3YWxrID0gcDxicj4gICAgd2hpbGUgc2VsZi5yaWdodCh3YWxrKSBpcyBub3QgTm9uZTo8YnI+
ICAgICAgICB3YWxrID0gc2VsZi5yaWdodCh3YWxrKTxicj4gICAgcmV0dXJuIHdhbGs8L3ByZT48
cD5gYGA8L3A+PHA+5LiL6Z2i5piv5LiA5Lqb5YWs5byA55qE6K6/6Zeu5pa55rOV77yaPC9wPjxw
PmBgYHB5dGhvbjwvcD48cHJlPmRlZiBmaXJzdChzZWxmKTo8YnI+ICAgIHJldHVybiBzZWxmLl9z
dWJ0cmVlX2ZpcnN0X3Bvc2l0aW9uKDxicj4gICAgICAgIHNlbGYucm9vdCgpKSBpZiBsZW4oc2Vs
ZikgJmd0OyAwIGVsc2UgTm9uZTxicj48YnI+ZGVmIGxhc3Qoc2VsZik6PGJyPiAgICByZXR1cm4g
c2VsZi5fc3VidHJlZV9sYXN0X3Bvc2l0aW9uKDxicj4gICAgICAgIHNlbGYucm9vdCgpKSBpZiBs
ZW4oc2VsZikgJmd0OyAwIGVsc2UgTm9uZTxicj48YnI+ZGVmIGJlZm9yZShzZWxmLCBwKTo8YnI+
ICAgICIiIuWJjempseS9jee9riIiIjxicj4gICAgaWYgc2VsZi5sZWZ0KHApOjxicj4gICAgICAg
IHJldHVybiBzZWxmLl9zdWJ0cmVlX2xhc3RfcG9zaXRpb24oc2VsZi5sZWZ0KHApKTxicj4gICAg
ZWxzZTo8YnI+ICAgICAgICB3YWxrID0gcDxicj4gICAgICAgIGFib3ZlID0gc2VsZi5wYXJlbnQo
d2Fsayk8YnI+ICAgICAgICB3aGlsZSBhYm92ZSBpcyBub3QgTm9uZSBhbmQgd2FsayA9PSBzZWxm
LmxlZnQoYWJvdmUpOjxicj4gICAgICAgICAgICB3YWxrID0gYWJvdmU8YnI+ICAgICAgICAgICAg
YWJvdmUgPSBzZWxmLnBhcmVudCh3YWxrKTxicj4gICAgICAgIHJldHVybiBhYm92ZTxicj48YnI+
ZGVmIGFmdGVyKHNlbGYsIHApOjxicj4gICAgIiIi5ZCO57un5L2N572uIiIiPGJyPiAgICBpZiBz
ZWxmLnJpZ2h0KHApOjxicj4gICAgICAgIHJldHVybiBzZWxmLl9zdWJ0cmVlX2ZpcnN0X3Bvc2l0
aW9uKHNlbGYucmlnaHQocCkpPGJyPiAgICBlbHNlOjxicj4gICAgICAgIHdhbGsgPSBwPGJyPiAg
ICAgICAgYWJvdmUgPSBzZWxmLnBhcmVudCh3YWxrKTxicj4gICAgICAgIHdoaWxlIGFib3ZlIGlz
IG5vdCBOb25lIGFuZCB3YWxrID09IHNlbGYucmlnaHQoYWJvdmUpOjxicj4gICAgICAgICAgICB3
YWxrID0gYWJvdmU8YnI+ICAgICAgICAgICAgYWJvdmUgPSBzZWxmLnBhcmVudCh3YWxrKTxicj4g
ICAgICAgIHJldHVybiBhYm92ZTxicj48L3ByZT48cHJlPmRlZiBmaW5kX3Bvc2l0aW9uKHNlbGYs
ayk6PGJyPiAgICBpZiBzZWxmLmlzX2VtcHR5KCk6PGJyPiAgICAgICAgcmV0dXJuIE5vbmU8YnI+
ICAgIGVsc2U6PGJyPiAgICAgICAgcCA9IHNlbGYuX3N1YnRyZWVfc2VhcmNoKHNlbGYucm9vdCgp
LGspPGJyPiAgICAgICAgcmV0dXJuIHA8L3ByZT48cD5gYGA8L3A+PHA+5o6l5LiL5p2l5piv5pig
5bCE55qE5qC45b+D5pa55rOV77yaPC9wPjxwPmBgYHB5dGhvbjwvcD48cHJlPmRlZiBfX2dldGl0
ZW1fXyhzZWxmLCBrKTo8YnI+ICAgIGlmIHNlbGYuaXNfZW1wdHkoKTo8YnI+ICAgICAgICByYWlz
ZSBLZXlFcnJvcignS2V5IEVycm9yJytyZXByKGspKTxicj4gICAgZWxzZTo8YnI+ICAgICAgICBw
ID0gc2VsZi5fc3VidHJlZV9zZWFyY2goc2VsZi5yb290KCksayk8YnI+ICAgICAgICBpZiBrIT1w
LmtleSgpOjxicj4gICAgICAgICAgICByYWlzZSBLZXlFcnJvcignS2V5IEVycm9yJyArIHJlcHIo
aykpPGJyPiAgICAgICAgcmV0dXJuIHAudmFsdWUoKTxicj48YnI+ZGVmIF9fc2V0aXRlbV9fKHNl
bGYsIGssdik6PGJyPiAgICBpZiBzZWxmLmlzX2VtcHR5KCk6PGJyPiAgICAgICAgbGVhZiA9IHNl
bGYuYWRkX3Jvb3Qoc2VsZi5fSXRlbShrLHYpKTxicj4gICAgZWxzZTo8YnI+ICAgICAgICBwID0g
c2VsZi5fc3VidHJlZV9zZWFyY2goc2VsZi5yb290KCksayk8YnI+ICAgICAgICBpZiBwLmtleSgp
ID09IGs6PGJyPiAgICAgICAgICAgIHAuZWxlbWVudCgpLnZhbHVlID0gdjxicj4gICAgICAgICAg
ICByZXR1cm48YnI+ICAgICAgICBlbHNlOjxicj4gICAgICAgICAgICBpdGVtID0gc2VsZi5fSXRl
bShrLHYpPGJyPiAgICAgICAgICAgIGlmIHAua2V5KCkgJmx0OyBrOjxicj4gICAgICAgICAgICAg
ICAgbGVhZiA9IHNlbGYuYWRkX3JpZ2h0KHAsaXRlbSk8YnI+ICAgICAgICAgICAgZWxzZTo8YnI+
ICAgICAgICAgICAgICAgIGxlYWYgPSBzZWxmLmFkZF9sZWZ0KHAsIGl0ZW0pPGJyPjxicj5kZWYg
X19pdGVyX18oc2VsZik6PGJyPiAgICBwID0gc2VsZi5maXJzdCgpPGJyPiAgICB3aGlsZSBwIGlz
IG5vdCBOb25lOjxicj4gICAgICAgIHlpZWxkIHAua2V5KCk8YnI+ICAgICAgICBwID0gc2VsZi5h
ZnRlcihwKTxicj48YnI+ZGVmIG1hcGRlbGV0ZShzZWxmLHApOjxicj4gICAgaWYgc2VsZi5sZWZ0
KHApIGFuZCBzZWxmLnJpZ2h0KHApOiAgICAgICPkuKTkuKrlranlrZDpg73mnInnmoTml7blgJk8
YnI+ICAgICAgICByZXBsYWNlbWVudCA9IHNlbGYuX3N1YnRyZWVfbGFzdF9wb3NpdGlvbihzZWxm
LmxlZnQocCkpICPnlKjlt6blrZDmoJHmnIDlj7PkvY3nva7ku6Pmm788YnI+ICAgICAgICBzZWxm
LnJlcGxhY2UocCxyZXBsYWNlbWVudC5lbGVtZW50KCkpPGJyPiAgICAgICAgcCA9IHJlcGxhY2Vt
ZW50PGJyPiAgICBzZWxmLmRlbGV0ZShwKTxicj4gICAgICAgICAgICAgICAgPGJyPmRlZiBfX2Rl
bGl0ZW1fXyhzZWxmLCBrKTo8YnI+ICAgIGlmIG5vdCBzZWxmLmlzX2VtcHR5KCk6PGJyPiAgICAg
ICAgcCA9IHNlbGYuX3N1YnRyZWVfc2VhcmNoKHNlbGYucm9vdCgpLGspPGJyPiAgICAgICAgaWYg
ayA9PSBwLmtleSgpOjxicj4gICAgICAgICAgICBzZWxmLm1hcGRlbGV0ZShwKTxicj4gICAgICAg
ICAgICByZXR1cm48YnI+ICAgIHJhaXNlIEtleUVycm9yKCdLZXkgRXJyb3InICsgcmVwcihrKSk8
L3ByZT48cD5gYGA8L3A+PHA+5pyA5ZCO5piv5LiA5Lqb5pyJ5bqP5pig5bCE54m55pyJ55qE5pa5
5rOV77yaPC9wPjxwPmBgYHB5dGhvbjwvcD48cHJlPmRlZiBmaW5kX21pbihzZWxmKTo8YnI+ICAg
ICIiIuaJvuacgOWwj+WAvO+8jOi/lOWbnumUruWAvOWFg+e7hCIiIjxicj4gICAgaWYgc2VsZi5p
c19lbXB0eSgpOjxicj4gICAgICAgIHJldHVybiBOb25lPGJyPiAgICBlbHNlOjxicj4gICAgICAg
IHAgPSBzZWxmLmZpcnN0KCk8YnI+ICAgICAgICByZXR1cm4ocC5rZXkoKSwgcC52YWx1ZSgpKTxi
cj48YnI+ZGVmIGZpbmRfZ2Uoc2VsZiwgayk6PGJyPiAgICAiIiLmib7nrKzkuIDkuKrlpKfkuo7n
rYnkuo5r55qE6ZSu5YC85YWD57uEIiIiPGJyPiAgICBpZiBzZWxmLmlzX2VtcHR5KCk6PGJyPiAg
ICAgICAgcmV0dXJuIE5vbmU8YnI+ICAgIGVsc2U6PGJyPiAgICAgICAgcCA9IHNlbGYuZmluZF9w
b3NpdGlvbihrKTxicj4gICAgICAgIGlmIHAua2V5KCkgJmx0OyBrOjxicj4gICAgICAgICAgICBw
ID0gc2VsZi5hZnRlcihwKTxicj4gICAgICAgIHJldHVybiAocC5rZXkoKSwgcC52YWx1ZSgpKSBp
ZiBwIGlzIG5vdCBOb25lIGVsc2UgTm9uZTxicj48YnI+ZGVmIGZpbmRfcmFuZ2Uoc2VsZiwgc3Rh
cnQsIHN0b3ApOjxicj48YnI+ICAgIGlmIG5vdCBzZWxmLmlzX2VtcHR5KCk6PGJyPiAgICAgICAg
aWYgc3RhcnQgaXMgTm9uZTo8YnI+ICAgICAgICAgICAgcCA9IHNlbGYuZmlyc3QoKTxicj4gICAg
ICAgIGVsc2U6PGJyPiAgICAgICAgICAgIHAgPSBzZWxmLmZpbmRfcG9zaXRpb24oc3RhcnQpPGJy
PiAgICAgICAgICAgIGlmIHAua2V5KCkgJmx0OyBzdGFydDo8YnI+ICAgICAgICAgICAgICAgIHAg
PSBzZWxmLmFmdGVyKHApPGJyPiAgICAgICAgd2hpbGUgcCBpcyBub3QgTm9uZSBhbmQgKHN0b3Ag
aXMgTm9uZSBvciBwLmtleSgpICZsdDsgc3RvcCk6PGJyPiAgICAgICAgICAgIHlpZWxkIChwLmtl
eSgpLCBwLnZhbHVlKCkpPGJyPiAgICAgICAgICAgIHAgPSBzZWxmLmFmdGVyKHApPC9wcmU+PHA+
YGBgPC9wPjxwPjxiciBkYXRhLW1jZS1ib2d1cz0iMSI+PC9wPjxwPjxiciBkYXRhLW1jZS1ib2d1
cz0iMSI+PC9wPjxwPjxiciBkYXRhLW1jZS1ib2d1cz0iMSI+PC9wPjxwPjxiciBkYXRhLW1jZS1i
b2d1cz0iMSI+PC9wPg==">?

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!