java - 二叉树的搜索功能未返回找到的节点

Question

这就是我要插入到树中的内容:

我正在寻找:Node nd = searchNodeIterativly(root, "Ortiz");
我得到一个空指针错误。

由于"Ortiz"实际上在树中，我不明白为什么我在循环中的返回不起作用。

是算法，还是我忽略的东西？

这是我的代码:

import java.io.IOException;
import java.util.*;

public class BinaryTree {
    public static class Node {
        String name, number;
        Node Llink, Rlink;
        boolean Ltag, Rtag;

        Node(String name, String number) {
            this.name = name;
            this.number = number;
            Llink = null;
            Rlink = null;
        }
    }

    public static Node insert(Node node, String name, String num) {
        // Searching for a Node with given value
        Node Q = node;
        Node P = null; // Parent of key to be inserted
        while (Q != null) {
            // If key already exists, return
            if (name == (Q.name)) {
                System.out.printf("Duplicate Key !\n");
                return node;
            }
            P = Q;
            if (name.compareTo(Q.name) < 0) {
                if (Q.Ltag == false)
                    Q = Q.Llink;
                else
                    break;
            } else {
                if (Q.Rtag == false)
                    Q = Q.Rlink;
                else
                    break;
            }
        }
        Node tmp = new Node(name, num);
        tmp.name = name;
        tmp.Ltag = true;
        tmp.Rtag = true;

        if (P == null) {
            node = tmp;
            tmp.Llink = null;
            tmp.Rlink = null;
        } else if (name.compareTo(P.name) < 0) {
            tmp.Llink = P.Llink;
            tmp.Rlink = P;
            P.Ltag = false;
            P.Llink = tmp;
        } else {
            tmp.Llink = P;
            tmp.Rlink = P.Rlink;
            P.Rtag = false;
            P.Rlink = tmp;
        }

        return node;
    }

    public static Node searchNodeIterativly(Node node, String name) {
        while (node != null) {
            if (name.compareTo(node.name) > 0) {
                node = node.Llink;
            } else if (name.compareTo(node.name) < 0) {
                node = node.Rlink;
            } else {
                return node;
            }
        }
        return node;
    }

    public static void main(String[] args) throws IOException {
        // BinaryTree tree = new BinaryTree();
        Node root = new Node("Moutafis  ", "295-1492");
        insert(root, "Ikerd     ", "291-1864");
        insert(root, "Gladwin   ", "295-1601");
        insert(root, "Robson    ", "293-6122");
        insert(root, "Dang      ", "295-1882");
        insert(root, "Bird      ", "291-7890");
        insert(root, "Harris    ", "294-8075");
        insert(root, "Ortiz     ", "584-3622");

        Node nd = searchNodeIterativly(root, "Ortiz     ");
        if (nd == null) {
            System.out.println("no result found!");
        } else {
            System.out.println(nd.name + ": " + nd.number);
        }
    }
}

Answer 1

长话短说，searchNodeIteratively的逻辑看起来不错，但是 insert被破坏，因为它构建了一个无效的树，并且类将从重写中受益。请继续阅读以了解详细信息。

这些类标榜核心 OOP 原则，最明显的违规行为是 re-use .如果 BinaryTree 中的所有逻辑类(class)是 hard coded依靠name和 num Node 的属性类，那么除了存储这两个确切的字段之外，它对于任何目的都是无用的，并且我们必须在数据更改时重新编写整个类。使用 generics , 我们可以允许 BinaryTree或 Node无需重写任何代码即可使用任意类型。

类(class)组织异常——BinaryTree强制唯一性，所以它真的是 BinarySearchTree类，并应相应命名。 insert应该返回一个 boolean 值(无论插入是否成功)并且方法不应该是静态的。 new BinaryTree在 main被注释掉了，但这是正确的想法(我们要实例化一个 BST)。隐藏Node BinaryTree 内部也很好(它是 BST 的实现细节)，但它应该是私有(private)的。

其他备注:

使用.equals()而不是 ==比较对象，如 name == (Q.name) ; ==比较内存位置(这可能是您的意图，但我会质疑这是否是我们认为独特的正确逻辑)。

Q , P Rlink不要过多解释它们是什么，也不遵守 Java 变量命名约定(使用 lowerCamelCase)。除非含义很明显，否则避免使用单字母变量名称。 String num不清楚-- String phoneNumber更有意义。而不是写注释来解释不清楚的变量名称，如 Node P = null; // Parent of key to be inserted ，提供一个有意义的名称，如 Node parent = null;并直接解决问题。

返回一个值或抛出一个错误，而不是打印错误消息。打印是 side effects无法以编程方式处理。

