Интервальный поиск в бинарном дереве

Question

Может кто-нибудь помочь мне с поиском интервалов в двоичном дереве. Я понимаю, как проверить левую сторону дерева, но у меня проблемы с надрезом правой части дерева. Сейчас это мой код.

private boolean search(BSTNode r, int from,int till){

             boolean found = false;
             int arr[];
             arr=new int[10];
             int i=0;
             while (r != null)

             {
                int rval = r.getData();
                if (from < rval && till >rval) {
                     r = r.getLeft();
                     arr[i]=rval;
                     i++;
                }else 
                    r=r.getRight(); 
             }
             return found;
         } 

Это полный класс BSTNode. От и до это интервал интервалов (от

     class BSTNode
     {
         BSTNode left, right;
         int data;
         /* Constructor */
         public BSTNode()
         {
             left = null;

             right = null;

             data = 0;
         }
         /* Constructor */
         public BSTNode(int n)
         {
             left = null;

             right = null;

             data = n;
         }
         /* Function to set left node */
         public void setLeft(BSTNode n)
         {
             left = n;
         }
         /* Function to set right node */ 
         public void setRight(BSTNode n)
         {
             right = n;
         }
         /* Function to get left node */

         public BSTNode getLeft()
         {
             return left;
         }
         /* Function to get right node */

         public BSTNode getRight()
         {
             return right;
         }

Answer 1

Вы можете искать, используя queue, например:

        public boolean search(Integer from, Integer till) {
            return search(root, from, till);
        }

        private boolean search(BSTNode root, Integer from, Integer till) {
            boolean found = false;
            Queue<BSTNode> queue = new ArrayDeque<>();
            queue.add(root);
            List<Integer> list = new ArrayList<>();
            while (!queue.isEmpty()) {
                BSTNode node = queue.poll();
                int data = node.getData();
                if (from < data && till > data) {
                    found = true;
                    list.add(data);
                }
                if (node.getLeft() != null)
                    queue.add(node.getLeft());
                if (node.getRight() != null)
                    queue.add(node.getRight());
            }
            System.out.println(list);
            return found;
        }

, полный код

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();

        // Tree building...
        tree.insert(50);
        tree.insert(40);
        tree.insert(20);
        tree.insert(10);
        tree.insert(50);

        System.out.println(tree.search(10, 30));
    }

    static class BinarySearchTree {

        private BSTNode root;

        public void insert(Integer item) {
            root = insert(root, item);
        }

        private BSTNode insert(BSTNode node, Integer item) {
            if (node == null) {
                return new BSTNode(item);
            } else if (item.compareTo(node.data) == 0) {
                return node;
            } else if (item.compareTo(node.data) < 0) {
                node.setRight(insert(node.r, item));
                return node;
            } else {
                node.setLeft(insert(node.l, item));
                return node;
            }
        }

        public Integer find(Integer target) {
            return find(root, target);
        }

        private Integer find(BSTNode node, Integer target) {
            if (node == null) {
                return null;
            }
            Integer cmd = target.compareTo(node.data);
            if (cmd == 0) {
                return node.data;
            } else if (cmd < 0) {
                return find(node.getRight(), target);
            } else {
                return find(node.getLeft(), target);
            }
        }

        public boolean search(Integer from, Integer till) {
            return search(root, from, till);
        }

        private boolean search(BSTNode root, Integer from, Integer till) {
            boolean found = false;
            Queue<BSTNode> queue = new ArrayDeque<>();
            queue.add(root);
            List<Integer> list = new ArrayList<>();
            while (!queue.isEmpty()) {
                BSTNode node = queue.poll();
                int data = node.getData();
                if (from < data && till > data) {
                    found = true;
                    list.add(data);
                }
                if (node.getLeft() != null)
                    queue.add(node.getLeft());
                if (node.getRight() != null)
                    queue.add(node.getRight());
            }
            System.out.println(list);
            return found;
        }
    }

    static class BSTNode {
        Integer data;
        BSTNode l = null;
        BSTNode r = null;

        public BSTNode(Integer data) {
            super();
            this.data = data;
        }

        public Integer getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }

        public BSTNode getLeft() {
            return l;
        }

        public void setLeft(BSTNode l) {
            this.l = l;
        }

        public BSTNode getRight() {
            return r;
        }

        public void setRight(BSTNode r) {
            this.r = r;
        }

        @Override
        public String toString() {
            return "BSTNode [data=" + data + ", l=" + l + ", r=" + r + "]";
        }
    }

, вывод

[20]
true