T1AlgoEstDadosII/Arvore.java at main · refrantz/T1AlgoEstDadosII · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
import java.util.ArrayList;

public class Arvore {
    private static final class Node {

        public String content;
        public Node left;
        public Node right;

        public Node(String content){
            this.left = null;
            this.right = null;
            this.content = content;
        }

    }

    private int index = 1;
    private Node root;
    private int count;
    private ArrayList<Node> nodos = new ArrayList<Node>();

    public Arvore(){
        root = null;
        this.count = 0;
    }

    public void setRoot(Node root){
        this.root = root;
    }

    public void add(String s, String s2, String s3){
        Node n;
        Node n2 = new Node(s2);
        Node n3 = new Node(s3);
        if(size() == 0){
            n = new Node(s);
            nodos.add(n);
            setRoot(n);
            count++;
        }else{
            n = nodos.get(index);
            index++;
        }
        n.left = n2;
        n.right = n3;
        nodos.add(n2);
        nodos.add(n3);
        count += 2;
    }

    /*
    public Node getNode(String content) {
        return getNode(root, content);
    }

    public Node getNode(Node node, String content) {

        if (node == null || node.content.equals(content)) {
            return node;
        }

        Node n = getNode(node.left ,content);
        if(n != null){
            return n;
        }else{
            return getNode(node.right, content);
        }

      }
    */

    public int size(){
        return this.count;
    }

    @Override
    public String toString(){
        StringBuilder nodosString = new StringBuilder();
        nodosString.append("Numero de computadores: " + size() + " | numero de computadores em equilibrio: " + totalBalanced() + "\n");
        /*
        for(Node n : nodos){
            if(n.left != null){
                nodosString.append("Computador: " + n.content + " | filho esquerda: " + n.left.content + " | esforco filho esquerda: " + getSum(n.left) + " | filho direita: " + n.right.content + " | esforco filho direita: " + getSum(n.right) + " | está balanceado? " + isBalanced(n) + "\n");
            }else{
                nodosString.append("Computador: " + n.content + " | filho esquerda: " + "vazio" + " | esforco filho esquerda: " + "0" + " | filho direita: " + "vazio" + " | esforco filho direita: " + "0" + "\n");
            }
        }
        */
        return nodosString.toString();
    }

    public int getSum(Node n){
        if(n.left == null || n.right == null){
            return Integer.parseInt(n.content);
        }
        int soma = getSum(n.left) + getSum(n.right);
        return soma;
    }

    public boolean isBalanced(Node n){
        if(n.left != null){
            return getSum(n.left) == getSum(n.right);
        }else{
            return false;
        }

    }

    public int totalBalanced(){
        int total = 0;
        for(Node n : nodos){
            if(isBalanced(n)){
                total++;
            }
        }
        return total;
    }

    public int rootSum(){
        return getSum(root);
    }
}