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

标签 java tree binary-search-tree

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

我正在寻找: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);
        }
    }
}

最佳答案

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

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

类(class)组织异常——BinaryTree强制唯一性,所以它真的是 BinarySearchTree类,并应相应命名。 insert应该返回一个 boolean 值(无论插入是否成功)并且方法不应该是静态的。 new BinaryTreemain被注释掉了,但这是正确的想法(我们要实例化一个 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无法以编程方式处理。
  • LtagRtag似乎是冗余信息,使插入逻辑非常困惑。只需检查左右Node对象是 null来测试它们的存在。这减少了膨胀并避免了 boolean 值与 Node 不同步的情况。值(value)观。
  • 插入逻辑:
    tmp.Llink = P.Llink;
    tmp.Rlink = P;
    

    似乎建立了一棵无效的树。这将新节点 ( tmp ) 的左链接设置为指向父节点的旧左链接,并将新节点的右链接指向父节点,从而打破了树的定义,即有一个根且没 Root过的图循环。
  • searchNodeIterativly应该叫 searchNodecontains .从这个类的客户的角度来看,它如何(迭代地)完成这一点应该是无关紧要的(这可能是私有(private)方法的适当名称)。
  • 我们可以看到 insert不提供树的平衡,所以这基本上会削弱 containsinsert方法复杂度为 O(n)。为树添加平衡将是一个很好的下一个添加,将操作带到所需的 O(n log(n))。

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

    关于java - 二叉树的搜索功能未返回找到的节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58827282/

    相关文章:

    java - Bukkit 交互式菜单 - 页面滚动

    algorithm - 如何在 Haskell 中标记树中的节点?

    linux - 在 bash 脚本中制作基本树结构的问题

    python - 以嵌套形式输出 BST

    javascript - 如何使用树数据结构提高复杂几何体的碰撞检测性能?

    java - java的stb_loadimage()和raster.getPixels()对于同一个文件的区别

    java - 如何将 SBT 管理的 scala 项目与 Maven 管理的 Java 项目合并?

    java - nginx 反向代理与 tomcat 不工作

    algorithm - 求和的RB树

    python - 连接到父循环的 BST