为什么在预序遍历（二叉搜索树）上使用递归？

Question

我在下面有这 3 种不同的遍历方法，它们遍历我的二叉搜索树。我知道后序和中序遍历都是从底部到根，但前序是从根到底部。既然递归是自下而上的，为什么要在前序遍历上使用递归呢？我能找到的所有预购示例都使用递归。

private void preOrder(BinaryNode<AnyType> t )

    {

        if(isEmpty()){

            System.out.println("Empty");

        }

        if(t != null) {

            System.out.println(t.element);

            preOrder(t.left);

            preOrder(t.right);

        }

    }

    private void postOrder(BinaryNode<AnyType> t){

        if(isEmpty()){

            System.out.println("Empty");

        }

        if (t != null) {

            postOrder(t.left);

            postOrder(t.right);

            System.out.println(t.element);

        }

    }

    private void inOrder(BinaryNode<AnyType> t)

    {

        if(isEmpty()){

            System.out.println("Empty");

        }

        if (t != null) {

            inOrder(t.left);

            System.out.println(t.element);

            inOrder(t.right);

        }

    }

Answer 1

好吧，关键是当我们打印树的节点时。后序：System.out.println放置在所有递归调用之后，因此算法遍历所有节点直到结束，然后开始打印它们。对于预购情况，打印当前节点，然后处理子树。没有像“递归自下而上或自上而下”这样的规则。但是如果您在递归调用之前有一些代码，它将自上而下执行。如果您在递归调用后有一些代码，它将自下而上执行。