樹的遍歷 Tree traversal (15點!)

首先了解節點的結構
struct BTreeNode
{
struct BTreeNode *Left;
int data;
struct BTreeNode *Right;
}struct BTreeNode *root;

LVR L走訪左邊 R走訪右邊 V節點上的資料

前序 VLR
中序 LVR
後序 LRV

假設樹的形狀是 http://w00073.myweb.hinet.net/bigtree.bmp
(我畫圖)

前序 VLR 則：1246753 (可由下列片段程式理解，遞回的概念)

void preorder (struct BTreeNode *node)
{
if(node !=NULL)
{ //印出節點資料 V
preorder(node->Left); //L
preorder(node->Right); //R

}
}
簡單的說...先印出資料後，呼叫自己(遞回)，然後在印出，又呼叫自己直到左邊都印完再開始印右邊。
中序 LVR 則：6472513
後序 LRV 則：6745231

不懂或是有說錯在發問吧!

Note I've got a 300 word limit.
Using the tree structure from wiki as an example:
http://en.wikipedia.org/wiki/Tree_traversal

Preorder: F B A D C E G I H (Root, L, R)
Inorder: A B C D E F G H I (L, Root, R)
Postorder: A C E D B H I G F (L, R, Root)

Given preoder and inorder list, to generate postorder list:

function postorder (preorder inorder)
1. if there is 1 element in the inorder list, print out and return
2. From preorder, you know the root is the first element of preorder.
3. From preorder, you get the next element is the immediate left child
and the immediate right child from the inorder list.
3. find the new preorder and inorder list for the left child and call
this function recursively.
4. find the new preorder and inorder list for the right child and call
this function recursively.
5. print the first element of preorder.

Example:
Initial call:
Preorder: F B A D C E G I H
Inorder: A B C D E F G H I
1. From preorder, you know the root is F.
2. Given F, from preorder, you get B is the immediate left child (preordering, B is right after F) and get G is the immediate right child from the inorder list (inordering, G is right after F).
3. send the list BADCE as the new preorder and ABCDE as the new inorder to function postorder recursively.
4. Send the list GHI as the new preorder and GIH as the new inorder to function postorder recursively.
5. print F

Note that step 3 is the left child, step 4 is the right child so L, R, Root.

Recursive:
Preorder: BADCE
Inorder: ABCDE
1. From preorder, you know the root is B.
2. Given B, from preorder, you get A is the immediate left child from preorder list and get C is the immediate right child from the inoder list
3. send the list A as preorder and A as inorder and call function postorder recursively
4. send the list DCE as preorder and CDE as inorder recursively call postorder
5. print B

...