在二叉树中，检查给定的节点是否是叶节点

Question

我已经编写了代码来查找给定节点是否为叶节点，对于正向情况，即输入节点是叶节点时，代码可以遍历到节点并输出结果停止执行，但负向情况下，当输入节点不是叶节点时，代码会继续遍历整个树，即使它已经通过该节点并确定它不是叶节点。

boolean isLeaf(BTNode node, int data) {
   if (node == null) {
    return false;
   }
System.out.println("Node traversed :"+ node.data);
if (node.left == null && node.right == null && node.data == data) {
    System.out.println("Node : " + node.data + " is leaf node");
    return true;
}
return (isLeaf(node.left, data) || isLeaf(node.right, data));
}

任何人能告诉我，如果找到节点并且它不是叶节点，停止递归的条件是什么。

谢谢。

- rohit garg

---

@Idos，你建议的代码中应该在哪里放置最终的返回语句？我在最后的大括号之前添加了return false;，这样整个函数都会返回false，即使找到了叶节点。使用当前的代码，它将无法编译，因为没有最终的返回语句。 - rohit garg

（已编辑以使其更易于理解并类似于您的代码） - Idos

@Idos，代码仍会抛出编译错误，因为它没有最终的返回语句。此外，在您当前的代码中，我们没有检查给定的节点，即使我们在isLeaf（BTNode node，int data）中添加节点值参数并在末尾返回false以及while返回true时的node.data == data条件，代码仍会遍历其他节点，即使它已经定位到叶节点。我通过所有这些更改运行了代码，但它并没有提供所需的答案。该代码适用于查找所有叶节点，但无法检查给定的节点是否为叶节点。 - rohit garg

我的第二个解决方案有效吗？ - Idos

@Idos，第二种解决方案是可行的，当我们不使用递归来遍历节点时。我应用了这个解决方案，通过搜索节点的解决方案来遍历树，当我到达那个节点时，我调用这个方法并将搜索到的节点传递给这个函数，如果函数返回true，则它是叶子节点。所以你的解决方案适用于单次检查。谢谢。 - rohit garg

Answer 1

可以尝试以下方法：

boolean isLeaf(BTNode node, int data) {
    if (node == null)       
        return false;
    if (node.left == null && node.right == null)      
        return true; 
    isLeaf(node.left); 
    isLeaf(node.right);      
}

你实现的主要问题在于这行代码：
。

return (isLeaf(node.left, data) || isLeaf(node.right, data));

你有没有想过实际执行时会发生什么？

Edit: If you just want to check if a node is a leaf do:

boolean isLeaf(BTNode node, int data) {
    if (node == null)
        return false;    
    if (node.right == null && node.left == null)
        return true;
    return false; 
}

- Idos

Answer 2

那是因为你的代码包含了没有明显原因的遍历。考虑一下这个递归调用的作用 - return (isLeaf(node.left, data) || isLeaf(node.right, data));。这很可能应该是return false。

- pvg

Answer 3

bool isleaf(Node* root)
    {
        if(root->left==NULL && root->right==NULL) return true;
        else return false;
    }

- Kunal Saha

---

当前您的回答写得不太清晰。请编辑以添加更多细节，以帮助其他人理解它是如何回答问题的。您可以在帮助中心中找到有关编写好回答的更多信息。 - Community

Answer 4

这是我使用纯C语言实现二叉搜索树的解决方案：

bool isLeaf(struct node *root, int data) {

    if (root == NULL)
        return false;

    if (root->data == data) {
        if (root->left == NULL && root->right == NULL)
            return true;
        else
            return false;
    }
    if (data > root->data)
        return isLeaf(root->right, data);
    else
        return isLeaf(root->left, data);
}

我认为你需要使用搜索/插入方法遍历树，利用BST的属性。

对于二叉树（而不是BST）：

bool isLeafBtree(struct node *root, int data) {
    if (root == NULL)
        return false;
    if (root->data == data) {
        if (root->left == NULL && root->right == NULL)
            return true;
        else
            return false;
    }
    if (isLeaf(root->left, data) == true)
        return true;
    else
        return isLeaf(root->right, data);
}

- Haswell