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 |