我搜索過(guò)的關(guān)于二叉樹(shù)的大多數(shù)問(wèn)題都顯示了二叉搜索樹(shù)的實(shí)現(xiàn)，而不是二叉樹(shù)。完全二叉樹(shù)的項(xiàng)是：要么是一棵空樹(shù)，要么它有 1 個(gè)節(jié)點(diǎn)和 2 個(gè)孩子，其中每個(gè)孩子都是另一個(gè)二叉樹(shù)。所有級(jí)別都已滿（可能最后一個(gè)級(jí)別除外）最底層的所有葉子都盡可能靠左。我想出了一個(gè)概念，但它似乎沒(méi)有正確運(yùn)行遞歸——有人知道我做錯(cuò)了什么嗎？class Node(): def __init__(self, key): self.key = key self.left = None self.right = None def add(self, key): if self.key: if self.left is None: self.left = Node(key) else: self.left.add(key) if self.right is None: self.right = Node(key) else: self.right.add(key) else: self.key = key return (self.key)
3 回答
慕雪6442864
TA貢獻(xiàn)1812條經(jīng)驗(yàn) 獲得超5個(gè)贊
您的代碼中的問(wèn)題是您多次添加相同的值。您添加節(jié)點(diǎn)，然后仍然更深入地遞歸，在那里您執(zhí)行相同的操作。
更深層次的問(wèn)題是，在到達(dá)樹(shù)的底層并檢測(cè)到該層的不完整位置之前，您并不知道將節(jié)點(diǎn)插入何處。找到正確的插入點(diǎn)可能需要遍歷整棵樹(shù)……這打敗了您最初期望使用二叉樹(shù)獲得的速度增益。
我在這里提供三種解決方案，從最有效的開(kāi)始：
1.使用列表作為樹(shù)實(shí)現(xiàn)
對(duì)于完整的樹(shù)，需要特別考慮：如果按級(jí)別對(duì)節(jié)點(diǎn)進(jìn)行編號(hào)，從 0 開(kāi)始作為根節(jié)點(diǎn)，并且在每個(gè)級(jí)別內(nèi)從左到右，您會(huì)注意到節(jié)點(diǎn)的父節(jié)點(diǎn)的編號(hào)為(k-1) /2當(dāng)它自己的編號(hào)是k時(shí)。在另一個(gè)方向：如果編號(hào)為k的節(jié)點(diǎn)有子節(jié)點(diǎn)，則其左子節(jié)點(diǎn)的編號(hào)為k*2+1，右子節(jié)點(diǎn)的編號(hào)大一。
因?yàn)闃?shù)是完整的，所以這個(gè)編號(hào)永遠(yuǎn)不會(huì)有間隙，所以你可以將節(jié)點(diǎn)存儲(chǔ)在一個(gè)列表中，并使用該列表的索引為節(jié)點(diǎn)編號(hào)。現(xiàn)在將節(jié)點(diǎn)添加到樹(shù)中僅意味著將其附加到該列表。您沒(méi)有Node對(duì)象，只有樹(shù)列表，該列表中的索引是您的節(jié)點(diǎn)引用。
這是一個(gè)實(shí)現(xiàn)：
class CompleteTree(list):
def add(self, key):
self.append(key)
return len(self) - 1
def left(self, i):
return i * 2 + 1 if i * 2 + 1 < len(self) else -1
def right(self, i):
return i * 2 + 2 if i * 2 + 2 < len(self) else -1
@staticmethod
def parent(i):
return (i - 1) // 2
def swapwithparent(self, i):
if i > 0:
p = self.parent(i)
self[p], self[i] = self[i], self[p]
def inorder(self, i=0):
left = self.left(i)
right = self.right(i)
if left >= 0:
yield from self.inorder(left)
yield i
if right >= 0:
yield from self.inorder(right)
@staticmethod
def depth(i):
return (i + 1).bit_length() - 1
這是一個(gè)創(chuàng)建示例樹(shù)的演示，然后打印按順序遍歷訪問(wèn)的鍵，按它們?cè)跇?shù)中的深度縮進(jìn)：
tree = CompleteTree()
tree.add(1)
tree.add(2)
tree.add(3)
tree.add(4)
tree.add(5)
for node in tree.inorder():
print(" " * tree.depth(node), tree[node])
當(dāng)然，這意味著您必須引用與使用真實(shí)Node類時(shí)略有不同的節(jié)點(diǎn)，但效率的提高是有回報(bào)的。
2.使用額外的屬性
如果您知道一棵（子）樹(shù)中有多少個(gè)節(jié)點(diǎn)，那么從該數(shù)字的位表示，您就可以知道應(yīng)該在何處添加下一個(gè)節(jié)點(diǎn)。
例如，在您的示例樹(shù)中，您有 5 個(gè)節(jié)點(diǎn)。想象一下，你想給那棵樹(shù)加一個(gè) 6。根節(jié)點(diǎn)會(huì)告訴您當(dāng)前有 5，因此您需要將其更新為 6。在二進(jìn)制中為 110。忽略最左邊的 1 位，其余位告訴您是向左還是向右。在這種情況下，您應(yīng)該向右走 (1)，然后最后向左走 (0)，在那個(gè)方向上創(chuàng)建節(jié)點(diǎn)。您可以迭代或遞歸地執(zhí)行此操作。
這是一個(gè)遞歸的實(shí)現(xiàn)：
class Node():
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.count = 1
def add(self, key):
self.count += 1
if self.left is None:
self.left = Node(key)
elif self.right is None:
self.right = Node(key)
# extract from the count the second-most significant bit:
elif self.count & (1 << (self.count.bit_length() - 2)):
self.right.add(key)
else:
self.left.add(key)
def inorder(self):
if self.left:
yield from self.left.inorder()
yield self
if self.right:
yield from self.right.inorder()
tree = Node(1)
tree.add(2)
tree.add(3)
tree.add(4)
tree.add(5)
for node in tree.inorder():
print(node.key)
3.無(wú)額外財(cái)產(chǎn)
如果沒(méi)有屬性可以添加到Node對(duì)象，則需要進(jìn)行更廣泛的搜索才能找到正確的插入點(diǎn)：
class Node():
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def newparent(self):
# Finds the node that should serve as parent for a new node
# It returns a tuple:
# if parent found: [-1, parent for new node]
# if not found: [height, left-most leaf]
# In the latter case, the subtree is perfect, and its left-most
# leaf is the node to be used, unless self is a right child
# and its sibling has the insertion point.
if self.right:
right = self.right.newparent()
if right[0] == -1: # found inbalance
return right
left = self.left.newparent()
if left[0] == -1: # found inbalance
return left
if left[0] != right[0]:
return [-1, right[1]] # found inbalance
# temporary result in perfect subtree
return [left[0]+1, left[1]]
elif self.left:
return [-1, self] # found inbalance
# temporary result for leaf
return [0, self]
def add(self, key):
_, parent = self.newparent()
if not parent.left:
parent.left = Node(key)
else:
parent.right = Node(key)
def __repr__(self):
s = ""
if self.left:
s += str(self.left).replace("\n", "\n ")
s += "\n" + str(self.key)
if self.right:
s += str(self.right).replace("\n", "\n ")
return s
tree = Node(1)
tree.add(2)
tree.add(3)
tree.add(4)
tree.add(5)
print(tree)
這從右到左遞歸搜索樹(shù)，以找到要添加的節(jié)點(diǎn)的候選父節(jié)點(diǎn)。
對(duì)于大樹(shù)，可以通過(guò)根據(jù)這些路徑的長(zhǎng)度在從根到葉的路徑之間進(jìn)行二進(jìn)制搜索來(lái)稍微改進(jìn)一下。但它仍然不會(huì)像前兩種解決方案那樣高效。
至尊寶的傳說(shuō)
TA貢獻(xiàn)1789條經(jīng)驗(yàn) 獲得超10個(gè)贊
茅侃侃
TA貢獻(xiàn)1842條經(jīng)驗(yàn) 獲得超22個(gè)贊
你真的需要以某種方式擴(kuò)充你的樹(shù)。因?yàn)檫@不是二叉搜索樹(shù)，所以關(guān)于每個(gè)節(jié)點(diǎn)的唯一真實(shí)信息是它是否有左孩子和右孩子。不幸的是，這對(duì)導(dǎo)航完整的二叉樹(shù)沒(méi)有幫助。想象一個(gè)有 10 個(gè)級(jí)別的完整二叉樹(shù)。直到第 9 級(jí)，每個(gè)節(jié)點(diǎn)都有一個(gè)左孩子和一個(gè)右孩子，所以你無(wú)法知道從哪條路徑向下到達(dá)葉子。那么問(wèn)題來(lái)了，你給每個(gè)節(jié)點(diǎn)添加什么信息呢？我會(huì)添加該樹(shù)中的節(jié)點(diǎn)數(shù)。
維護(hù)計(jì)數(shù)很容易，因?yàn)槊看蜗陆档阶訕?shù)時(shí)，您都知道要在該節(jié)點(diǎn)的計(jì)數(shù)上加一。你要識(shí)別的是最左邊的不完美子樹(shù)。每個(gè)完美二叉樹(shù)都有 n = 2^k - 1，其中 k 是層數(shù)，n 是節(jié)點(diǎn)數(shù)。有一些快速簡(jiǎn)便的方法可以檢查一個(gè)數(shù)是否小于 2 的冪（參見(jiàn)這個(gè)問(wèn)題的第一個(gè)答案），事實(shí)上，在一棵完整的二叉樹(shù)中，每個(gè)節(jié)點(diǎn)最多有一個(gè)不是根的子節(jié)點(diǎn)的完美二叉樹(shù)。遵循一個(gè)簡(jiǎn)單的規(guī)則來(lái)添加節(jié)點(diǎn)：
如果左孩子為 None，則設(shè)置
root.left = Node(key)并返回否則，如果右孩子為 None，則設(shè)置
root.right = Node(key)并返回如果當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)之一是不完美子樹(shù)的根，則使該節(jié)點(diǎn)成為當(dāng)前節(jié)點(diǎn)（沿該子樹(shù)下降）
否則，如果大小不相等，則將具有較小子樹(shù)的節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)。
否則，使左子節(jié)點(diǎn)成為當(dāng)前節(jié)點(diǎn)。
通過(guò)用以該節(jié)點(diǎn)為根的子樹(shù)的大小擴(kuò)充每個(gè)節(jié)點(diǎn)，您可以在每個(gè)節(jié)點(diǎn)上獲得構(gòu)建遞歸解決方案所需的所有信息。
添加回答
舉報(bào)
0/150
提交
取消