Простой способ найти Поддерево в Дереве

Question

Простой способ найти Поддерево в Дереве

Если мы обращаемся к репо tensorflow , мы можем получить ответ:

// Порядок записей в «dim» имеет значение: он указывает макет
// значений в тензорном представлении в памяти.
//
// Первая запись в «dim» - это самое внешнее измерение, используемое для компоновки значений
//, последняя запись - это самое внутреннее измерение . Это соответствует
// расположению в памяти тензоров RowMajor Eigen.
blockquote>
(выделено мной)

Это то же самое, что макет по умолчанию (основной ряд, также называемый стилем C) для массивов numpy, где последнее измерение считается самым внутренним потому что меняется быстрее всего .

5

tree algorithm java

задан Pete Kirkham 24 March 2009 в 12:17

3 ответа

Вы ищете какие-либо конкретные ограничения на поддерево? В противном случае простой обход должен быть достаточным для идентификации поддеревьев (в основном рассматривают каждый узел как корень поддерева).

Я полагаю, что Вы найдете, что API, который Вы захотите для дерева, варьируется много Вашим конкретным приложением - так много, что универсальные реализации не очень полезны. Возможно, если Вы могли бы сказать нам, для какого приложения дерево будет использоваться, мы могли обеспечить подробные сведения.

Кроме того, если Вы просто используете дерево для хранения данных, Вы могли бы хотеть спросить себя, почему Вам нужно дерево. Тот ответ должен также ответить на вопрос в моем предыдущем абзаце.

2

ответ дан 14 December 2019 в 04:48

Интересно, существует ли расширение алгоритма Knuth, который был бы более эффективным, чем наивный обход...

0

ответ дан 14 December 2019 в 04:48

Другие вопросы по тегам:

tree algorithm java

Похожие вопросы:

score 6 · Accepted Answer

Похож на простой алгоритм: Найдите корень дерева поиска в игровом дереве и проверьте, являются ли дети дерева поиска подмножеством детей в игровом дереве.

От Ваших объяснений я не уверен ли дерево поиска

  A
 / \
A   A

должен соответствовать этому дереву:

  A
 /|\
A C A

(т.е. если несоответствующие дети, как предполагается, проигнорированы.)

Так или иначе вот код, с которым я просто играл вокруг. Это - полностью рабочий пример и идет с основным методом и простым Node класс. Не стесняйтесь играть с ним:

import java.util.Vector;

public class PartialTreeMatch {
    public static void main(String[] args) {
        Node testTree = createTestTree();
        Node searchTree = createSearchTree();

        System.out.println(testTree);
        System.out.println(searchTree);

        partialMatch(testTree, searchTree);
    }

    private static boolean partialMatch(Node tree, Node searchTree) {
        Node subTree = findSubTreeInTree(tree, searchTree);
        if (subTree != null) {
            System.out.println("Found: " + subTree);
            return true;
        }
        return false;
    }

    private static Node findSubTreeInTree(Node tree, Node node) {
        if (tree.value == node.value) {
            if (matchChildren(tree, node)) {
                return tree;
            }
        }

        Node result = null;
        for (Node child : tree.children) {
            result = findSubTreeInTree(child, node);

            if (result != null) {
                if (matchChildren(tree, result)) {
                    return result;
                }
            }
        }

        return result;
    }

    private static boolean matchChildren(Node tree, Node searchTree) {
        if (tree.value != searchTree.value) {
            return false;
        }

        if (tree.children.size() < searchTree.children.size()) {
            return false;
        }

        boolean result = true;
        int treeChildrenIndex = 0;

        for (int searchChildrenIndex = 0;
                 searchChildrenIndex < searchTree.children.size();
                 searchChildrenIndex++) {

            // Skip non-matching children in the tree.
            while (treeChildrenIndex < tree.children.size()
                  && !(result = matchChildren(tree.children.get(treeChildrenIndex),
                                              searchTree.children.get(searchChildrenIndex)))) {
                treeChildrenIndex++;
            }

            if (!result) {
                return result;
            }
        }

        return result;
    }

    private static Node createTestTree() {
        Node subTree1 = new Node('A');
        subTree1.children.add(new Node('A'));
        subTree1.children.add(new Node('A'));

        Node subTree2 = new Node('A');
        subTree2.children.add(new Node('A'));
        subTree2.children.add(new Node('C'));
        subTree2.children.add(subTree1);

        Node subTree3 = new Node('B');
        subTree3.children.add(subTree2);

        Node root = new Node('A');
        root.children.add(subTree3);

        return root;
    }

    private static Node createSearchTree() {
        Node root = new Node('A');
        root.children.add(new Node('A'));
        root.children.add(new Node('A'));

        return root;
    }
}

class Node {
    char value;
    Vector<Node> children;

    public Node(char val) {
        value = val;
        children = new Vector<Node>();
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();

        sb.append('(');
        sb.append(value);

        for (Node child : children) {
            sb.append(' ');
            sb.append(child.toString());
        }

        sb.append(')');

        return sb.toString();
    }
}