python 新手，并試圖確定如何通過創建新樹遞回地修剪決策樹。如果一個節點在“keys_to_prune”串列中有一個鍵，它和它的后代不包括在新樹中。這是我想出的：
def prune_tree(tree, keys_to_prune)
new_tree = Tree()
for child in tree.children:
if child.key not in keys_to_prune:
new_tree.children.append(child)
else:
prune_tree(child, keys_to_prune)
return new_tree
樹物件 (Tree()) 具有 .key、.value 和 .children 屬性。這段代碼似乎不起作用——它似乎在檢查沒有鍵和值的空節點。任何幫助都會有所幫助！
uj5u.com熱心網友回復：
dict 是一種樹。考慮這個例子：
{
"a": {
"a": 1,
"b": 2,
{
"c": 3,
"d": 4,
}
},
"b": {
"a": {
"a": 1,
"b": 2,
},
"z": 99,
},
}
如果keys_to_prune僅包含a，則所需的修剪樹將如下所示：
{
"b": {
"z": 99,
},
}
換句話說，如果你看到一個應該修剪的鍵，什么都不做：不要將它添加到新樹中，也不要探索它的子樹。否則，將子項添加到新樹并探索子項以進行更深入的修剪。
但更微妙的問題是您的遞回實作混合了兩種不同的策略。一方面，它正在組裝和回傳一棵新樹。另一方面，它忽略了回傳值并期望遞回呼叫更深層次來改變子層次。您需要選擇一種方法或另一種方法。例如，如果你堅持回傳新樹的想法，你可能會采取這樣的方法：
def prune_tree(tree, keys_to_prune)
new_tree = Tree()
for child in tree.children:
if child.key not in keys_to_prune:
new_child = prune_tree(child, keys_to_prune)
new_tree.children.append(new_child)
return new_tree
uj5u.com熱心網友回復：
您可以使用串列理解輕松過濾掉內容：
class Tree:
def __init__(self, k, v, children=None):
self.key = k
self.value = v
if children:
self.children = children
else:
self.children = []
def __repr__(self):
return str((self.key, self.value, self.children))
def pruned(t, keys):
return Tree(t.key, t.value, [pruned(c, keys) for c in t.children if c.key not in keys])
import random
def random_tree(max_depth=5, max_children=3):
nb_children = random.randrange(max_children 1) if max_depth > 0 else 0
return Tree(random.randrange(100), random.choice('abcdefghijklmnopqrstuvwxyz'), [random_tree(max_depth-1, max_children) for _ in range(nb_children)])
t = random_tree()
s = pruned(t, set(range(0, 100, 2))) # keep only odd keys
print(t)
# (9, 'd', [(93, 'n', [(17, 'j', [(23, 'h', [(65, 'o', [(80, 'u', []), (89, 'b', [])]), (97, 'e', [(64, 'l', []), (81, 'q', []), (51, 'o', [])])]), (63, 'y', [(65, 'c', [(27, 'h', []), (25, 'z', []), (30, 'k', [])]), (78, 'r', [])]), (65, 'z', [(15, 's', [(39, 'm', []), (69, 'a', [])])])])]), (63, 'a', [(67, 'r', [(18, 'j', [(97, 'i', [(88, 'n', [])]), (6, 'a', [(72, 'l', []), (81, 'n', [])])])]), (52, 'q', [(92, 'z', [(27, 'm', [(88, 'm', []), (39, 't', [])]), (28, 'u', [(40, 'c', [])])]), (1, 'z', [])]), (99, 'r', [(49, 'x', []), (46, 'h', [(38, 'm', [(72, 'v', [])]), (98, 'h', [(75, 'z', []), (67, 'q', [])]), (78, 'w', [(67, 'v', []), (78, 'p', [])])]), (5, 'a', [(1, 'y', []), (73, 'g', [(87, 'o', []), (63, 'i', [])]), (67, 'z', [])])])])])
print(s)
# (9, 'd', [(93, 'n', [(17, 'j', [(23, 'h', [(65, 'o', [(89, 'b', [])]), (97, 'e', [(81, 'q', []), (51, 'o', [])])]), (63, 'y', [(65, 'c', [(27, 'h', []), (25, 'z', [])])]), (65, 'z', [(15, 's', [(39, 'm', []), (69, 'a', [])])])])]), (63, 'a', [(67, 'r', []), (99, 'r', [(49, 'x', []), (5, 'a', [(1, 'y', []), (73, 'g', [(87, 'o', []), (63, 'i', [])]), (67, 'z', [])])])])])
我必須說我對在你的樹中使用key和感到有點困惑value。也許我們可以Tree完全洗掉類并dict直接使用 a ？
def pruned(t, keys):
return {k:pruned(v, keys) for k,v in t.items() if k not in keys}
import random
def random_tree(max_depth=5, max_children=3):
nb_children = random.randrange(max_children 1) if max_depth > 0 else 0
return {random.randrange(100): random_tree(max_depth-1, max_children) for _ in range(nb_children)}
t = random_tree()
s = pruned(t, set(range(0,100,2)))
print(t)
# {63: {37: {}}, 73: {4: {57: {74: {15: {}, 58: {}}, 4: {}}, 58: {4: {33: {}, 56: {}, 70: {}}, 49: {}, 38: {85: {}}}, 66: {22: {79: {}}, 1: {}, 2: {9: {}, 19: {}}}}}}
print(s)
# {63: {37: {}}, 73: {}}
uj5u.com熱心網友回復：
這是我如何使用遞回創建新的“修剪”樹的示例。
為了簡單起見，我將創建一個二叉樹。我將使用此影像作為參考。
這是從示例影像創建樹的代碼，因此我們可以使用一些東西。
class Tree(object):
def __init__(self, data):
self.left = None
self.right = None
self.data = data
####All of the main Nodes####
tree_start = Tree("Has feathers")
can_fly = Tree("Can fly")
has_finns = Tree("Has finns")
hawk = Tree("Hawk")
penguin = Tree("Penguin")
dolphin = Tree("Dolphin")
bear = Tree("Bear")
#####Connect the nodes####
#does it have feathers?
tree_start.left = can_fly
tree_start.right = has_finns
#can it fly?
can_fly.left = hawk
can_fly.right = penguin
#does it have finns?
has_finns.left = dolphin
has_finns.right = bear
這是我們如何使用遞回創建新修剪的樹
#Recursive Funciton
def prune_tree(treeNode, keys_to_prune):
if treeNode is None:
return
if treeNode.data in keys_to_prune:
print("pruning this branch: {}".format(treeNode.data))
return
newTreeNode = Tree(treeNode.data)
if treeNode.left is not None:
newTreeNode.left = (prune_tree(treeNode.left, keys_to_prune))
if treeNode.right is not None:
newTreeNode.right = (prune_tree(treeNode.right, keys_to_prune))
return newTreeNode
呼叫我們的修剪函式
prunedTree = prune_tree(tree_start, ["Can fly"])
最后一部分是可選的，但我們可以使用類似的遞回邏輯來列印出新樹的分支
def print_tree(tree):
if tree:
print(tree.data)
print_tree(tree.left)
print_tree(tree.right)
呼叫列印函式
print_tree(prunedTree)
一切的最終輸出是：
pruning this branch: Can fly
Has feathers
Has finns
Dolphin
Bear
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/371670.html