Рекурсия бинарного дерева поиска - нужно ли использовать setLeft и правильно? - PullRequest
Новая
       36

Рекурсия бинарного дерева поиска - нужно ли использовать setLeft и правильно?

1 голос
/ 29 апреля 2020 
public class BSTNode {

    Profile data = null;
    BSTNode l = null;
    BSTNode r = null;

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

    public Profile getData() {  //not sure
        return data;
    }

    public void setData(Profile data) { //not sure
        this.data = data;
    }

    public Profile getProfile() {
        return data;

    }

    public BSTNode getL() {
        return l;
    }

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

    public BSTNode getR() {
        return r;
    }

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

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


public class BST {

    BSTNode root = null;

    public BST() {

    }   
    public void insertProfile(Profile p) {
        BSTNode node = new BSTNode(p);

        if (root == null) {
            root = node;
            return;
        }
    }
}

Все, что я сделал до сих пор. Мне нужно вызвать частный рекурсивный метод, если root не равно нулю. В этом новом методе он должен рекурсивно вызывать getL или getR из BSTNode.

Ответы [ 2 ]

2 голосов
/ 29 апреля 2020

Можно попробовать вставить вот так: 

Node root;

class Node {
    Item data;
    Node left;
    Node right;

    public Node(Item e) {
        data = e;
    }
}

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

private Node insert(Node node, Item item) {
    if (node== null) {
        return new Node(item);
    } else if (item.compareTo(node.data) == 0) {
        return node;
    } else if (item.compareTo(node.data) < 0) {
        node.right = insert(node.right, item);
        return node;
    } else {
        node.left = insert(node.left, item);
        return node;
    }
}

, обновленная версия 

public class BST {

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

        // Tree building...
        tree.insert(new Profile("50"));
        tree.insert(new Profile("70"));
        tree.insert(new Profile("80"));
        tree.insert(new Profile("60"));
        tree.insert(new Profile("30"));
        tree.insert(new Profile("40"));
        tree.insert(new Profile("20"));

        System.out.println("\nSearch the node with data 60: " + tree.find(new Profile("60")));
        System.out.println("Search the node with data 65: " + tree.find(new Profile("65")));
        System.out.println("Search the node with data 20: " + tree.find(new Profile("20")));
        System.out.println("Search the node with data 25: " + tree.find(new Profile("25")));
    }

    static class BinarySearchTree {

        private BSTNode root;

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

        private BSTNode insert(BSTNode node, Profile item) {
           if (node == null) {
                return new BSTNode(item);
            } else if (item.id.compareTo(node.data.id) == 0) {
                return node;
            } else if (item.id.compareTo(node.data.id) < 0) {
                node.setR(insert(node.r, item));
                return node;
            } else {
                node.setL(insert(node.l, item));
                return node;
            }
        }

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

        private Profile find(BSTNode node, Profile target) {
            if (node == null) {
                return null;
            }
            int cmd = target.id.compareTo(node.data.id);
            if (cmd == 0) {
                return node.data;
            } else if (cmd < 0) {
                return find(node.getR(), target);
            } else {
                return find(node.getL(), target);
            }
        }

    }

    static class Profile {
        String id;

        public Profile(String id) {
            this.id = id;
        }

        @Override
        public int hashCode() {
            return id.hashCode();
        }

        @Override
        public boolean equals(Object obj) {
            return this.id.equals(((Profile) obj).id);
        }

        @Override
        public String toString() {
            return id;
        }
    }

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

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

        public Profile getData() { // not sure
            return data;
        }

        public void setData(Profile data) { // not sure
            this.data = data;
        }

        public Profile getProfile() {
            return data;

        }

        public BSTNode getL() {
            return l;
        }

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

        public BSTNode getR() {
            return r;
        }

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

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

, вывод 

Search the node with data 60: 60
Search the node with data 65: null
Search the node with data 20: 20
Search the node with data 25: null
0 голосов
/ 29 апреля 2020 
class Node {
  Node left;
  Node right;
  Object data;

  public void insert(Object data) {
    // decide whether it goes to the left or to the right. 
    // assume the left:
    if (left != null) {
      left.insert(data);
    } else {
      left = new Node(data);
    }
  }
}
...