Python遞回函式搜索二叉樹

在 Python 中非常新，我正在嘗試理解二叉樹上的遞回。我已經實作了一個非常簡單的樹，它有趣地將英文字符映射到二進制（1 和 0）。我只使用了一個非常簡單的結構，因為我正在努力解決一個我已經設定的更復雜的問題。我想如果我能理解我的例子，那么我應該能夠離開并看看我自己提出的問題。

下面創建類 BinaryTree 和這個的一個實體

class BinaryTree:
    """A rooted binary tree"""
    def __init__(self):
        self.root = None
        self.left = None
        self.right = None

def is_empty(testtree: BinaryTree) -> bool:
        """Return True if tree is empty."""
        return testtree.root == testtree.left == testtree.right == None

def join(item: object, left: BinaryTree, right: BinaryTree) -> BinaryTree:
    """Return a tree with the given root and subtrees."""
    testtree = BinaryTree()
    testtree.root = item
    testtree.left = left
    testtree.right = right
    return testtree

EMPTY = BinaryTree()
C = join('C',EMPTY,EMPTY)
D = join('D',EMPTY,EMPTY)
E = join('E',EMPTY,EMPTY)
F = join('F',EMPTY,EMPTY)
A = join('A',C,D)
B = join('B',E,F)
BINARY = join('START',B,A)

我將其可視化如下

二叉樹的可視化

Now I'm trying to create a function that will take two inputs, a BinaryTree and a single character and the output will be the binary code for the corresponding letter (as an example, D = " 10 "). I'm outputting as a string rather than an integer. My function and test case as follows

# global variable
result = ''

#Convert binary to letter
def convert_letter(testtree: BinaryTree, letter: str) -> str:
    global result
    if testtree == None:
        return False
    elif testtree.root == letter:
        return True        
    else:  
        if convert_letter(testtree.left, letter) == True:
            result  = "1"
            return result
        elif convert_letter(testtree.right, letter) == True:
            result  = "0"
            return result
     
#Test
test = 'D' #Return '10'
convert_letter(BINARY, test)

And unfortunately that's where I'm hitting a brick wall. I had tried initialising an empty string within the function, but everytime it iterates over the function it overwrites the string. Any help greatly appreciated.

uj5u.com熱心網友回復：

我冒昧地簡化了您的代碼，如果您對它的作業原理有任何疑問，請告訴我。

class node:
    """A rooted binary tree"""
    def __init__(self, value = None, left = None, right = None):
        self.value = value
        self.left = left
        self.right = right

C = node('C')
D = node('D')
E = node('E')
F = node('F')
A = node('A',C,D)
B = node('B',E,F)
BINARY = node('START',B,A)

def convert_letter(n,letter):
    if n.value == letter:
        return "1" (convert_letter(n.left,letter) if not n.left is None else "") (convert_letter(n.right,letter)if not n.right is None else "")
    else:
        return "0" (convert_letter(n.left,letter) if not n.left is None else "") (convert_letter(n.right,letter)if not n.right is None else "")

def walk(n):
    return n.value (walk(n.left) if not n.left is None else "") (walk(n.right) if not n.right is None else "")

test = 'D'
print(convert_letter(BINARY, test))
print(walk(BINARY))

uj5u.com熱心網友回復：

這不是我個人構建答案的方式，但我認為它最接近您正在嘗試的內容。您的答案的缺點只是您只回傳一個值，而是跟蹤兩個值。請注意，我冒昧更正：

BINARY = join('START',A,B)

讓我們修改您的方法以回傳指示是否找到字母的布林值以及路徑的指示符。

def convert_letter2(testtree: BinaryTree, letter: str):
    if not testtree:
        return (False, "")

    if testtree.root == letter:
        return (True, "")

    test, val = convert_letter2(testtree.left, letter)
    if test:
        return (True, "1"   val)

    test, val = convert_letter2(testtree.right, letter)
    if test:
        return (True, "0"   val)

    return (False, "")

那么如果我們：

print(convert_letter2(BINARY, "D")[1])

我們應該回去"10"

uj5u.com熱心網友回復：

問題是您的函式有時會回傳布林值，有時會回傳字串，有時會回傳None. 因此，使用此代碼：

    if convert_letter(testtree.left, letter) == True:
        result  = "1"
        return result
    elif convert_letter(testtree.right, letter) == True:
        result  = "0"
        return result

...您沒有捕獲所有成功的搜索，因為成功的搜索將回傳“0”和“1”的實際字串，這顯然不是True。在這種情況下，執行無需執行else并回傳None——即使在更深的節點中找到了該字母。

你的函式不應該回傳一個布林值——它也不匹配型別提示。它應該是一個字串（結果）。您可以保留None以指示未找到該信件。

其他一些問題：

• result = "0"將附加數字，但由于您已經進行了遞回呼叫，因此您需要添加數字- 因為您現在在樹中較高。

• 樹的初始化使樹與影像中的樹不同：A應該是左孩子，而不是右孩子。所以應該是join('START', A, B)

通過這些修復，您將擁有以下代碼：

def convert_letter(testtree: BinaryTree, letter: str) -> str:
    global result
    if testtree is None:
        result = None  # Not found here 
    elif testtree.root == letter:
        result = ''  # Found! Start a path
    elif convert_letter(testtree.left, letter) is not None:
        result = "1"   result  # Prepend
    elif convert_letter(testtree.right, letter) is not None:
        result = "0"   result  # Prepend
    else:
        result = None  # Not found here
    return result

如果你也正確使用join('START', A, B)，那么輸出將是10。

更好的實踐

有些事情你可以做得更好：

• 不要使用全域變數來存盤函式結果。當您回傳它時，您可以result將從遞回呼叫中獲得的作為區域變數捕獲，添加到它之前，然后再次回傳它。

• 的定義EMPTY使您的樹變得不必要地大。只是None用來表示一棵空樹。

• Don't call a node's value root. A rooted tree has only one root, and it is a node, not a value of a node. So call that attribute value or data, but not root.

• The join function is nice, but why not use the constructor for that feature? The constructor can take those arguments as optional and immediately initialise the left and right attributes with those arguments.

• The code-comment above the convert_letter function describes the opposite from what the function does.

Taking all that into account, your code could look like this:

class BinaryTree:
    def __init__(self, value, left: 'BinaryTree'=None, right: 'BinaryTree'=None):
        self.value = value
        self.left = left
        self.right = right

def convert_letter(tree: BinaryTree, letter: str) -> str:
    if not tree:
        return # Not found here, return None
    if tree.value == letter:
        return ""  # Bingo: return an empty path
    # No more global. path is a local variable
    path = convert_letter(tree.left, letter)
    if path is not None:
        return "1"   path
    path = convert_letter(tree.right, letter)
    if path is not None:
        return "0"   path

# Look how nice it is to create a tree using the constructor arguments
binary = BinaryTree("Start",
    BinaryTree("A",
        BinaryTree("C"), BinaryTree("D")
    ),
    BinaryTree("B",
        BinaryTree("E"), BinaryTree("F")
    )
)

# Test
test = 'D'
print(convert_letter(binary, test))  # 10

標籤：python recursion binary-tree

上一篇：自行列印到控制臺的遞回階乘函式（C#）

下一篇：Java：For回圈在遞回函式中的一個元素后停止