Skip to main content
 首页 » 编程设计

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

2024年12月31日13落叶无声

我正在尝试从哈夫曼树生成二进制代码。我被困在树遍历。为了遍历树并打印每个字符频率的代码,我编写了以下代码。

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 

请您参考如下方法:

你的逻辑的主要问题是 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 = ""