1

我正在为工作面试而学习并正在审查树木，遍历它们时我没有问题，但我遇到了一个我无法找到正确答案的问题：

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

到目前为止，我什至无法弄清楚为什么我会关心存储在树中的信息（孩子的数量）。除此之外，如果我们假设有一棵像这样的树：

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

我知道这会遍历树，但它仍然不能完全满足我的要求。任何帮助，将不胜感激。

4

4 回答 4

1

这个问题是模棱两可的。“中序”对于二叉树是有意义的，在这种情况下，“孩子的数量”总是两个，除非它们的意思是“后代的数量”，在这种情况下，您可以使用它来避免通过中序列表进行线性搜索（O* n) 因为在每个节点上，您可以根据后代的数量决定采用哪个分支 (O*log n)。

于 2012-02-01T20:34:50.493 回答
1

你可以这样做： 

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

注意：如果你不想要，你不需要使用额外的数据结构，但是因为你有一个 Stack，我就用它了。

注意 2：正如 Jim Garrison 指出的，如果您有后代计数，您可以优化算法。

于 2012-02-01T21:34:48.063 回答
0

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

于 2012-02-01T20:35:42.940 回答
0

最好通过使用树的属性来降低算法的复杂性，即每个节点都知道它拥有的子节点总数。因此，如果您知道当前节点左侧有多少个子节点，则可以计算当前节点的订单号（对于 root，它将是左侧的子节点数 + 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-27T20:06:28.600 回答