带递归的中序遍历? [英] Inorder Traversal with Recursion?

问题描述

我刚刚开始学习树遍历，我很难理解这段用于有序树遍历的代码:

I have just started learning about tree traversal and I'm having a hard time understanding this code for a in-order tree traversal:

class tree {
   String data;
   tree left;
   tree right;
}

void inorder (tree root) {
   if (root == null) return;
   inorder (root.left);
   out.printf ("%s%n", root.data);
   inorder (root.right);
}

我不明白，一旦 root != null，那么程序执行不会继续递归调用 in order 方法的第 2 行吗?那不会导致执行打印语句?

I dont understand that, once root != null, then won't program execution keep recursively calling line 2 of the in order method? and that won't lead to execution of print statement?

推荐答案

代码遍历树，直到遇到未设置的根 - 即 left 或 right 为 null.如果发生这种情况，inorder 的当前执行将通过调用 return 退出(您可能会说是过早地).

The code traverses the tree until it hits a root that isn't set – i.e. left or right being null. If this happens, the current executon of inorder exits (prematurely, you might say) by calling return.

当使用return时，无论在方法的什么地方，方法都会终止，所以下面几行不会被执行.

When using return, no matter where in a method, the method will terminate, so the following lines are not being executed.

考虑树

为了表示这一点，你可以创建一个像

To represent this, you could create a structure like

Tree node4 = new Tree("Node 4", null, null);
Tree node5 = new Tree("Node 5", null, null);
Tree node2 = new Tree("Node 2", node4, node5);
Tree node6 = new Tree("Node 6", null, null);
Tree node7 = new Tree("Node 7", null, null);
Tree node3 = new Tree("Node 3", node6, node7);
Tree root  = new Tree("Root", node2, node3);

当在 root 上调用 inorder 时，你会得到:

When calling inorder on root, you'd get:

节点 4
节点 2
节点 5
根
节点 6
节点 3
节点 7

Node 4
Node 2
Node 5
Root
Node 6
Node 3
Node 7

请注意，我更新了 Tree 以拥有一个构造函数(并且将其大写，因为类应该使用大写字母).

Note that I updated Tree to have a constructor (and also uppercased it, since classes should being with a capital letter).

public Tree(String data, Tree left, Tree right) {
    this.data = data;
    this.left = left;
    this.right = right;
}

这篇关于带递归的中序遍历?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！