Бинарное дерево из общего дерева

Question

У меня есть древовидная структура, в которой есть узел с родительским идентификатором (неограниченное количество дочерних узлов).Для целей отображения мне нужна эта древовидная структура в виде двоичного дерева.Как я это делаю, на каждом уровне узлы группируются в один узел на основе условия.Когда узел выбран, отображаются его дочерние элементы.Пример:

Зеленый - это когда условие true, а красный - false

B,C были сгруппированы в левый узел, а D, E - справа в зависимости от их условий.

ВОПРОС: Я использую KnockoutJS для отображения своего дерева, и мне нужно иметь возможностьвыполнять обычные операции с деревом, такие как получение узла на основе его идентификатора, вставка узла (ов) и удаление узла (ов).Это структура, которую я имею.Есть ли лучшая структура / способ сделать это?

var tree = [
    { groupNodeId: "A", childNodes: [
        { nodeId: "A", childGroupNodes: [
            { groupNodeId: "B", condition: true, childNodes: [
                { nodeId: "B", childGroupNodes: []},
                { nodeId: "C", childGroupNodes: []}
            ]},
            { groupNodeId: "D", condition: false, childNodes: [
                { nodeId: "D", childGroupNodes: []},
                { nodeId: "E", childGroupNodes: []}
            ]}
        ]}
    ]}
];

Answer 1

Я не совсем уверен, что вы хотите, но при условии, что:

1. Вы хотите вставить «groupNodes», а не обычные узлы, и чтобы у groupNodes могли быть неограниченные дочерние элементы.
2. Исходное дерево содержит только обычные узлы, а не groupNodes.
3. Все обычные узлы имеют идентификатор узла, условие, установленное в true или false, и массив childNodes.
4. Вы не хотите создавать групповые узлы, которые не имеют дочерних элементов.

тогда вот ваш ответ.

function binize(tree) {
  var left,right,t,u,
    stack=[tree];
  while(t=stack.pop()) {
    left=[];
    right=[];
    while(u=t.childNodes.pop()) {
      (u.condition?left:right).push(u);
      stack.push(u);
    }
    left.length&&t.childNodes.push({
      groupNodeId:left[0].nodeId,
      condition:true,
      childNodes:left
    });
    right.length&&t.childNodes.push({
      groupNodeId:right[0].nodeId,
      condition:false,
      childNodes:right
    });
  }
}

Я протестировал его, используя эту структуру данных (обратите внимание, что дерево - это объект верхнего уровня, а не массив, содержащий его).

var tree={nodeId:'A',childNodes:[
  {nodeId:'B',condition:true,childNodes:[]},
  {nodeId:'C',condition:true,childNodes:[]},
  {nodeId:'D',condition:false,childNodes:[
    {nodeId:'F',condition:false,childNodes:[]},
    {nodeIf:'G',condition:false,childNodes:[]}
  ]},
  {nodeId:'E',condition:false,childNodes:[]}
]};

Если бы я знал немного больше о вашем дереве, то мог бы пойти другим путем. Например, если дерево не очень глубокое, то может быть более эффективно (и, конечно, чище) рекурсивно копаться в нем.

Кроме того, я никогда раньше не использовал KnockoutJS и не знаю, какие структуры ему нравятся. Я просто создал структуры, которые вы указали; надеюсь, это сработает.