0

我试图递归地显示到二叉树中给定节点的路径，该方法将以下列方式输出所需的路径：“左、右、左”。这是我到目前为止所拥有的：

public static void pathToNode(BTNode p, char target, String res){
    if(p.data == target){
        res = res + p.data;
        System.out.println(res);
        return;
    }else if(res != null){
        if(res.charAt(0) == 'S'){
        res = res + p.data;
        }
    }else{
        pathToNode(p.leftLink, target, res);
        pathToNode(p.leftLink, target, res);
    }

}

此代码旨在像这样打印出路径：“ABCD”。完成此操作后，我打算根据每个节点遍历的正确选项使该方法从左到右打印出来。有任何想法吗？

4

3 回答 3

1

你的代码对我来说有点不清楚。'S' 应该是根有效载荷吗？此外，您真的应该尝试使用更有说服力的变量名称。

public static String pathToNode(BTNode p, char target) {
    // termination rules
    if (p.data == target) {
       // success
       return p.data;       
    }
    // failure: p is not the target AND is a leaf.
    if (p.leftLink == null && p.rightLink == null) return null;

    // recursion: if p is in the subtree, this will find it.
    return (pathToNode(p.leftLink, target) == null) ? (p.data + pathToNode(p.rightLink), target) : (p.data + pathToNode(p.leftLink, target));

}

编辑：null如果目标不在树中，这当然可能会返回。另外，我忘了实际打印路径。现在在里面。

于 2012-11-16T10:23:21.220 回答
0

我认为您正在尝试从根目录中找到路径。另外我假设这棵树只有一条到达目标的路径。我的意思是同一个元素不能在树的不同位置。

此代码将起作用，

public static void pathToNode(BTNode p, char target, String res){
    if(p.data == target){
        res += p.data;
        System.out.println(res);
        return;
    }
    else{
        if(res==null){
           res="";
        }
        res += p.data;
        pathToNode(p.leftLink, target, res);
        pathToNode(p.rightLink, target, res);
    }
}

但这将是非常低效且容易消耗内存的解决方案。请阅读有关树遍历的更多信息以获得一个好的解决方案。

于 2012-11-16T10:17:49.143 回答
0

当您在第一个 if 子句中找到您正在寻找的目标时，您正在打印结果。或者，您应该同时尝试树的左分支和右分支，就像您（几乎，您正在做左两个）在最后一个子句中所做的那样。

我不确定第二个子句应该做什么，但删除它并在递归调用中添加p.data应该res确保“当前”步骤保存在res变量中：

if (p.data == target) {
    res = res + p.data;
    System.out.println(res);
} else {
    pathToNode(p.leftLink, target, res + p.data);
    pathToNode(p.rightLink, target, res + p.data);
}

这样，您将使用递归算法常见的传统基本案例 + 递归案例。

于 2012-11-16T10:17:59.617 回答