Редактировать узлы в двоичном дереве в Java

Question

Хорошо. У меня есть двоичное дерево, и вот что я хочу с ним сделать:

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

Проблема в следующем: я обхожу дерево, используя стек. Если я изменю узел stack.pop () на лист, это НЕ удалит все ветви в исходном дереве. Это то же самое объяснение, почему вы можете сделать:

int x=1
int y=x
y++

И х по-прежнему равен 1. Для этого есть технический термин, но я его забыл.

Так, как я могу отредактировать узлы в исходном дереве и все же пройти по нему?

Это в основном то, что я делаю, чтобы пройти по дереву прямо сейчас:

public void iterativePreorder(Node root) {
        Stack nodes = new Stack();
        nodes.push(root);

        Node currentNode;

        while (!nodes.isEmpty()) {
                currentNode = nodes.pop();
                Node right = currentNode.right();
                if (right != null) {
                        nodes.push(right);
                }
                Node left = currentNode.left();
                if (left != null) {
                        nodes.push(left);      
                }
                //This is where you do operations on the currentNode
        }
}

Answer 1

Из того, что я могу сказать из вашего вопроса, для каждого Node вы хотите вычислить что-то о дереве, как если бы этот узел был листом.

Для этого нет никаких оснований фактически делать этоУзел лист, а затем снова прикрепить его.Вместо этого ваша логика может просто запомнить, какой узел обрабатывать как лист для каждого вычисления.

Обходить дерево, а для каждого Node назовем его outerCurrentNode, еще раз обойти дерево, выполняя ваш расчет- но теперь для каждого Node, давайте назовем это innerCurrentNode, проверим, если outerCurrentNode == innerCurrentNode.Если тест возвращает true, обработайте этот innerCurrentNode как лист, игнорируя его дочерние элементы.

РЕДАКТИРОВАТЬ: Вот пример того, что я предлагаю (не проверено):

//entry point - called from directing code
public void iterativePreorder(Node root) {
   iterativePreorderKernel(root, root);
}

//recursive method - keeps track of root in addition to current Node
private void iterativePreorderKernel(Node root, Node current) {

    if (current.left() != null) {
        iterativePreorderKernel(root, current.left());
    }
    if (current.right() != null) {
        iterativePreorderKernel(root, current.right());
    }

    //for each Node in the tree, do calculations on the entire tree, pretending
    //the current Node is a leaf
    doCalculation(root, current);
}

//calculation method (also recursive) - takes a current Node, plus
//the Node to treat as a leaf
public void doCalculation(Node innerCurrent, Node pretendLeaf) {

   //do calculation with inner current node

   if (innerCurrent != pretendLeaf) {
      if (innerCurrent.left() != null) {
         doCalculation(innerCurrent.left(), pretendLeaf);
      }
      if (innerCurrent.right() != null) {
         doCalculation(innerCurrent.right(), pretendLeaf);
      }
   }
}

Я использую рекурсию вместо Stack, но любой из них будет работать.iterativePreorder() выполняет обход, вызывая doCalculation() для каждого Node, передавая его вместе с корнем (для отслеживания всего дерева).Затем этот метод выполняет свой собственный обход, выполняя ваши вычисления, но останавливаясь на короткой позиции, когда достигает особо отмеченного Node.