Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commita8bc10f

Browse files
author
jsquared21
committed
Add Ex 25.09
1 parente22003e commita8bc10f

File tree

11 files changed

+480
-0
lines changed

11 files changed

+480
-0
lines changed
554 Bytes
Binary file not shown.
Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
publicabstractclassAbstractTree<E>
2+
implementsTree<E>{
3+
@Override/** Inorder traversal from the root */
4+
publicvoidinorder() {
5+
}
6+
7+
@Override/** Postorder traversal from the root */
8+
publicvoidpostorder() {
9+
}
10+
11+
@Override/** Preorder traversal from the root */
12+
publicvoidpreorder() {
13+
}
14+
15+
@Override/** Return true if the tree is empty */
16+
publicbooleanisEmpty() {
17+
returngetSize() ==0;
18+
}
19+
}
1.51 KB
Binary file not shown.
524 Bytes
Binary file not shown.
5.59 KB
Binary file not shown.
Lines changed: 367 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,367 @@
1+
importjava.util.Stack;
2+
publicclassBST<EextendsComparable<E>>
3+
extendsAbstractTree<E>implementsCloneable {
4+
protectedTreeNode<E>root;
5+
protectedintsize =0;
6+
7+
/** Create a default binary search tree */
8+
publicBST() {
9+
}
10+
11+
/** Create a binary search tree from an array of objects */
12+
publicBST(E[]objects) {
13+
for (inti =0;i <objects.length;i++)
14+
insert(objects[i]);
15+
}
16+
17+
@Override/** Return true if the element is in the tree */
18+
publicbooleansearch(Ee) {
19+
TreeNode<E>current =root;// Start from the root
20+
21+
while (current !=null) {
22+
if (e.compareTo(current.element) <0) {
23+
current =current.left;// Go left
24+
}
25+
elseif (e.compareTo(current.element) >0) {
26+
current =current.right;// Go right
27+
}
28+
else// Element matches current.element
29+
returntrue;// Element is found
30+
}
31+
32+
returnfalse;// Element is not in the tree
33+
}
34+
35+
@Override/** Insert element e into the binary search tree.
36+
*Return true if the element is inserted successfully. */
37+
publicbooleaninsert(Ee) {
38+
if (root ==null)
39+
root =createNewNode(e);// Create a new root
40+
else {
41+
// Locate the parent node
42+
TreeNode<E>parent =null;
43+
TreeNode<E>current =root;
44+
while (current !=null) {
45+
if (e.compareTo(current.element) <0) {
46+
parent =current;
47+
current =current.left;
48+
}
49+
elseif (e.compareTo(current.element) >0) {
50+
parent =current;
51+
current =current.right;
52+
}
53+
else
54+
returnfalse;// Duplicate node not inserted
55+
}
56+
// Create the new node and attach it to the parent
57+
if (e.compareTo(parent.element) <0)
58+
parent.left =createNewNode(e);
59+
else
60+
parent.right =createNewNode(e);
61+
}
62+
63+
size++;
64+
returntrue;// Element inserted successfully
65+
}
66+
67+
protectedTreeNode<E>createNewNode(Ee) {
68+
returnnewTreeNode<>(e);
69+
}
70+
71+
@Override/** Inorder traversal from the root */
72+
publicvoidinorder() {
73+
inorder(root);
74+
}
75+
76+
/** Inorder traversal from a subtree */
77+
protectedvoidinorder(TreeNode<E>root) {
78+
if (root ==null)return;
79+
inorder(root.left);
80+
System.out.print(root.element +" ");
81+
inorder(root.right);
82+
}
83+
84+
@Override/** Postorder traversal from the root */
85+
publicvoidpostorder() {
86+
postorder(root);
87+
}
88+
89+
/** Postorder traversal from a subtree */
90+
protectedvoidpostorder(TreeNode<E>root) {
91+
if (root ==null)return;
92+
postorder(root.left);
93+
postorder(root.right);
94+
System.out.print(root.element +" ");
95+
}
96+
97+
@Override/** Preorder traversal from the root */
98+
publicvoidpreorder() {
99+
preorder(root);
100+
}
101+
102+
/** Preorder traversal from a subtree */
103+
protectedvoidpreorder(TreeNode<E>root) {
104+
if (root ==null)return;
105+
System.out.print(root.element +" ");
106+
preorder(root.left);
107+
preorder(root.right);
108+
}
109+
110+
/** This inner class is static, because it does not access
111+
any instance members defined in its outer class */
112+
publicstaticclassTreeNode<EextendsComparable<E>> {
113+
protectedEelement;
114+
protectedTreeNode<E>left;
115+
protectedTreeNode<E>right;
116+
117+
publicTreeNode(Ee) {
118+
element =e;
119+
}
120+
}
121+
122+
@Override/** Get the number of nodes in the tree */
123+
publicintgetSize() {
124+
returnsize;
125+
}
126+
127+
/** Returns the root of the tree */
128+
publicTreeNode<E>getRoot() {
129+
returnroot;
130+
}
131+
132+
/** Return a path from the root leadting to the specified element */
133+
publicjava.util.ArrayList<TreeNode<E>>path(Ee) {
134+
java.util.ArrayList<TreeNode<E>>list =
135+
newjava.util.ArrayList<>();
136+
TreeNode<E>current =root;// Start from the root
137+
138+
while (current !=null) {
139+
list.add(current);// Add the node to the list
140+
if (e.compareTo(current.element) <0) {
141+
current =current.left;
142+
}
143+
elseif (e.compareTo(current.element) >0) {
144+
current =current.right;
145+
}
146+
else
147+
break;
148+
}
149+
150+
returnlist;// Return an array list of nodes
151+
}
152+
153+
@Override/** Delete an element from the binary search tree.
154+
* Return true if the element is deleted successfully.
155+
* Return false if the element is not in the tree. */
156+
publicbooleandelete(Ee) {
157+
//Locate the node to be deleted and also locate its parent node
158+
TreeNode<E>parent =null;
159+
TreeNode<E>current =root;
160+
while (current !=null) {
161+
if (e.compareTo(current.element) <0) {
162+
parent =current;
163+
current =current.left;
164+
}
165+
elseif (e.compareTo(current.element) >0) {
166+
parent =current;
167+
current =current.right;
168+
}
169+
else
170+
break;// Element is in the tree pointed at by current
171+
}
172+
173+
if (current ==null)
174+
returnfalse;// Element is not in the tree
175+
176+
// Case 1: current has no left child
177+
if (current.left ==null) {
178+
// Connect the parent with the right child of the current node
179+
if (parent ==null) {
180+
root =current.right;
181+
}
182+
else {
183+
if (e.compareTo(parent.element) <0)
184+
parent.left =current.right;
185+
else
186+
parent.right =current.right;
187+
}
188+
}
189+
else {
190+
// Case 2: The current node has a left child.
191+
// Locate the rightmost node in the left subtree of
192+
// the current node an also its parent.
193+
TreeNode<E>parentOfRightMost =current;
194+
TreeNode<E>rightMost =current.left;
195+
196+
while (rightMost.right !=null) {
197+
parentOfRightMost =rightMost;
198+
rightMost =rightMost.right;// Keep going to the right
199+
}
200+
201+
// Replace the element in current by the element in rightMost
202+
current.element =rightMost.element;
203+
204+
// Eliminate rightmost node
205+
if (parentOfRightMost.right ==rightMost)
206+
parentOfRightMost.right =rightMost.left;
207+
else
208+
// Special case: parentOfRightMost == current
209+
parentOfRightMost.left =rightMost.left;
210+
}
211+
212+
size--;
213+
returntrue;// Element deleted successfully
214+
}
215+
216+
@Override/** Obtain an iterator. Use inorder. */
217+
publicjava.util.Iterator<E>iterator() {
218+
returnnewInorderIterator();
219+
}
220+
221+
// Inner class InorderIterator
222+
privateclassInorderIteratorimplementsjava.util.Iterator<E> {
223+
// Store the elements in a list
224+
privatejava.util.ArrayList<E>list =
225+
newjava.util.ArrayList<>();
226+
privateintcurrent =0;// Point to the current element in list
227+
228+
publicInorderIterator() {
229+
inorder();// Traverse binary tree and store elements in list
230+
}
231+
232+
/** Inorder traversal from the root */
233+
privatevoidinorder() {
234+
inorder(root);
235+
}
236+
237+
/** Inorder traversal from a subtree */
238+
privatevoidinorder(TreeNode<E>root) {
239+
if (root ==null)return;
240+
inorder(root.left);
241+
list.add(root.element);
242+
inorder(root.right);
243+
}
244+
245+
@Override/** More elements for traversing? */
246+
publicbooleanhasNext() {
247+
if (current <list.size())
248+
returntrue;
249+
250+
returnfalse;
251+
}
252+
253+
@Override/** Get the current element and move to the next */
254+
publicEnext() {
255+
returnlist.get(current++);
256+
}
257+
258+
@Override/** Remove the current element */
259+
publicvoidremove() {
260+
delete(list.get(current));// Delete the current element
261+
list.clear();// Clear the list
262+
inorder();// Rebuild the list
263+
}
264+
}
265+
266+
/** Remove all elements from the tree */
267+
publicvoidclear() {
268+
root =null;
269+
size =0;
270+
}
271+
272+
/** Displays the nodes in a breadth-first traversal */
273+
publicvoidbreadthFirstTraversal() {
274+
if (root ==null)return;
275+
java.util.Queue<TreeNode<E>>queue =newjava.util.LinkedList<>();
276+
queue.add(root);
277+
while (!queue.isEmpty()){
278+
TreeNode<E>current =queue.element();
279+
if (current.left !=null) {
280+
queue.add(current.left);
281+
}
282+
if (current.right !=null) {
283+
queue.add(current.right);
284+
}
285+
System.out.print(queue.remove().element +" ");
286+
}
287+
}
288+
289+
/** Returns the height of this binary tree */
290+
publicintheight() {
291+
returnheight(root);
292+
}
293+
294+
/** Height from a subtree */
295+
protectedintheight(TreeNode<E>root) {
296+
if (root ==null)return0;
297+
return1 +Math.max(height(root.left),height(root.right));
298+
}
299+
300+
/** Returns true if the tree is a full binary tree */
301+
publicbooleanisFullBST() {
302+
returnsize ==Math.pow(2,height()) -1 ?true :false;
303+
}
304+
305+
/** Returns the number of leaf nodes */
306+
publicintgetNumberOfLeaves() {
307+
returngetNumberOfLeaves(root);
308+
}
309+
310+
/** Returns the number of leaf nodes */
311+
protectedintgetNumberOfLeaves(TreeNode<E>root) {
312+
if (root ==null)return0;
313+
314+
// If node has no children return 1
315+
// else return the sum of all the leaves
316+
returnroot.left ==null &&root.right ==null ?1 :
317+
getNumberOfLeaves(root.left) +getNumberOfLeaves(root.right);
318+
}
319+
320+
/** Returns the number of nonleaf nodes */
321+
publicintgetNumberOfNonLeaves() {
322+
returngetNumberOfNonLeaves(root);
323+
}
324+
325+
/** Returns the number of nonleaf nodes */
326+
protectedintgetNumberOfNonLeaves(TreeNode<E>root) {
327+
if (root ==null)return0;
328+
329+
// If node has children return 0
330+
// else return 1 plus the sum of the nonleaves
331+
return (root.left ==null &&root.right ==null) ?0 :
332+
1 +getNumberOfNonLeaves(root.left) +
333+
getNumberOfNonLeaves(root.right) ;
334+
}
335+
336+
/** Returns true if two trees are equal.
337+
Otherwise returns false (recursive) */
338+
publicbooleanequals(BST<E>tree) {
339+
if (tree.size !=size)returnfalse;
340+
returnequals(root,tree.root);
341+
}
342+
343+
/** Equals helper */
344+
protectedbooleanequals(TreeNode<E>root1,TreeNode<E>root2) {
345+
if (root1 ==root2)returntrue;
346+
if (root1 ==null ||root2 ==null)returnfalse;
347+
returnroot1.element.equals(root2.element) &&
348+
equals(root1.left,root2.left) &&
349+
equals(root1.right,root2.right);
350+
}
351+
352+
@Override/** Override the protected clone method
353+
defined in the Object class, and deep copy BST */
354+
publicBST<E>clone()throwsCloneNotSupportedException {
355+
BST<E>cloneBST =newBST<>();
356+
clone(cloneBST,root);
357+
returncloneBST;
358+
}
359+
360+
/** Clone helper */
361+
protectedvoidclone(BST<E>clone,TreeNode<E>root) {
362+
if (root ==null)return;
363+
clone.insert(root.element);
364+
clone(clone,root.left);
365+
clone(clone,root.right);
366+
}
367+
}
1.32 KB
Binary file not shown.

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp