<p><strong>节点结构和插入</strong></p>
<p>我们从一个简单的<code>node</code>结构开始,但是请注意<code>left</code>和<code>right</code>属性可以在构造时设置-</p>
<pre class="lang-py prettyprint-override"><code># btree.py
class node:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
</code></pre>
<p>递归是一种函数遗产,因此将其与函数风格结合使用会产生最好的结果。这意味着避免突变、变量重新分配和其他副作用。注意<code>add</code>总是构造一个<em>新的</em>节点,而不是变异一个旧节点。这就是我们设计<code>node</code>在施工时接受所有财产的原因-</p>
<pre class="lang-py prettyprint-override"><code># btree.py (continued)
def add(t, q):
if not t:
return node(q)
elif q < t.data:
return node(t.data, add(t.left, q), t.right)
elif q > t.data:
return node(t.data, t.left, add(t.right, q))
else:
return node(q, t.left, t.right)
</code></pre>
<p><strong>顺序遍历和字符串转换</strong></p>
<p>在我们创建了一些节点之后,我们需要一种可视化树的方法。下面我们编写一个<code>inorder</code>遍历和一个<code>to_str</code>函数-</p>
<pre class="lang-py prettyprint-override"><code># btree.py (continued)
def inorder(t):
if not t: return
yield from inorder(t.left)
yield t.data
yield from inorder(t.right)
def to_str(t):
return "->".join(map(str,inorder(t)))
</code></pre>
<p><strong>b树对象接口</strong></p>
<p>请注意,我们并没有将上面的普通函数与类纠缠在一起,从而使其过于复杂。我们现在可以定义一个<code>btree</code>面向对象接口,它只包装普通函数-</p>
<pre class="lang-py prettyprint-override"><code># btree.py (continued)
class btree:
def __init__(self, t=None): self.t = t
def __str__(self): return to_str(self.t)
def add(self, q): return btree(add(self.t, q))
def inorder(self): return inorder(self.t)
</code></pre>
<p>注意,我们还编写了<code>btree.py</code>作为它自己的模块。这定义了一个抽象的障碍,并允许我们扩展、修改和重用特性,而不会将它们与程序的其他区域纠缠在一起。让我们看看到目前为止我们的树是如何工作的-</p>
<pre class="lang-py prettyprint-override"><code># main.py
from btree import btree
t = btree().add(50).add(60).add(40).add(30).add(45).add(55).add(100)
print(str(t))
# 30->40->45->50->55->60->100
</code></pre>
<p><strong>最小值和最大值</strong></p>
<p>我们将继续这样工作,定义直接作用于<code>node</code>对象的普通函数。接下来,<code>minimum</code>和<code>maximum</code>-</p>
<pre class="lang-py prettyprint-override"><code># btree.py (continued)
from math import inf
def minimum(t, r=inf):
if not t:
return r
elif t.data < r:
return min(minimum(t.left, t.data), minimum(t.right, t.data))
else:
return min(minimum(t.left, r), minimum(t.right, r))
def maximum(t, r=-inf):
if not t:
return r
elif t.data > r:
return max(maximum(t.left, t.data), maximum(t.right, t.data))
else:
return max(maximum(t.left, r), maximum(t.right, r))
</code></pre>
<p><code>btree</code>接口只提供普通函数的包装器-</p>
<pre class="lang-py prettyprint-override"><code># btree.py (continued)
class btree:
def __init__(): # ...
def __str__(): # ...
def add(): # ...
def inorder(): # ...
def maximum(self): return maximum(self.t)
def minimum(self): return minimum(self.t)
</code></pre>
<p>我们现在可以测试<code>minimum</code>和<code>maximum</code></p>
<pre class="lang-py prettyprint-override"><code># main.py
from btree import btree
t = btree().add(50).add(60).add(40).add(30).add(45).add(55).add(100)
print(str(t))
# 30->40->45->50->55->60->100
print(t.minimum(), t.maximum()) # <-
# 30 100
</code></pre>
<p><strong>从iterable插入</p>
<p>链接<code>.add().add().add()</code>有点冗长。提供<code>add_iter</code>函数允许我们从另一个iterable插入任意数量的值。我们现在介绍它是因为我们也将在即将到来的<code>remove</code>函数中重用它-</p>
<pre class="lang-py prettyprint-override"><code>def add_iter(t, it):
for q in it:
t = add(t, q)
return t
</code></pre>
<pre class="lang-py prettyprint-override"><code>#main.py
from btree import btree
t = btree().add_iter([50, 60, 40, 30, 45, 55, 100]) # <-
print(str(t))
# 30->40->45->50->55->60->100
print(t.minimum(), t.maximum())
# 30 100
</code></pre>
<p><strong>节点删除和前序遍历</strong></p>
<p>现在我们转到<code>remove</code>函数。它的工作原理类似于<code>add</code>函数,与要删除的值<code>q</code>执行<code>t.data</code>比较。您会注意到,我们在这里使用<code>add_iter</code>组合要删除的节点的<code>left</code>和<code>right</code>分支。我们<em>可以</em>在这里为我们的树重用<code>inorder</code>迭代器,但是<code>preorder</code>将使树更加平衡。这是一个完全不同的话题,所以我们现在不讨论-</p>
<pre class="lang-py prettyprint-override"><code># btree.py (continued)
def remove(t, q):
if not t:
return t
elif q < t.data:
return node(t.data, remove(t.left, q), t.right)
elif q > t.data:
return node(t.data, t.left, remove(t.right, q))
else:
return add_iter(t.left, preorder(t.right))
def preorder(t):
if not t: return
yield t.data
yield from preorder(t.left)
yield from preorder(t.right)
</code></pre>
<p>别忘了扩展<code>btree</code>接口-</p>
<pre class="lang-py prettyprint-override"><code># btree.py (continued)
class btree:
def __init__(): # ...
def __str__(): # ...
def add(): # ...
def inorder(): # ...
def maximum(): # ...
def minimum(): # ...
def add_iter(self, it): return btree(add_iter(self.t, it))
def remove(self, q): return btree(remove(self.t, q))
def preorder(self): return preorder(self.t)
</code></pre>
<p>让我们看看<code>remove</code>现在的行动-</p>
<pre class="lang-py prettyprint-override"><code># main.py
from btree import btree
t = btree().add_iter([50, 60, 40, 30, 45, 55, 100])
print(str(t))
# 30->40->45->50->55->60->100
print(t.minimum(), t.maximum())
# 30 100
t = t.remove(30).remove(50).remove(100) # <-
print(str(t))
# 40->45->55->60
print(t.minimum(), t.maximum())
# 40 60
</code></pre>
<p><strong>完成的btree模块</strong></p>
<p>这是我们在回答这个问题的过程中构建的完整模块-</p>
<pre class="lang-py prettyprint-override"><code>from math import inf
class node:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def add(t, q):
if not t:
return node(q)
elif q < t.data:
return node(t.data, add(t.left, q), t.right)
elif q > t.data:
return node(t.data, t.left, add(t.right, q))
else:
return node(q, t.left, t.right)
def add_iter(t, it):
for q in it:
t = add(t, q)
return t
def maximum(t, r=-inf):
if not t:
return r
elif t.data > r:
return max(maximum(t.left, t.data), maximum(t.right, t.data))
else:
return max(maximum(t.left, r), maximum(t.right, r))
def minimum(t, r=inf):
if not t:
return r
elif t.data < r:
return min(minimum(t.left, t.data), minimum(t.right, t.data))
else:
return min(minimum(t.left, r), minimum(t.right, r))
def inorder(t):
if not t: return
yield from inorder(t.left)
yield t.data
yield from inorder(t.right)
def preorder(t):
if not t: return
yield t.data
yield from preorder(t.left)
yield from preorder(t.right)
def remove(t, q):
if not t:
return t
elif q < t.data:
return node(t.data, remove(t.left, q), t.right)
elif q > t.data:
return node(t.data, t.left, remove(t.right, q))
else:
return add_iter(t.left, preorder(t.right))
def to_str(t):
return "->".join(map(str,inorder(t)))
class btree:
def __init__(self, t=None): self.t = t
def __str__(self): return to_str(self.t)
def add(self, q): return btree(add(self.t, q))
def add_iter(self, it): return btree(add_iter(self.t, it))
def maximum(self): return maximum(self.t)
def minimum(self): return minimum(self.t)
def inorder(self): return inorder(self.t)
def preorder(self): return preorder(self.t)
def remove(self, q): return btree(remove(self.t, q))
</code></pre>
<p><strong>吃你的蛋糕,也吃它</strong></p>
<p>上述方法的一个被低估的优点是,我们的<code>btree</code>模块有一个<em>双</em>接口。我们可以用传统的面向对象的方式来使用它,<em>或</em>我们可以用一种更功能化的方法来使用它-</p>
<pre class="lang-py prettyprint-override"><code># main.py
from btree import add_iter, remove, to_str, minimum, maximum
t = add_iter(None, [50, 60, 40, 30, 45, 55, 100])
print(to_str(t))
# 30->40->45->50->55->60->100
print(minimum(t), maximum(t))
# 30 100
t = remove(remove(remove(t, 30), 50), 100)
print(to_str(t))
# 40->45->55->60
print(minimum(t), maximum(t))
# 40 60
</code></pre>
<p><strong>额外阅读</strong></p>
<p>我已经写了大量关于这个答案中使用的技巧的文章。按照链接查看它们在其他上下文中的使用,并提供其他解释-</p>
<ul>
<li><p><a href="https://stackoverflow.com/a/65532663/633183">I want to reverse the stack but i dont know how to use recursion for reversing this… How can i reverse the stack without using Recursion</a></p>
</li>
<li><p><a href="https://stackoverflow.com/a/65512563/633183">Finding all maze solutions with Python</a></p>
</li>
<li><p><a href="https://stackoverflow.com/a/61963040/633183">Return middle node of linked list with recursion</a></p>
</li>
<li><p><a href="https://stackoverflow.com/a/66723902/633183">How do i recursively find a size of subtree based on any given node? (BST)</a></p>
</li>
</ul>