Ltag和 Rtag似乎是冗余信息，使插入逻辑非常困惑。只需检查左右Node对象是 null来测试它们的存在。这减少了膨胀并避免了 boolean 值与 Node 不同步的情况。值(value)观。

插入逻辑:

tmp.Llink = P.Llink;
tmp.Rlink = P;

似乎建立了一棵无效的树。这将新节点 ( tmp ) 的左链接设置为指向父节点的旧左链接，并将新节点的右链接指向父节点，从而打破了树的定义，即有一个根且没 Root过的图循环。

searchNodeIterativly应该叫 searchNode或 contains .从这个类的客户的角度来看，它如何(迭代地)完成这一点应该是无关紧要的(这可能是私有(private)方法的适当名称)。

我们可以看到 insert不提供树的平衡，所以这基本上会削弱 contains和 insert方法复杂度为 O(n)。为树添加平衡将是一个很好的下一个添加，将操作带到所需的 O(n log(n))。

这是在 BinarySearchTree 中实现泛型和可重用性的初始重写。类(class)。我们可以调用 contains使用 lambda 函数进行动态搜索(或者我们可以使用 T 的实例，如果这样更有意义的话)。这些类只部分实现了类契约——我希望 equals和 hashCode为初学者实现。

import java.util.*;

class BinarySearchTree<T extends Comparable<T>> {
    public interface Comparator<T> {
        int compare(T t);
    }

    private static class Node<T extends Comparable<T>> 
              implements Comparable<Node<T>> {
        private T data;
        private Node left;
        private Node right;

        Node(T data, Node left, Node right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }

        @Override
        public int compareTo(Node<T> node) {
            return this.data.compareTo(node.data);
        }
    }

    private Node<T> root;

    public BinarySearchTree() {
        this.root = null;
    }

    public boolean insert(T item) {
        Node<T> prev = null;

        for (var curr = root; curr != null;) {
            prev = curr;

            if (curr.data.compareTo(item) == 0) {
                return false;
            }

            curr = curr.data.compareTo(item) < 0 ? 
                curr.left : curr.right;
        }

        if (prev == null) {
            root = new Node<T>(item, null, null);
        }
        else if (prev.data.compareTo(item) < 0) {
            prev.left = new Node<T>(item, null, null);
        }
        else {
            prev.right = new Node<T>(item, null, null);
        }

        return true;
    }

    public boolean contains(Comparator<T> cmp) {
        for (var curr = root; curr != null;) {
            if (cmp.compare(curr.data) == 0) {
                return true;
            }

            curr = cmp.compare(curr.data) < 0 ? 
                curr.left : curr.right;
        }

        return false;
    }

    public boolean contains(T item) {
        for (var curr = root; curr != null;) {
            if (curr.data.compareTo(item) == 0) {
                return true;
            }

            curr = curr.data.compareTo(item) < 0 ? 
                curr.left : curr.right;
        }

        return false;
    }

    private static void print(Node node, int depth) {
        if (node != null) {
            print(node.left, depth + 4);

            for (int i = 0; i < depth; i++) {
                System.out.print(" ");
            }

            System.out.println(node.data);
            print(node.right, depth + 4);
        }
    }

    public void print() {
        print(root, 0);
    }
}

class Person implements Comparable<Person> {
    private String name;
    private String phone;

    public Person(String name, String phone) {
        this.name = name;
        this.phone = phone;
    }

    public String getName() { return name; }
    public String getPhone() { return phone; }
    public String toString() { return name; }

    public int compareTo(Person person) {
        return name.compareTo(person.name);
    }
}

class Main {
    public static void main(String[] args) {
        String[][] data = {
            {"Ikerd", "291-1864"},
            {"Gladwin", "295-1601"},
            {"Robson", "293-6122"},
            {"Dang", "295-1882"},
            {"Bird", "291-7890"},
            {"Harris", "294-8075"},
            {"Ortiz", "584-3622"},
            {"Ortiz", "584-3622"}
        };

        var people = new BinarySearchTree<Person>();

        for (var entry : data) {
            people.insert(new Person(entry[0], entry[1]));
        }

        people.print();
        System.out.println(
            "\nContains \"Bird\"? " + people.contains((p) -> p.getName().compareTo("Bird"))
        );
        System.out.println(
            "Contains \"Birds\"? " + people.contains((p) -> 
                p.getName().compareTo("Birds"))
        );
    }
}

输出:

    Robson
        Ortiz
Ikerd
        Harris
    Gladwin
        Dang
            Bird

Contains "Bird"? true
Contains "Birds"? false