我已经尝试了一段时间让这个图表伪装成二叉树工作。目前我正在使用一个函数,该函数传入根节点和我正在查找的节点的 ID。唯一的问题是,根据我的编码方式,我的一侧永远无法超过 3 个节点长。我确信我只是没有正确执行递归。我已经被这个问题困住了一晚上了,没能明白。我尝试查看其他图表和树,但无济于事。我们没有使用实际的顶点或其他类似图形的属性,但我不能只使用 if (x <root.getID())
然后 root.left,因为这不成立,因为它仍然是一个“图”
这是我的非工作搜索算法,如果我将其设置为几个节点长,它就会在右侧停止工作。访问的是使用 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 来放入一个新节点,然后现有节点放入它的左子节点或右子节点。 就是这样。其中search是调用私有(private)dfs的公共(public)方法。
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;
}
}
最佳答案
你可以简化代码。我认为你不需要“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());
}
关于java - Java 中二叉树/图的深度优先搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5195365/