python - 如何遍历树以从 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=False)，那么它就是一片叶子，在遍历的这一点上，我正在打印带有字符频率的代码。但是我无法返回到之前的内部节点并继续处理另一个尚未遍历的树分支。所以这段代码结束时只返回树的第一个叶子的二进制代码。

树的每个节点都是用下面的代码创建的:

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 = ""