我搜索過的關于二叉樹的大多數問題都顯示了二叉搜索樹的實現，而不是二叉樹。完全二叉樹的項是：要么是一棵空樹，要么它有 1 個節點和 2 個孩子，其中每個孩子都是另一個二叉樹。所有級別都已滿（可能最后一個級別除外）最底層的所有葉子都盡可能靠左。我想出了一個概念，但它似乎沒有正確運行遞歸——有人知道我做錯了什么嗎？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貢獻1812條經驗 獲得超5個贊
您的代碼中的問題是您多次添加相同的值。您添加節點，然后仍然更深入地遞歸，在那里您執行相同的操作。
更深層次的問題是，在到達樹的底層并檢測到該層的不完整位置之前，您并不知道將節點插入何處。找到正確的插入點可能需要遍歷整棵樹……這打敗了您最初期望使用二叉樹獲得的速度增益。
我在這里提供三種解決方案，從最有效的開始：
1.使用列表作為樹實現
對于完整的樹，需要特別考慮：如果按級別對節點進行編號，從 0 開始作為根節點，并且在每個級別內從左到右，您會注意到節點的父節點的編號為(k-1) /2當它自己的編號是k時。在另一個方向：如果編號為k的節點有子節點，則其左子節點的編號為k*2+1，右子節點的編號大一。
因為樹是完整的，所以這個編號永遠不會有間隙，所以你可以將節點存儲在一個列表中，并使用該列表的索引為節點編號?，F在將節點添加到樹中僅意味著將其附加到該列表。您沒有Node對象，只有樹列表，該列表中的索引是您的節點引用。
這是一個實現：
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
這是一個創建示例樹的演示，然后打印按順序遍歷訪問的鍵，按它們在樹中的深度縮進：
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])
當然，這意味著您必須引用與使用真實Node類時略有不同的節點，但效率的提高是有回報的。
2.使用額外的屬性
如果您知道一棵（子）樹中有多少個節點，那么從該數字的位表示，您就可以知道應該在何處添加下一個節點。
例如，在您的示例樹中，您有 5 個節點。想象一下，你想給那棵樹加一個 6。根節點會告訴您當前有 5，因此您需要將其更新為 6。在二進制中為 110。忽略最左邊的 1 位，其余位告訴您是向左還是向右。在這種情況下，您應該向右走 (1)，然后最后向左走 (0)，在那個方向上創建節點。您可以迭代或遞歸地執行此操作。
這是一個遞歸的實現：
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.無額外財產
如果沒有屬性可以添加到Node對象，則需要進行更廣泛的搜索才能找到正確的插入點：
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)
這從右到左遞歸搜索樹，以找到要添加的節點的候選父節點。
對于大樹，可以通過根據這些路徑的長度在從根到葉的路徑之間進行二進制搜索來稍微改進一下。但它仍然不會像前兩種解決方案那樣高效。
茅侃侃
TA貢獻1842條經驗 獲得超22個贊
你真的需要以某種方式擴充你的樹。因為這不是二叉搜索樹，所以關于每個節點的唯一真實信息是它是否有左孩子和右孩子。不幸的是，這對導航完整的二叉樹沒有幫助。想象一個有 10 個級別的完整二叉樹。直到第 9 級，每個節點都有一個左孩子和一個右孩子，所以你無法知道從哪條路徑向下到達葉子。那么問題來了，你給每個節點添加什么信息呢？我會添加該樹中的節點數。
維護計數很容易，因為每次下降到子樹時，您都知道要在該節點的計數上加一。你要識別的是最左邊的不完美子樹。每個完美二叉樹都有 n = 2^k - 1，其中 k 是層數，n 是節點數。有一些快速簡便的方法可以檢查一個數是否小于 2 的冪（參見這個問題的第一個答案），事實上，在一棵完整的二叉樹中，每個節點最多有一個不是根的子節點的完美二叉樹。遵循一個簡單的規則來添加節點：
如果左孩子為 None，則設置
root.left = Node(key)并返回否則，如果右孩子為 None，則設置
root.right = Node(key)并返回如果當前節點的子節點之一是不完美子樹的根，則使該節點成為當前節點（沿該子樹下降）
否則，如果大小不相等，則將具有較小子樹的節點作為當前節點。
否則，使左子節點成為當前節點。
通過用以該節點為根的子樹的大小擴充每個節點，您可以在每個節點上獲得構建遞歸解決方案所需的所有信息。
添加回答
舉報
0/150
提交
取消