Add the abstract class Forme that Cercle and Segment extend.
[TP_POO.git] / Arbres / ArbreBinaire.java
... / ...
CommitLineData
1
2/**
3 * Binary tree class.
4 * A binary tree is a ordered value tree with only two childs per node
5 */
6public class ArbreBinaire {
7
8 private class IntNode {
9 private int data;
10 private IntNode leftIntNode;
11 private IntNode rightIntNode;
12
13 IntNode(int value) {
14 setData(value);
15 setLeftNode(null);
16 setRightNode(null);
17 }
18
19 IntNode(int value, IntNode leftNode, IntNode rightNode) {
20 setData(value);
21 setLeftNode(leftNode);
22 setRightNode(rightNode);
23 }
24
25 private int getData() {
26 return data;
27 }
28
29 private void setData(int value) {
30 data = value;
31 }
32
33 private IntNode getLeftNode() {
34 return leftIntNode;
35 }
36
37 private void setLeftNode(IntNode leftNode) {
38 leftIntNode = leftNode;
39 }
40
41 private IntNode getRightNode() {
42 return rightIntNode;
43 }
44
45 private void setRightNode(IntNode rightNode) {
46 rightIntNode = rightNode;
47 }
48
49 }
50
51 private IntNode rootNode;
52
53 ArbreBinaire() {
54 setRootNode(null);
55 }
56
57 private void setRootNode(IntNode node) {
58 rootNode = node;
59 }
60
61 private IntNode getRootNode() {
62 return rootNode;
63 }
64
65 private boolean isEmpty() {
66 return (getRootNode() == null);
67 }
68
69 private IntNode inserer_rec(IntNode currentNode, int value) {
70 if (currentNode == null) {
71 return new IntNode(value);
72 }
73 if (value < currentNode.getData()) {
74 currentNode.setLeftNode(inserer_rec(currentNode.getLeftNode(), value));
75 } else if (value > currentNode.getData()) {
76 currentNode.setRightNode(inserer_rec(currentNode.getRightNode(), value));
77 } /* skip the equality case */
78 return currentNode;
79 }
80
81 public void inserer(int value) {
82 setRootNode(inserer_rec(rootNode, value));
83 }
84
85 private IntNode supprimer_rec(IntNode currentNode, int value) {
86 if (currentNode == null) {
87 return null;
88 }
89 if (value == currentNode.getData()) {
90 if (currentNode.getLeftNode() == null && currentNode.getRightNode() == null) {
91 return null;
92 } else if (currentNode.getRightNode() == null) {
93 return currentNode.getLeftNode();
94 } else if (currentNode.getLeftNode() == null) {
95 return currentNode.getRightNode();
96 } else {
97 /*
98 * First, we need to find the node that will replace the deleted node.
99 * We’ll use the smallest node of the node to be deleted’s right sub-tree.
100 * Then, we assign the smallest value to the node to delete and after that,
101 * we’ll delete it from the right subtree.
102 */
103 int smallestValue = findSmallestData(currentNode.getRightNode());
104 currentNode.setData(smallestValue);
105 currentNode.setRightNode(supprimer_rec(currentNode.getRightNode(), smallestValue));
106 return currentNode;
107 }
108 } else if (value < currentNode.getData()) {
109 currentNode.setLeftNode(supprimer_rec(currentNode.getLeftNode(), value));
110 } else {
111 currentNode.setRightNode(supprimer_rec(currentNode.getRightNode(), value));
112 }
113 return currentNode;
114 }
115
116 public void supprimer(int value) {
117 supprimer_rec(rootNode, value);
118 }
119
120 private boolean hasDataRec(IntNode currentNode, int value) {
121 if (currentNode == null) {
122 return false;
123 }
124 if (value == currentNode.getData()) {
125 return true;
126 }
127 return value < currentNode.getData() ? hasDataRec(currentNode.getLeftNode(), value) : hasDataRec(currentNode.getRightNode(), value);
128 }
129
130 public boolean hasData(int value) {
131 return hasDataRec(rootNode, value);
132 }
133
134 private int findSmallestData(IntNode node) {
135 return node.getLeftNode() == null ? node.getData() : findSmallestData(node.getLeftNode());
136 }
137
138 private void afficher_rec(IntNode currentNode) {
139 if (currentNode != null) {
140 afficher_rec(currentNode.getLeftNode());
141 System.out.print(currentNode.getData() + " ");
142 afficher_rec(currentNode.getRightNode());
143 }
144 }
145
146 public void afficher() {
147 afficher_rec(rootNode);
148 System.out.println();
149 }
150
151 private void afficher_arbre_rec(IntNode currentNode, int column) {
152 if (currentNode != null) {
153 afficher_arbre_rec(currentNode.getRightNode(), column + 1);
154 for (int i = 0; i < column; i++) {
155 System.out.print(" ");
156 }
157 System.out.println(currentNode.getData());
158 afficher_arbre_rec(currentNode.getLeftNode(), column + 1);
159 }
160 }
161
162 public void afficher_arbre() {
163 afficher_arbre_rec(rootNode, 1);
164 }
165
166 public static void main(String[] args) {
167 ArbreBinaire bTree = new ArbreBinaire();
168
169 bTree.inserer(2);
170 bTree.inserer(6);
171 bTree.inserer(4);
172 bTree.inserer(5);
173 bTree.inserer(1);
174 bTree.inserer(0);
175
176 bTree.afficher();
177 bTree.afficher_arbre();
178
179 bTree.supprimer(4);
180
181 bTree.afficher();
182 bTree.afficher_arbre();
183
184 bTree.supprimer(6);
185
186 bTree.afficher();
187 bTree.afficher_arbre();
188
189 bTree.inserer(2);
190 bTree.inserer(7);
191 bTree.inserer(3);
192 bTree.inserer(9);
193 bTree.inserer(11);
194 bTree.inserer(10);
195 bTree.inserer(8);
196 bTree.inserer(4);
197
198 bTree.afficher();
199 bTree.afficher_arbre();
200 }
201
202}