Как передать данные своим потомкам в древовидной структуре данных

Question

Как пройти через эту древовидную структуру данных, передавая значение ее дочерним элементам в javascript. Процент используется для разделения передачи значения на «N» и «Y»

Вот изображение, например

Answer 1

Не зная вашей структуры данных, я предложу использовать класс Node со свойствами:

• дробь (процент от 0 до 1),
• две ссылки на дочерние узлы (одна для «нет», другая для «да») и
• значение, которое вначале равно 0, но определяется после расчета.

Алгоритм будет рекурсивным, где вы начнете с корня и введете 1000 в него. Этот узел будет применять дробь к этому значению (то есть умножать) и добавлять результат к своему собственному значению. Затем это значение рекурсивно вводится в дочерний элемент «yes» (если он есть), а оставшееся значение рекурсивно вводится в дочерний элемент «no».

Важно добавить значение к существующему значению узла, так как некоторые узлы могут получать входные данные от нескольких "родителей", как это имеет место в правой части примера графика. Эти несколько входов должны быть сложены.

Вот код JavaScript:

class Node {
    constructor(fraction) {
        this.fraction = fraction; // number between 0 and 1
        this.no = null; // child node for edge with label "N"
        this.yes = null; // child node for edge with label "Y"
        this.value = 0; // This will get a value later, as input is cascaded through the graph
    }
    setChildren(no, yes) {
        this.no = no;
        this.yes = yes;
    }
    addInput(value) {
        const addedValue = value * this.fraction;
        this.value += addedValue;
        if (value) { // dripple down the value through the outward edges
            if (this.no) this.no.addInput(value - addedValue);
            if (this.yes) this.yes.addInput(addedValue);
        }
    }
}

// Create vertices with their percentages (fractions)
const nodes = [
    new Node(1),
    new Node(0.5),
    new Node(0.8),
    new Node(1),
    new Node(0.13),
    new Node(0.5),
    new Node(1),
    new Node(0.3)
];

// Create edges
nodes[0].setChildren(null, nodes[1]);
nodes[1].setChildren(nodes[2], nodes[5]);
nodes[2].setChildren(nodes[3], nodes[4]);
nodes[4].setChildren(null, nodes[5]);
nodes[5].setChildren(nodes[6], nodes[7]);

// Send a value of 1000 to the root node
nodes[0].addInput(1000);

// Show the value of each node after this action
console.log("node  value");
for (const node of nodes) {
    console.log((node.fraction*100 + "%").padStart(4), node.value.toFixed(1).padStart(6));
}

Некоторые замечания

Хотя этот вопрос говорит о структуре данных дерева и помечен tree и tree-traversal, входной граф - это не дерево, а DAG .

В комментариях упоминается, что процентное значение используется для разбиения значения, которое идет в круг следующий , но на графике процентное отношение применяется к самому узлу . также: лист с процентом 30% получает значение 276, но все же изображение показывает, что к значению узла применены 30%.