如何遍历树以从HuffmanTree生成二进制代码？

Question

我想用哈夫曼树做二进制代码。我被困在树遍历。为了遍历树并打印每个字符频率的代码，我编写了以下代码。你知道吗

def printCode(node,prefix=""):
    if node.left:
        prefix = prefix+"0"
        printCode(node.left,prefix)
    elif node.right:
        prefix = prefix+"1"
        printCode(node.right,prefix)
    elif node.internal ==False:
        print(node.data,prefix)
        printCode(node,prefix="") #need change 

以下是必要的解释： 如果节点不是内部节点(node.internal=假)然后它是一片叶子，在这个遍历点，我用字符频率打印代码。但我无法返回到上一个内部节点并继续使用另一个尚未遍历的分支树。因此，此代码仅返回树的第一个叶的二进制代码。你知道吗

树的每个节点都使用以下代码创建：

class Node:
    def __init__(self,data,internal=False):
        self.data = data  #frequency of a char
        self.internal = internal

        self.left = None
        self.right = None

Answer 1

逻辑的主要问题是使用elif

def printCode(node):
    if node.left:
        node.left.prefix = node.prefix+"0"
        printCode(node.left)

    if node.right:
        node.right.prefix = node.prefix+"1"
        printCode(node.right)

    if node.internal == False:
        print(node.data,node.prefix)

通过这种方式，它将遍历树的左侧，直到到达某个叶，当到达某个叶时，它将打印节点数据。在代码的这一点上，它返回到最后一个递归调用（叶子之前的节点），它将返回到正确的节点，如果这个正确的节点是叶子，它将打印出它的节点信息，然后它将返回到最后一个递归调用

如果你需要一个更好的解释，或者如果有一个误解，这不符合你的要求，请告诉我

更新：

class Node:
    def __init__(self,data,internal=False):
        self.data = data  #frequency of a char
        self.internal = internal

        self.left = None
        self.right = None

        #Add a prefix to your nodes, so each node keeps track of its own prefix
        self.prefix = ""