Как пройти по дереву для создания двоичного кода из HuffmanTree? - PullRequest
Новая
       56

Как пройти по дереву для создания двоичного кода из HuffmanTree?

0 голосов
/ 13 декабря 2018

Я пытаюсь сделать двоичный код из дерева Хаффмана.Я застрял в обход дерева.Чтобы обойти дерево и напечатать код для каждой частоты символов, я написал следующий код. 

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

1 Ответ

0 голосов
/ 13 декабря 2018

Основная проблема с вашей логикой - использование 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 = ""
...