当最左边的节点具有右子节点时，有序树遍历(In

当最左边的节点具有右子节点时，有序树遍历(In-order tree traversal when leftmost node has right child)

我有这样一棵树：

如果我在这棵树上执行有序树遍历，则输出为：

d，h，b ......

要么

d，b，h ......

换句话说，感觉有序树遍历向左 - >根 - >右，当最左边的节点有一个正确的孩子时会发生什么？

我的猜测是按顺序对子树进行操作，如果我们将d作为最左边子树的根，那么输出应该是

d，h，b ......

我是否正确地考虑过这个问题？

I have a tree like this:

If I do an in-order tree traversal on this tree would the output be:

d, h, b...

or

d, b, h...

In other words sense in-order tree traversal goes left -> root -> right, what happens when the leftmost node has a right child?

My guess is that in-order operates on subtrees and if we take d as the root of the leftmost subtree then the output should be

d, h, b...

Am I thinking about this correctly?

最满意答案

是的，你是对的，d，h，b，......是正确的顺序。 很容易看到，因为d和h都在b的左子树中，因此必须在b之前。

Yes, you are right, d,h,b,... is the correct order. Easy to see, because both d and h are in the left subtree of b and must therefore come before b.