1

我一直在尝试让这个图伪装成二叉树工作。目前我正在使用一个函数，它传入根节点和我正在寻找的节点的 ID。唯一的问题是，根据我的编码方式，我的一方永远无法超过 3 个节点。我确定我只是没有正确地进行递归。我整晚都被困在这个问题上，无法得到这个。我试过查看其他图表和树，但无济于事。我们没有使用实际的顶点或其他类似属性的图，但我不能只使用if (x <root.getID())root.left，因为它仍然是一个“图”，所以这不成立

这是我的非工作搜索算法，如果我让它长几个节点，它就会在右侧停止工作。Visited 正在使用 HashSet() 类。

private Node dfs(Node x, int id)
{
    if (x==null) //base case. Runs into null link
       return null;
    if(visited.contains(x.getID())) //visited before
       return null;
    visited.add(x.getID()); //don't go below Node again
    if(id==x.getID())
      return x;
    Node rc = dfs(x.getRightChild(), id);
    Node lc = dfs(x.getLeftChild(), id);
    //recursive calls

  if (lc.getID()==id)
      return lc;
  if(rc.getID()==id)
      return rc;
  return null;
}

我有一个打印所有树的工作代码，但我无法更改上面代码中的键比较。

private String dfsPrint(Node x) //pass in root at top level
                                //returns a String containing all ID's
{
   if (x==null) //base case. Runs into null link
       return "";
   if(visited.contains(x.getID())) //visited before
       return "";
   visited.add(x.getID()); //don't go below Node again
   String lc = dfsPrint(x.getLeftChild()); //recursive stuffs
   String rc = dfsPrint(x.getRightChild());
   return Integer.toString(x.getID()) + " " + lc + rc;
}

感谢您的任何帮助。

编辑：我想我会扩展我正在做的事情。我必须有一个函数 makeRight 或 makeLeft 放入一个新节点，然后一个现有节点放入它有它的左或右子节点。就是这样。在其中搜索是调用私有 dfs 的公共方法。

  Node search(int id) // calls private dfsSearch() returns null or a ref to 
                    // a node with ID = id
{
  int ID = id;
  Node x= dfs(root, ID);
  return x;
}


void ML(int x, int y) // ML command
{
visited.clear();
Node temp = new Node(y, null, null);
Node current = search(x);
current.putLeft(temp);

}

void MR(int x, int y)//MR command
{
visited.clear();
Node temp = new Node(y, null, null);
Node current = search(x);
current.putRight(temp);

}

根据我对 lc 和 rc 的 if 语句的递归函数的排序方式，树的另一侧会递归回基本情况，这就是让我假设 dfs 方法有问题的原因。这是请求的节点类。

 class Node {
 private int ID; //ID of the Node. Distinct
 private Node leftChild;
 private Node rightChild;

 Node(int identification)//constructor

{
     ID = identification;
}
 Node(int identification, Node lt, Node rt) //constructor

{
 ID = identification;
 leftChild = lt;
 rightChild = rt;

}

int getID()

{
    return ID;
}

Node getLeftChild()
    {
           return leftChild;
    }
Node getRightChild()
{
    return rightChild;
}
void putLeft(Node lt)
{
    leftChild = lt;
}
void putRight (Node rt)
{
    rightChild = rt;
}

}

4

2 回答 2

1

你可以简化代码。我不认为你需要'id'。这个怎么样？

private dfs(Node x, int id) {
    if (x==null) { //base case. Runs into null link
       return;
    }
    if(visited.contains(x)) { //visited before
       return;
    }
    visited.add(x); //don't go below Node again
    dfs(x.getRightChild());
    dfs(x.getLeftChild());
}
于 2011-03-04T15:31:12.107 回答
0

您的dfs方法在几种情况下返回 null。当您尝试调用getId()这样的返回值时，您应该得到一个异常。不是吗？

于 2011-03-04T15:07:34.830 回答