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);
        }
    }
}

标签： javatreebinary-search-tree

Answer 1

Long story short, searchNodeIteratively's logic looks fine, but insert is broken because it builds an invalid tree and the classes would benefit from a re-write. Read on for details.

---

These classes flaunt core OOP principles with the most blatant violation being re-use. If all of the logic in the BinaryTree class is hard coded to rely on name and num properties of the Node class, then it's useless for any purpose than storing these exact two fields and we have to re-write the entire class any time our data changes. Using generics, we can allow a BinaryTree or Node to work with arbitrary types without re-writing any code.

The class organization is unusual--BinaryTree enforces uniqueness, so it's really a BinarySearchTree class and should be named accordingly. insert should return a boolean (whether the insertion succeeded or not) and methods should not be static. new BinaryTree in main was commented out, but this is the right idea (we want to instantiate a BST). Hiding Node inside of BinaryTree is also good (it's an implementation detail of a BST), but it should be private.

Other remarks:

• Use .equals() instead of == to compare objects, as in name == (Q.name); == compares memory locations (this may have been your intent here, but then I'd question whether it's the correct logic for what we'd consider unique).
• Q, P Rlink don't explain much about what they are and don't adhere to Java variable naming conventions (use lowerCamelCase). Avoid single-letter variable names unless the meaning is obvious. String num is unclear--String phoneNumber makes more sense. Instead of writing comments to explain unclear variable names like Node P = null; // Parent of key to be inserted, provide a meaningful name like Node parent = null; and solve the problem directly.
• Return a value or throw an error instead of printing error messages. Prints are side effects that can't be programmatically handled.
• Ltag and Rtag appear to be redundant information and make the insertion logic very confusing. Just check whether the left and right Node objects are null to test their existence. This reduces bloat and avoids scenarios where the boolean values get out of sync with the Node values.

• The insertion logic:

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

  appears to build an invalid tree. This sets the new node (tmp)'s left link to point to the parent node's old left link and points the new node's right link to the parent, breaking the definition of a tree, which is a graph with one root and no cycles.

• searchNodeIterativly should be called searchNode or contains. How it accomplishes this (iteratively) should be inconsequential from the perspective of the client of this class (this might be an appropriate name for a private method).
• We can see that insert offers no balancing of the tree, so this essentially cripples contains and insert method complexity to O(n). Adding balancing to the tree would be a good next addition, bringing operations to the desired O(n log(n)).

Here's an initial re-write that implements generics and reusability in the BinarySearchTree class. We can invoke contains with a lambda function to dynamically search (or we can use an instance of T if that makes more sense). These classes only partially implement the class contract--I'd expect equals and hashCode to be implemented for starters.

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"))
        );
    }
}

Output:

    Robson
        Ortiz
Ikerd
        Harris
    Gladwin
        Dang
            Bird

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