PostOrder обход бинарного дерева непоследовательно переходит к родному брату или родителю

Question

При вводе следующих значений ({18, 26, 52, 78, 45, 16, 67, 58, 73, 11}) в двоичном дереве вы получаете это дерево:

И обходы PreOrder, и InOrder работают так, как я ожидаю. Однако, когда дело доходит до PostOrder (PO), я получаю нечто иное, чем я мог бы подумать.

Насколько я понимаю, PO сначала ищет через левое поддерево, затем правое поддерево и, в конце концов, узел (заканчивающийся корневым узлом).

При прохождении PO через это дерево вы получите следующий результат: {11, 16, 45, 58, 73, 67, 78, 52, 26, 18}. При написании логики, лежащей в основе этого результата, вы получаете следующее: Начиная с корня, после полного левого, вы в конечном итоге в 11, который является вашим первым узлом. После этого вы поднимаетесь на один уровень вверх и берете его родителя (16). Вы продолжаете делать это, пока не достигнете корня (который не включается, потому что это не leftChild). После того, как вы прошли через это начальное левое поддерево, вы переходите на уровень вниз справа и проверяете там левых детей. Если их нет, вы переходите на другой уровень, где мы находим 45.

На данный момент у нас есть список {11, 16, 45}. Мы продолжаем это и в конечном итоге в 58, что является нашим следующим значением в результате. Вот тут-то и возникает моя путаница: следующее значение, которое мы получаем, - 73, в отличие от ожидаемого 67. Почему оно перешло на 73, когда есть еще один leftChild (его родитель)?

Следующий код выполняет обход дерева в PostOrder:

public void postorderTraversal(){
    postorderHelper(root);
}

private void postorderHelper(Node node){
    if(node != null){
        postorderHelper(node.getLeftNode());
        postorderHelper(node.getRightNode());
        System.out.print(node.getData() + " ");
    }
}

Я предполагаю, что это потому, что узел со значением 73 обрабатывается до parentNode (приоритет слева-справа-сверху), но почему тогда это не так в треугольнике 45-52-78?

Answer 1

Я предполагаю, что это потому, что узел со значением 73 обрабатывается до parentNode (приоритет слева-справа-сверху), но почему тогда это не так в треугольнике 45-52-78?

То есть, в этом 45 предшествует 78, что предшествует 52.

Левый брат всегда будет посещаться раньше правого брата, который всегда будет посещаться раньше родителя. Что еще будет посещено между ними, будет зависеть от того, какие дети у левых и правых братьев и сестер.

Страница википедии об обходе дерева описывает это как:

Чтобы пройти непустое двоичное дерево в порядке заказа, выполните следующие операции рекурсивно на каждом узле:

• Пройдите через левое поддерево.
• Пройдите правое поддерево.
• Посетите корень.

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