View difference between Paste ID: 1w5hf4r9 and DECuYAzx
SHOW: | | - or go back to the newest paste.
1
//
2
// Created by Julio Tentor <jtentor@fi.unju.edu.ar>
3
//
4
5
6
public class BinaryTree<ELEMENT> {
7
8
9
    //region Binary Tree Node Class
10
11
    protected class BTNode<ELEMENT> {
12
13
        public ELEMENT item;
14-
        public BTNode<ELEMENT> left;
14+
        public BTNode<ELEMENT> left; //izquierdo
15-
        public BTNode<ELEMENT> right;
15+
        public BTNode<ELEMENT> right; // Derecho
16
17
        public BTNode() {
18
            this(null, null, null);
19
        }
20
        public BTNode(ELEMENT item) {
21
            this(item, null, null);
22
        }
23
        public BTNode(ELEMENT item, BTNode<ELEMENT> left, BTNode<ELEMENT> right) {
24
            this.item = item;
25
            this.left = left;
26
            this.right = right;
27
        }
28
29
        @Override
30
        public String toString() {
31
            return this.item.toString();
32
        }
33
34
        // Método para propósitos académicos
35
        public void Visit() {
36
            System.out.printf("%s ", this.item.toString());
37
        }
38
    }
39
    //endregion
40
41
42
43
44
    //region Attributes
45
46-
    protected BTNode<ELEMENT> root;
46+
    protected BTNode<ELEMENT> root; // raiz
47
48
    //endregion
49
50
51
    //region Constructors
52
53
    public BinaryTree() {
54
        this.root = null;
55
    }
56
57
    // Métodos para propósitos académicos
58
    public BinaryTree(ELEMENT item) {
59
        this(item, null, null);
60
    }
61
    public BinaryTree(ELEMENT item, BinaryTree<ELEMENT> left, BinaryTree<ELEMENT> right) {
62
        this.root = new BTNode<ELEMENT>(item, null, null);
63
        if (left != null) {
64
            this.root.left = left.root;
65
        }
66
        if (right != null) {
67
            this.root.right = right.root;
68
        }
69
    }
70
71
    //endregion
72
73
    @Override
74
    public String toString() {
75
        StringBuilder sb = new StringBuilder();
76
        toString(sb, this.root);
77
        return sb.toString();
78
    }
79
    protected void toString(StringBuilder sb, BTNode<ELEMENT> root) {
80
        if (root != null) {
81
            sb.append(root.item.toString());
82
            if (root.left != null) {
83
                sb.append("(");
84
                toString(sb, root.left);
85
                if (root.right != null) {
86
                    sb.append(",");
87
                    toString(sb, root.right);
88
                }
89
                sb.append(")");
90
            } else {
91
                if (root.right != null) {
92
                    sb.append("(,");
93
                    toString(sb, root.right);
94
                    sb.append(")");
95
                }
96
            }
97
        }
98
    }
99
100
101
    public void PreOrder() {
102
        PreOrder(this.root);
103
    }
104
    protected void PreOrder(BTNode<ELEMENT> root) {
105
        if (root != null) {
106
            root.Visit();
107
            PreOrder(root.left);
108
            PreOrder(root.right);
109
        }
110
    }
111
112
    public void InOrder() {
113
        InOrder(this.root);
114
    }
115
    protected void InOrder(BTNode<ELEMENT> root) {
116
        if (root != null) {
117
            InOrder(root.left);
118
            root.Visit();
119
            InOrder(root.right);
120
        }
121
    }
122
123
    public void PostOrder() {
124
        PostOrder(this.root);
125
    }
126
    protected void PostOrder(BTNode<ELEMENT> root) {
127
        if (root != null) {
128
            PostOrder(root.left);
129
            PostOrder(root.right);
130
            root.Visit();
131
        }
132
    }
133
134
    public void DescendingOrder() {
135
        DescendingOrder(this.root);
136
    }
137
    protected void DescendingOrder(BTNode<ELEMENT> root) {
138
        if (root != null) {
139
            DescendingOrder(root.right);
140
            root.Visit();
141
            DescendingOrder(root.left);
142
        }
143
    }
144
145
146
    public int NodeCount() {
147
        return NodeCount(this.root);
148
    }
149
    protected int NodeCount(BTNode<ELEMENT> root) {
150
        if (root != null) {
151
            return 1 + NodeCount(root.left) + NodeCount(root.right);
152
        }
153
        return 0;
154
    }
155
156
157
    public int LeafCount() {
158
        return LeafCount(this.root);
159
    }
160
    protected int LeafCount(BTNode<ELEMENT> root) {
161
        if (root != null) {
162
            if ( (root.left == null) && (root.right == null) ) {
163
                return 1;
164
            } else {
165
                return LeafCount(root.left) + LeafCount(root.right);
166
            }
167
        }
168
        return 0;
169
    }
170
171
172
    public int InternalCount() {
173
        return InternalCount(this.root);
174
    }
175
    protected int InternalCount(BTNode<ELEMENT> root) {
176
        if (root != null) {
177
            if ( (root.left == null) && (root.right == null) ) {
178
                return 0;
179
            } else {
180
                return 1 + InternalCount(root.left) + InternalCount(root.right);
181
            }
182
        }
183
        return 0;
184
    }
185
186
187
    public int MaxLevel() {
188
        return MaxLevel(this.root);
189
    }
190
    protected int MaxLevel(BTNode<ELEMENT> root) {
191
        if (root != null) {
192
            if ( (root.left != null) || (root.right != null) ) {
193
                int leftLevel = MaxLevel(root.left);
194
                int rightLevel = MaxLevel(root.right);
195
                return 1 + Math.max(leftLevel, rightLevel);
196
            }
197
            return 0;
198
        }
199
        return -1;
200
    }
201
202
203
    public int Height() {
204
        return MaxLevel() + 1;
205
    }
206
}
207