树的遍历在Java中

我面试的研究，并正检讨树木，我有穿越他们的时候没有问题，但我有一个问题我一直没能得到正确答案的身影到：树的遍历在Java中

编写一个函数，该函数返回给定两个参数的树中的节点：指向根节点的指针和我们要返回的节点的inorder遍历数。存储在树中的唯一信息是每个节点的子数。

到目前为止，我还没有能够确定为什么我会照顾存储在树中的信息（孩子的数量）。除此之外，如果我们假设有像这样的树：

 5 
    4  7 
3 1 4

那么序遍历将341547但我想不通的代码返回我想要的节点（便于讨论，我假设中序遍历数是2 - 意思是我想要值1的节点）。

我试着做一个递归遍历，但我最终拧了内部计数器我有，所以我尝试了不同的方法，只是试图把一切都放在堆栈上，但我不知道如何正确地做到这一点。到目前为止，我有：

public int findNode(root, position){ 
    Stack<Integer> s = new Stack<Integer>(); 
    cNode = root; //cNode = current Node 

    while(cNode.left != null) 
     cNode = cNode.left; 

    s.push(cNode); 

    while(cNode.right != null) 
    cNode = cNode.right; 

    //stuck here. 
}

的递归方法是比较容易，但我想不出如何检查，如果我有我要找的＃：

public int findNode(root, position){ 
    cNode = root; 
    if(cNode != null){ 
     findNode(cNode.left, position); 
     System.out.print(cNode.data); 
     findNode(cNode.right, position); 
    } 
}

我知道这遍历树但它仍然没有做到我想要的。任何帮助，将不胜感激。

来源

2012-02-01 Tsundoku

鉴于“存储在树中的唯一信息是每个节点的子节点数”，我猜你的示例树是错误的。另外，“inorder traversal number “究竟是？ – Gevorg 2012-02-01 20:29:30

“写一个函数，返回一个树中的***节点***给出两个参数”，***树中的一个节点***，哪个节点？在该特定索引处具有该特定值OR节点的节点（索引与在中间遍历中一样） – Bhushan 2012-02-01 20:33:32

你能做到这样：

public Node findNode(Node root, int position) { 
    ArrayList<Node> a = new ArrayList<Node>(); 
    populateNodes(root, a); 
    return a.get(position); 
} 

private void populateNodes(Node node, ArrayList<Node> a) { 
    if (node == null) return; 
    populateNodes(node.left, a); 
    a.add(node); 
    populateNodes(node.right, a); 
}

注意：您不需要使用额外的数据结构，如果你不想要的，但因为你有一个堆栈，我只是用它去。注2：正如Jim Garrison所指出的，如果你有后代数，你可以优化算法。

来源

2012-02-01 21:34:48

这是辉煌的我不知道我怎么想不到这一点，非常感谢。 – Tsundoku 2012-02-01 22:16:17

问题不明确。 “Inorder”对于二叉树是有意义的，在这种情况下，“孩子的数量”总是两个，除非他们的意思是“后裔的数量”，在这种情况下，您可以使用它来避免通过inorder列表进行线性搜索（O * n）因为在每个节点你可以根据子孙的数量来决定采取哪个分支（O * log n）。

来源

2012-02-01 20:34:50

我猜这棵树是错的，错过了一个孩子。既然这是我在书中的例子。 – Tsundoku 2012-02-01 20:36:30

你是什么意思“失踪的孩子”。二叉树不必完全填充。 – 2012-02-01 20:38:08

而不是传递位置，传递中序遍历数并在每个递归方法中追加到它。

来源

2012-02-01 20:35:42

通过使用树的属性来减少算法的复杂度会更好，每个节点都知道它拥有的子节点的总数。所以，如果你知道有多少孩子在左侧就可以计算出当前节点的顺序号下面的代码应该工作（根就没有左+ 1的孩子。）：

Nodeptr nthInInorder(Nodeptr root, int x){ 
Nodeptr curr = root; 
int countedIn = 0, leftchildren = 0, currIn=0; 

while(curr!=NULL){ 
    if(curr->left == NULL) 
    leftchildren = 0; 
    else 
    leftchildren = (curr->left)->data + 1; 

    currIn = countedIn + leftchildren + 1; 

    if(currIn == x) 
    return curr; 
    else if(currIn > x) 
    curr = curr->left; 
    else if(currIn < x) 
    { countedIn = currIn + 1; 
    curr = curr->right; 
    } 
    } 
    return NULL; 
}

这个算法的复杂性是O（log n）

来源

2013-01-27 20:06:28

树的遍历在Java中

回答

相关问题