二叉树搜索非键值

Question

我目前正在寻找一种递归算法来在我的树中找到一个非键值。

我有我的节点Class:

public class TreeNode {
    private Person person;
    private TreeNode left, right;

    public TreeNode(Person person) {
        this.person = person;
    }

    public boolean insert(Person person) {
        if (person.getAge() < this.person.getAge()){
            if (left != null){
                return left.insert(person);
            }else {
                left = new TreeNode(person);
            }
        }else{
            if (right != null){
                return right.insert(person);
            }else{
                right = new TreeNode(person);
            }
        }
        return true;
    }

    public boolean countryExists(String country){
        if (!this.person.getCountry().equals(country)){
            if (right != null) {
                return right.countryExists(country);
            }
            if (left != null) {
                return left.countryExists(country);
            }
        }else {
            return true;
        }
    }
}

这里的Key值是一个人的年龄。我想知道是否有来自特定国家/地区的人。因此我创建了函数 countryExists(String country) 我不知道如何实现它，我到处搜索并观看了很多关于 post/pre/inorder 的视频。顺序应该没有问题吧？我认为返回正确的布尔值有问题...

感谢您的帮助。

Answer 1

在你的 countryExists 方法中你应该 return false 在两次 != null 检查之后，因为如果执行到了这个点就意味着你的节点没有左右兄弟姐妹（这是一片叶子）和它的人的国家不等于你要找的那个。

但我建议做一些重构，而不是否定 this.person.getCountry().equals(country)，只需在方法的开头使用它和 return true。

public boolean countryExists(String country) {
    if (this.person.getCountry().equals(country)) {
        return true;
    }

    if (right != null) {
        return right.countryExists(country);
    }
    if (left != null) {
        return left.countryExists(country);
    }

    return false;
}

此外，这是 O(n) 解决方案，因为您没有使用键来切断整个分支，而是进行完整的树遍历。

要做到O(log n)（在树平衡的情况下），需要使用country作为key，搜索时只选择一个分支。

二叉树搜索非键值

Binary Tree Search for non key value

java

tree

binary-search-tree