时间戳

首页 > 解决方案 > Java中的二分查找和中序遍历

java - Java中的二分查找和中序遍历

问题描述

我正在研究二叉搜索树。我使用 inOrder 类型的遍历方法，但在 main 方法中出现错误。问题是为什么？我想念什么？谢谢

inOrder(S11.Tree<java.lang.Integer>.Node<java.lang.Integer>) in Tree 不能应用于(S11.Node<java.lang.Integer>)

public class Tree<T extends Comparable<T>> {
    private Node<T> root;


    public void add(T data) {
        root = doInsert(root, data);
    }

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

    public void inOrder(Node<T> root) {
        if (root != null) {
            inOrder(root.left);
            System.out.print(root.data + " ");
            inOrder(root.right);
        }
    }

    class Node<T> {
        Node<T> left;
        Node<T> right;
        T data;

        public Node(T data) {
            this.data = data;

        }
    }
}

  public static void main(String[] args) {
        Tree<Integer> tree = new Tree<Integer>();
        Node<Integer> root1 = new Node<>(8);
        tree.add(3);
        tree.add(10);
        tree.add(1);
        tree.add(6);
        tree.add(14);
        tree.add(4);
        tree.add(7);
        tree.add(13);
        tree.add(18);

        tree.inOrder(**root1)**;//here I get an error
    }
}

标签： java

解决方案

您在这里遇到设计问题以及add(T data)方法的错误实现。

public final class Tree<T extends Comparable<T>> {

    private Node<T> root;
    private int size;

    public void add(T val) {
        Node<T> node = new Node<>(val);

        if (root == null)
            root = node;
        else
            add(root, node);

        size++;
    }

    private void add(Node<T> parent, Node<T> node) {
        if (node.val.compareTo(parent.val) < 0) {
            if (parent.left == null)
                parent.left = node;
            else
                add(parent.left, node);
        } else if (parent.right == null)
            parent.right = node;
        else
            add(parent.right, node);
    }

    public List<T> inOrder() {
        return size == 0 ? Collections.emptyList() : Collections.unmodifiableList(inOrder(root, new ArrayList<>(size)));
    }

    private static <T> List<T> inOrder(Node<T> node, List<T> res) {
        while (true) {
            if (node == null)
                return res;

            inOrder(node.left, res);
            res.add(node.val);
            node = node.right;
        }
    }
   
    // This is an internal implementation of Tree and should be hidden
    // Node should not be linked with Tree instance
    private static final class Node<T> {

        private final T val;
        private Node<T> left;
        private Node<T> right;

        public Node(T val) {
            this.val = val;
        }
    }
}

输出：

Tree<Integer> tree = new Tree<>();
tree.add(8);
tree.add(3);
tree.add(10);
tree.add(1);
tree.add(6);
tree.add(14);
tree.add(4);
tree.add(7);
tree.add(13);
tree.add(18);

System.out.println(tree.inOrder()); // [1, 3, 4, 6, 7, 8, 10, 13, 14, 18]

推荐阅读