How to implement a binary tree structure with objects?

Question

How can I implement a "binary tree structure"?

The result should be:

If the field contains "true" both lists should add this element. If the field contains "false" only the right list should add this element. I think without a recursive function this method is not implementable.

public class Test {

    static List<String> fields = new ArrayList<>();
    static List<Fieldmatrix> list = new ArrayList<>();

    public static void main(String[] args) {

        fields.add("1 : true");
        fields.add("2 : false");
        fields.add("3 : false");    

        permute(new ArrayList<>(),new ArrayList<>(), 0 , fields); 
    }
}

Method:

public static List<List<String>> permute(List<String> fieldsRight, List<String> fieldsLeft, int start, List<String> fields){

    List<List<String>> combinations = new ArrayList<>();

    if (start >= fields.size()) {
        combinations.add(fieldsRight);
        combinations.add(fieldsLeft);
        return combinations;
    }
    List<String> tmpRight = new ArrayList<>();
    List<String> tmpLeft = new ArrayList<>();

    if (fields.get(start).contains("false")){


        fieldsRight.add(fields.get(start));
        tmpRight = new ArrayList<>(fieldsRight);
        tmpLeft = new ArrayList<>(fieldsLeft);

        combinations.addAll(permute(fieldsRight, fieldsLeft, start+1, fields));


    }
    else{

        fieldsRight.add(fields.get(start));
        fieldsLeft.add(fields.get(start));
        tmpRight = new ArrayList<>(fieldsRight);
        tmpLeft = new ArrayList<>(fieldsLeft);

        combinations.addAll(permute(fieldsRight, fieldsLeft, start+1, fields));
    }

    return combinations;
}

Where is my mistake? How can I solve this problem?

The classic way to implement a binary try is with a class that represents a node has some data fields, and a left and a right pointer (of that same class). — Maurice Perry
– Maurice Perry, Commented May 12, 2017 at 6:28

Maurice Perry · Accepted Answer · 2017-06-19 12:51:39Z

1

The way I understand your diagram, each node would have a data field that is a list of boolean, and a left and a right reference to some other node:

class Node {
    Map<Integer,Boolean> data;
    Node left;
    Node right;
};

UPDATE

public class Tree {
    private List<Boolean> list;
    private Node left;
    private Node right;

    private static class Node {
        List<Integer> list;
        private Node left;
        private Node right;

        Node(List<Boolean> treeList, List<Integer> list, int start) {
            this.list = list;
            if (start < treeList.size()) {
                List<Integer> leftList = new ArrayList<>(list);
                List<Integer> rightList = new ArrayList<>(list);
                rightList.add(start+1);
                if (treeList.get(start)) {
                    leftList.add(start+1);
                }
                left = new Node(treeList, leftList, start+1);
                right = new Node(treeList, rightList, start+1);
            }
        }

        void print(int indent) {
            for (int i = 0; i < indent; ++i) {
                System.out.print("    ");
            }
            System.out.println(list);
            if (left != null) {
                left.print(indent+1);
            }
            if (right != null) {
                right.print(indent+1);
            }
        }
    }

    public Tree(List<Boolean> list) {
        this.list = new ArrayList<>(list);
        if (!list.isEmpty()) {
            List<Integer> leftList = new ArrayList<>();
            List<Integer> rightList = new ArrayList<>();
            rightList.add(1);
            if (list.get(0)) {
                leftList.add(1);
            }
            left = new Node(list, leftList, 1);
            right = new Node(list, rightList, 1);
        }
    }

    public void print() {
        System.out.println(list);
        if (left != null) {
            left.print(1);
        }
        if (right != null) {
            right.print(1);
        }
    }
}

To build the tree:

    Tree tree = new Tree(Arrays.asList(true, false, false));
    tree.print();

UPDATE 2: Output

[true, false, false]
    [1]
        [1]
            [1]
            [1, 3]
        [1, 2]
            [1, 2]
            [1, 2, 3]
    [1]
        [1]
            [1]
            [1, 3]
        [1, 2]
            [1, 2]
            [1, 2, 3]

edited Jun 19, 2017 at 12:51

answered May 12, 2017 at 6:33

Maurice Perry

9,6782 gold badges15 silver badges28 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

mrfsl Over a year ago

How did you come to List<Boolean> ?

Maurice Perry Over a year ago

@mrfsl you're right: it's not a List<Boolean>, rather a Map<Integer,Boolean>.

mrfsl Over a year ago

And how can I make the references to the lists recursively?

Maurice Perry Over a year ago

You build the tree

Maurice Perry Over a year ago

@mrfsl like this

Collectives™ on Stack Overflow

How to implement a binary tree structure with objects?

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related