In-order tree traversal

问题:

I have the following text from an academic course I took a while ago about in-order traversal (they also call it pancaking) of a binary tree (not BST):

In-order tree traversal

Draw a line around the outside of the tree. Start to the left of the root, and go around the outside of the tree, to end up to the right of the root. Stay as close to the tree as possible, but do not cross the tree. (Think of the tree — its branches and nodes — as a solid barrier.) The order of the nodes is the order in which this line passes underneath them. If you are unsure as to when you go “underneath” a node, remember that a node “to the left” always comes first.

Here's the example used (slightly different tree from below)

However when I do a search on google, I get a conflicting definition. For example the wikipedia example:

Inorder traversal sequence: A, B, C, D, E, F, G, H, I (leftchild,rootnode,right node)

But according to (my understanding of) definition #1, this should be

A, B, D, C, E, F, G, I, H

Can anyone clarify which definition is correct? They might be both describing different traversal methods, but happen to be using the same name. I'm having trouble believing the peer-reviewed academic text is wrong, but can't be certain.

回答1:

In my bad attempt at the drawing here's the order that shows how they should be picked.

pretty much pick the node that is directly above the line being drawn,.

回答2:

Forget the definitions, it's so much easier to just apply the algorithm:

void inOrderPrint(Node root)
{
  if (root.left != null) inOrderPrint(root.left);
  print(root.name);
  if (root.right != null) inOrderPrint(root.right);
}

It's just three lines. Rearrange the order for pre- and post- order.

回答3:

If you read carefully you see that the first "definition" says to start left of the root and that the order of the nodes is determined by when you pass under them. So B is not the first node, as you pass it from the left on the way to A, then first pass under A after which you go up and pass under B. Therefore it seems that both definitions give the same result.

回答4:

I personally found this lecture quite helpful.

回答5:

Both definitions give the same result. Don't be fooled by the letters in the first example - look at the numbers along the path. The second example does use letters to denote the path - perhaps that is what is throwing you off.

For example, in your example order showing how you thought the second tree would be traversed using the algorithm of the first one, you place "D" after "B" but you shouldn't because there is still a left-hand child node of D available (that's why the first item says "the order in which this line passes underneath them."

回答6:

this may be late but it could be useful for anyone later .. u just need not to ignore the dummy or null nodes e.g the Node G has a left null node .. considering this null node will make every thing alright ..

回答7:

The proper traversal would be: as far left as possible with leaf nodes (not root nodes)

Left Root Right

A B NULL

C D E

Null F G

H I NULL

F is root or left, i am not sure

回答8:

I think the first binary tree with the root of a is a Binary tree which is not correctly constructed.

Try to implement so that all the left side of the tree is less than the root and all the right side of the tree is greater than or equal to the root.

回答9:

But according to (my understanding of) definition #1, this should be

A, B, D, C, E, F, G, I, H

Unfortunately, your understanding is wrong.

Whenever you arrive at a node, you must descend to an available left node, before you look at the current node, then you look at an available right node. When you chose D before C, you didn't descend to the left node first.

回答10:

Hey according to me as mentioned in wiki is correct the sequence for a inorder traversal is left-root-right.

Till A, B, C, D, E, F i think you have understood already. Now after root F the next node is G that doesn't hav a left node but a right node so as per the rule (left-root-right) its null-g-right. Now I is the right node of G but I has a left node hence the traversal would be GHI. This is correct.

Hope this helps.

回答11:

For an inline tree traversal you have to keep in mind that the order of traversal is left-node-right. For the above diagram that you are conflicted on, your error occurs when you read a parent node before reading any leaf(children) nodes to the left.

The proper traversal would be: as far left as possible with leaf nodes(A), return to parent node(B), move to the right, but since D has a child to its left you move down again(C), back up to C's parent(D), to D's right child(E), reverse back to the root(F), move to the right leaf(G), move to G's leaf but since it has a left leaf node move there(H), return to parent(I).

the above traversal reads the node when I have it listed in parenthesis.

回答12:

package datastructure;

public class BinaryTreeTraversal {

public static Node<Integer> node;

public static Node<Integer> sortedArrayToBST(int arr[], int start, int end) {
    if (start > end)
        return null;

    int mid = start + (end - start) / 2;
    Node<Integer> node = new Node<Integer>();
    node.setValue(arr[mid]);

    node.left = sortedArrayToBST(arr, start, mid - 1);
    node.right = sortedArrayToBST(arr, mid + 1, end);
    return node;
}

public static void main(String[] args) {

    int[] test = new int[] { 1, 2, 3, 4, 5, 6, 7 };
    Node<Integer> node = sortedArrayToBST(test, 0, test.length - 1);

    System.out.println("preOrderTraversal >> ");

    preOrderTraversal(node);

    System.out.println("");

    System.out.println("inOrderTraversal >> ");

    inOrderTraversal(node);

    System.out.println("");

    System.out.println("postOrderTraversal >> ");

    postOrderTraversal(node);

}

public static void preOrderTraversal(Node<Integer> node) {

    if (node != null) {

        System.out.print(" " + node.toString());
        preOrderTraversal(node.left);
        preOrderTraversal(node.right);
    }

}

public static void inOrderTraversal(Node<Integer> node) {

    if (node != null) {

        inOrderTraversal(node.left);
        System.out.print(" " + node.toString());
        inOrderTraversal(node.right);
    }

}

public static void postOrderTraversal(Node<Integer> node) {

    if (node != null) {

        postOrderTraversal(node.left);

        postOrderTraversal(node.right);

        System.out.print(" " + node.toString());
    }

}

}

package datastructure;

public class Node {

E value = null;
Node<E> left;
Node<E> right;

public E getValue() {
    return value;
}

public void setValue(E value) {
    this.value = value;
}

public Node<E> getLeft() {
    return left;
}

public void setLeft(Node<E> left) {
    this.left = left;
}

public Node<E> getRight() {
    return right;
}

public void setRight(Node<E> right) {
    this.right = right;
}

@Override
public String toString() {
    return " " +value;
}

}

preOrderTraversal >> 4 2 1 3 6 5 7 inOrderTraversal >> 1 2 3 4 5 6 7 postOrderTraversal >> 1 3 2 5 7 6 4

回答13:

void
inorder (NODE root)
{
  if (root != NULL)
    {
      inorder (root->llink);
      printf ("%d\t", root->info);
      inorder (root->rlink);
    }
}

This the most simplest approach to recursive definition of in-order traversal, just call this function in the main function to get the in-order traversal of a given binary tree.

回答14:

It is correct for preorder,nt for inorder