Как напечатать 2-3 дерева от мин до макс?

Question

Я не знаю, как подойти к алгоритму. Я думал что-то вроде этого:

TreeNode n = root;
while(n.first.first!=0){ 
    n=n.first;
} // finding the leftMost parent
//printing the first child key, then first num of parent, then second child.. and so on

У кого-нибудь есть идея получше?

Answer 1

Согласно 2-3 определениям дерева, вы можете встретить 3 типа узлов:

• внутренний узел с 2 дочерними и 1 значением
• внутренний узел с 3 дочерними и 2 значениями
• лист без детей и 1 или 2 значения

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

Вот псевдокод. Я оставил фактическую реализацию для себя. Изучите это и убедитесь, что вы понимаете поток метода (вы можете использовать отладчик и отслеживать фактические параметры)

/* you start algorithm by calling recursivePrint(root) */

void recursivePrint(node){

    if (node is a leaf){

        /* Here print node's value/values */

    } else if (node has 2 children){

        recursivePrint(node.leftChild);
        /* Here print node's value */
        recursivePrint(node.rightChild);

    } else if (node has 3 children)

        recursivePrint(node.leftChild);
        /* Here print node's left value */
        recursivePrint(node.middleChild);
        /* Here print node's right value */
        recursivePrint(node.rightChild)

    }

    /* Shouldn't be other cases in 2-3 trees */
}