Расшифровать дерево из файла

Question

Помогите создать дерево используя 2 массива типа LinkedList treeShape, LinkedList treeLeaves. Последовательность битов описывает структуру узлов в порядке как при прямом обходе дерева. Если лист - это 0, иначе 1. Листья - в порядке как они встречаются при обходе дерева по порядку. Из этого всего надо собрать дерево, а потом это дерево использовать для расшифровки по Хаффману.

    private HashMap<Byte, Node> createHuffmanTree(HashMap<Byte, Integer> uniqueSequences) {
        HashMap<Byte, Node> codingTable = new HashMap<>();
        PriorityQueue<Node> tree = new PriorityQueue<>();

        //I am creating leaves that only store characters.
        for (Map.Entry<Byte, Integer> entry : uniqueSequences.entrySet()) {
            Node leaf = new Node(entry.getValue(), entry.getKey());
            codingTable.put(entry.getKey(), leaf);
            tree.add(leaf);
        }

        //I iterate over all the trees until there is only 1 left.
        while (tree.size() > 1) {
            Node first = tree.poll();
            Node second = tree.poll();
            tree.add(new Tree(first, Objects.requireNonNull(second)));
        }

        //I create binary sequences (path) for each character in the tree.
        Node root = tree.poll();
        if (codingTable.size() == 1) {
            Objects.requireNonNull(root).createBitSequence("0");
        } else {
            Objects.requireNonNull(root).createBitSequence("");
        }

        return codingTable;
    }

по обходе дерева используя частоты я разобрался а вот построить такое же дерево используя шаблон выше - туговато(

Answer 1

В общем реализовал с помощью стека, а хотел неявной рекурсией в дереве...

public EncodingTreeNode unflattenTree(LinkedList<Boolean> treeShape, LinkedList<Byte> treeLeaves) {
    Stack<EncodingTreeNode> stack = new Stack<>();
    EncodingTreeNode parent = new EncodingTreeNode();
    stack.push(parent);
    for (int i = 1; i < treeShape.size(); i++) {
        EncodingTreeNode previousNode = stack.peek();
        if (treeShape.get(i)) {
            if (previousNode.leftNode == null) {
                previousNode.leftNode = new EncodingTreeNode();
                stack.push(previousNode.leftNode);
            } else if (previousNode.rightNode == null) {
                previousNode.rightNode = new EncodingTreeNode();
                stack.pop();
                stack.push(previousNode.rightNode);
            }
        } else {
            if (previousNode.leftNode == null) {
                previousNode.leftNode = new EncodingTreeNode(treeLeaves.pollFirst());
            } else if (previousNode.rightNode == null) {
                previousNode.rightNode = new EncodingTreeNode(treeLeaves.pollFirst());
                stack.pop();
            }
        }
    }
    return parent;
}

БЛОГ НА HUSL

Расшифровать дерево из файла

Ответы (1 шт):