2011-11-19 228 views
1

我做了一个二叉树,并试图做一个后序遍历。我已经做了一个前序遍历 - 我虽然是我需要的。但谷歌遍历后,我发现它是后我需要。 我的想法是在左边出来,然后右边,然后是根(这是后序权利?:))的遍历。 我试图实现它,但它看起来有点奇怪的出落得二叉树遍历

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

任何人都可以看到我做错了什么 - 我已经尝试了很多东西。什么都没有

+0

修复了损坏的链接 我相信你会喜欢阅读如何进行遍历作品递归技术和算法的深度相同。我有一些时间写下来,请看看http://techieme.in/hierarchical-datastructure-tree-traversals - – dharam

回答

2

您在postorder的执行范围内致电preorder


更新:现在它看起来像你正在做的有序遍历,但调用后序

移动这一行:

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

到端部(右返回之前)。

+0

抱歉..错误的代码..我会更新问题 – Anne

+0

它现在更新。你能看到错误吗?它出来,而不是后序 – Anne

+0

@安妮 - 是的,更新的答案。 –

0
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); 
    } 
}