<p>您可以找到树中的所有节点以及节点的路径,找到结果的最小值,然后遍历生成的路径以删除节点:</p>
<pre><code>class Tree:
def __init__(self, **kwargs):
self.__dict__ = {i:kwargs.get(i) for i in ['val', 'left', 'right']}
def get_nodes(self, current = []):
yield [''.join(current), self.val]
yield from getattr(self.right, 'get_nodes', lambda _:[])(current+['1'])
yield from getattr(self.left, 'get_nodes', lambda _:[])(current+['0'])
def __iter__(self):
yield self.val
yield from [[], self.left][bool(self.left)]
yield from [[], self.right][bool(self.right)]
def _insert_back(self, _v):
if not self.val:
self.val = _v
else:
if _v < self.val:
getattr(self.left, '_insert_back', lambda x:setattr(x, 'left', Tree(val=x)))(_v)
else:
getattr(self.right, '_insert_back', lambda x:setattr(x, 'right', Tree(val=x)))(_v)
def remove(self, _path, _to_val, last=None):
'''_to_val: if _to_val is None, then the item is removed. If not, the node value is set to _to_val'''
if _path:
getattr(self, ['left', 'right'][int(_path[0])]).remove(_path[1:], _to_val, last = self)
else:
if _to_val is None:
last.left = None
last.right = None
for i in [[], self.left][bool(self.left)]:
last._insert_back(i)
for i in [[], self.right][bool(self.right)]:
last._insert_back(i)
else:
self.val = _to_val
</code></pre>
<p>创建:</p>
^{pr2}$
<hr/>
<pre><code>t = Tree(val = 7, left=Tree(val = 5, left=Tree(val=4), right=Tree(val=6)), right=Tree(val=9, left=Tree(val=8), right=Tree(val=10, right=Tree(val=12))))
path, _to_remove = min(t.get_nodes(), key=lambda x:x[-1])
print(f'Removing {_to_remove}')
t.remove(path, None)
print([i for i in t])
</code></pre>
<p>输出:</p>
<pre><code>4
[7, 5, 9, 8, 10, 12]
</code></pre>