二叉樹遍歷

Question

我做了一個二叉樹，並試圖做一個後序遍歷。我已經做了一個前序遍歷 - 我雖然是我需要的。但谷歌遍歷後，我發現它是後我需要。 我的想法是在左邊出來，然後右邊，然後是根（這是後序權利？:)）的遍歷。 我試圖實現它，但它看起來有點奇怪的出落得

public static <E> String postorder(BinaryTree<E> t, Position<E> v){ 
    String tree = ""; 
    if(t.hasLeft(v)){ 
     tree += postorder(t, t.left(v)); 
    } 
    tree += v.element() +", "; 
    if(t.hasRight(v)){ 
     tree += postorder(t, t.right(v)); 
    } 
    return tree; 
} 

我的樹是：

  45 
     / \ 
      22 77 
     /\  \ 
     11 30  90 
     \ / /
     15 25 88 

我的結果應該是我的知識後 15,11,25,30 ，22,88,90,77,45 但是它是 11,15,22,25,30,45,77,88,90

任何人都可以看到我做錯了什麼 - 我已經嘗試了很多東西。什麼都沒有

Answer 1

您在postorder的執行範圍內致電preorder。

---

更新：現在它看起來像你正在做的有序遍歷，但調用它後序。

移動這一行：

tree += v.element() +", "; 

到端部（右返回之前）。

Answer 2

void preOrder(BSTNode *root){ 
    while(root != NULL){ 
     cout<<root->data<<endl; 
     preOrder(root->left); 
     preOrder(root->right); 
    } 
} 

void postOrder(BSTNode *root){ 
    while(root != NULL){ 
     preOrder(root->left); 
     preOrder(root->right); 
     cout<<root->data<<endl; 
    } 
} 

void inOrder(BSTNode *root){ 
    while(root != NULL){ 
     preOrder(root->left); 
     cout<<root->data<<endl; 
     preOrder(root->right); 
    } 
}