Test ArrayBinaryTree [hm] [1011272]

!7

p {
}

// ArrayBinaryTree.java			Authors:  Lewis/Chase
// Implements the BinaryTreeADT interface using an array

sclass ArrayBinaryTree<T> {
   int count;
   T[] tree; 
   static final int capacity = 50;

   //================================================================
   //  Creates an empty binary tree.
   //================================================================
   public ArrayBinaryTree() 
   {
      count = 0;
      tree = (T[]) new Object[capacity];
   }  // constructor BinaryTree

   //================================================================
   //  Creates a binary tree with the specified element as its root.
   //================================================================
   public ArrayBinaryTree (T element) 
   {
      count = 1;
      tree = (T[]) new Object[capacity];

      tree[0] = element;
   }  // constructor BinaryTree



   protected void expandCapacity()
   {
      T[] temp = (T[]) new Object[tree.length * 2];
      for (int ct=0; ct < tree.length; ct++)
         temp[ct] = tree[ct];
      tree = temp;
   }
   
   //================================================================
   //  Removes the left subtree of this binary tree.
   //================================================================
   public void removeLeftSubtree() 
   {

   }  // method removeLeftSubtree

   //================================================================
   //  Removes the right subtree of this binary tree.
   //================================================================
   public void removeRightSubtree() 
   {
      
   }  // method removeRightSubtree
   
   //================================================================
   //  Deletes all nodes from the binary tree.
   //================================================================
   public void removeAllElements() 
   {
      count = 0;
      for (int ct=0; ct<tree.length; ct++)      
         tree[ct] = null;
   }  // method removeAllElements
   
   //================================================================
   //  Returns true if the binary tree is empty and false otherwise.
   //================================================================
   public boolean isEmpty() 
   {
      return (count == 0);
   }  // method isEmpty

   //================================================================
   //  Returns true if the binary tree is empty and false otherwise.
   //================================================================
   public int size() 
   {
      return count;
   }  // method size
   
   //================================================================
   //  Returns true if the tree contains an element that matches the
   //  specified target element and false otherwise.
   //================================================================
   public boolean contains (T targetElement) 
   {
      boolean found = false;

      for (int ct=0; ct<count && !found; ct++)
         if (targetElement.equals(tree[ct]))
	       found = true;

      return found;

   }  // method contains

   //================================================================
   //  Returns a reference to the specified target element if it is
   //  found in the binary tree.  Throws a NoSuchElementException if
   //  the specified target element is not found in the binary tree.
   //================================================================
   public T find (T targetElement) throws ElementNotFoundException 
   {
      T temp=null;
	 boolean found = false;

      for (int ct=0; ct<count && !found; ct++)
         if (targetElement.equals(tree[ct]))
         {
	       found = true;
            temp = tree[ct];
         }

      if (!found)
         throw new ElementNotFoundException("binary tree");

      return temp;


   }  // method find



   //================================================================
   //  Returns a string representation of the binary tree.
   //================================================================
   public String toString() 
   {
      ArrayUnorderedList<T> templist = new ArrayUnorderedList<T>();
      inorder (0, templist);
      return templist.toString();
   }  // method toString

   //================================================================
   //  Performs an inorder traversal on the binary tree by calling an
   //  overloaded, recursive inorder method that starts with
   //  the root.
   //================================================================
   public Iterator<T> iteratorInOrder() 
   {
      ArrayUnorderedList<T> templist = new ArrayUnorderedList<T>();
      inorder (0, templist);
      return templist.iterator();
   }  // method inorder

   //================================================================
   //  Performs a recursive inorder traversal.
   //================================================================
   protected void inorder (int node, ArrayUnorderedList<T> templist) 
   {
      if (node < tree.length)
         if (tree[node] != null) 
 	    {
            inorder ((node+1)*2-1, templist);
            templist.addToRear(tree[node]);
            inorder ((node+1)*(2+1)-1, templist);
         }//if

   }  // method inorder

   //================================================================
   //  Performs an preorder traversal on the binary tree by calling an
   //  overloaded, recursive preorder method that starts with
   //  the root.
   //================================================================
   public Iterator<T> iteratorPreOrder() 
   {
      ArrayUnorderedList<T> templist = new ArrayUnorderedList<T>();
      preorder (0, templist);
      return templist.iterator();
   }  // method preorder

   //================================================================
   //  Performs a recursive preorder traversal.
   //================================================================
   protected void preorder (int node, ArrayUnorderedList<T> templist) 
   {
      if (node < tree.length)
         if (tree[node] != null) 
 	    { 
            templist.addToRear(tree[node]);
            inorder ((node+1)*2-1, templist);
            inorder ((node+1)*(2+1)-1, templist);
         }//if

      

   }  // method preorder

   //================================================================
   //  Performs an postorder traversal on the binary tree by calling
   //  an overloaded, recursive postorder method that starts
   //  with the root.
   //================================================================
   public Iterator<T> iteratorPostOrder() 
   {
      ArrayUnorderedList<T> templist = new ArrayUnorderedList<T>();
      postorder (0, templist);
      return templist.iterator();
   }  // method postorder

   //================================================================
   //  Performs a recursive postorder traversal.
   //================================================================
   protected void postorder (int node, ArrayUnorderedList<T> templist) 
   {
      if (node < tree.length)
         if (tree[node] != null) 
 	    {
            inorder ((node+1)*2-1, templist); 
            inorder ((node+1)*(2+1)-1, templist);
            templist.addToRear(tree[node]);
            
         }//if


   }  // method postorder

   //================================================================
   //  Performs a levelorder traversal on the binary tree, using a
   //  templist.
   //================================================================
   public Iterator<T> iteratorLevelOrder() 
   {
      ArrayUnorderedList<T> templist = new ArrayUnorderedList<T>();
      for (int ct=0; ct<count; ct++)
         templist.addToRear(tree[ct]);
      return templist.iterator();
   }  // method levelorder
}  // class BinaryTree

Travelled to 13 computer(s): aoiabmzegqzx, bhatertpkbcr, cbybwowwnfue, cfunsshuasjs, gwrvuhgaqvyk, ishqpsrjomds, lpdgvwnxivlt, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tslmcundralx, tvejysmllsmz, vouqrxazstgt

Snippet ID:	#1011272
Snippet name:	Test ArrayBinaryTree [hm]
Eternal ID of this version:	#1011272/1
Text MD5:	b662edea7583991ebdd94d03e5cfad91
Author:	stefan
Category:	javax
Type:	JavaX source code (desktop)
Public (visible to everyone):	Yes
Archived (hidden from active list):	No
Created/modified:	2017-10-21 22:35:29
Source code size:	8012 bytes / 235 lines
Pitched / IR pitched:	No / No
Views / Downloads:	496 / 673
Referenced in:	[show references]

< > BotCompany Repo | #1011272 // Test ArrayBinaryTree [hm]

JavaX source code (desktop) - run with: x30.jar

1	!7
2
3	p {
4	}
5
6	// ArrayBinaryTree.java Authors: Lewis/Chase
7	// Implements the BinaryTreeADT interface using an array
8
9	sclass ArrayBinaryTree<T> {
10	int count;
11	T[] tree;
12	static final int capacity = 50;
13
14	//================================================================
15	// Creates an empty binary tree.
16	//================================================================
17	public ArrayBinaryTree()
18	{
19	count = 0;
20	tree = (T[]) new Object[capacity];
21	} // constructor BinaryTree
22
23	//================================================================
24	// Creates a binary tree with the specified element as its root.
25	//================================================================
26	public ArrayBinaryTree (T element)
27	{
28	count = 1;
29	tree = (T[]) new Object[capacity];
30
31	tree[0] = element;
32	} // constructor BinaryTree
33
34
35
36	protected void expandCapacity()
37	{
38	T[] temp = (T[]) new Object[tree.length * 2];
39	for (int ct=0; ct < tree.length; ct++)
40	temp[ct] = tree[ct];
41	tree = temp;
42	}
43
44	//================================================================
45	// Removes the left subtree of this binary tree.
46	//================================================================
47	public void removeLeftSubtree()
48	{
49
50	} // method removeLeftSubtree
51
52	//================================================================
53	// Removes the right subtree of this binary tree.
54	//================================================================
55	public void removeRightSubtree()
56	{
57
58	} // method removeRightSubtree
59
60	//================================================================
61	// Deletes all nodes from the binary tree.
62	//================================================================
63	public void removeAllElements()
64	{
65	count = 0;
66	for (int ct=0; ct<tree.length; ct++)
67	tree[ct] = null;
68	} // method removeAllElements
69
70	//================================================================
71	// Returns true if the binary tree is empty and false otherwise.
72	//================================================================
73	public boolean isEmpty()
74	{
75	return (count == 0);
76	} // method isEmpty
77
78	//================================================================
79	// Returns true if the binary tree is empty and false otherwise.
80	//================================================================
81	public int size()
82	{
83	return count;
84	} // method size
85
86	//================================================================
87	// Returns true if the tree contains an element that matches the
88	// specified target element and false otherwise.
89	//================================================================
90	public boolean contains (T targetElement)
91	{
92	boolean found = false;
93
94	for (int ct=0; ct<count && !found; ct++)
95	if (targetElement.equals(tree[ct]))
96	found = true;
97
98	return found;
99
100	} // method contains
101
102	//================================================================
103	// Returns a reference to the specified target element if it is
104	// found in the binary tree. Throws a NoSuchElementException if
105	// the specified target element is not found in the binary tree.
106	//================================================================
107	public T find (T targetElement) throws ElementNotFoundException
108	{
109	T temp=null;
110	boolean found = false;
111
112	for (int ct=0; ct<count && !found; ct++)
113	if (targetElement.equals(tree[ct]))
114	{
115	found = true;
116	temp = tree[ct];
117	}
118
119	if (!found)
120	throw new ElementNotFoundException("binary tree");
121
122	return temp;
123
124
125	} // method find
126
127
128
129	//================================================================
130	// Returns a string representation of the binary tree.
131	//================================================================
132	public String toString()
133	{
134	ArrayUnorderedList<T> templist = new ArrayUnorderedList<T>();
135	inorder (0, templist);
136	return templist.toString();
137	} // method toString
138
139	//================================================================
140	// Performs an inorder traversal on the binary tree by calling an
141	// overloaded, recursive inorder method that starts with
142	// the root.
143	//================================================================
144	public Iterator<T> iteratorInOrder()
145	{
146	ArrayUnorderedList<T> templist = new ArrayUnorderedList<T>();
147	inorder (0, templist);
148	return templist.iterator();
149	} // method inorder
150
151	//================================================================
152	// Performs a recursive inorder traversal.
153	//================================================================
154	protected void inorder (int node, ArrayUnorderedList<T> templist)
155	{
156	if (node < tree.length)
157	if (tree[node] != null)
158	{
159	inorder ((node+1)*2-1, templist);
160	templist.addToRear(tree[node]);
161	inorder ((node+1)*(2+1)-1, templist);
162	}//if
163
164	} // method inorder
165
166	//================================================================
167	// Performs an preorder traversal on the binary tree by calling an
168	// overloaded, recursive preorder method that starts with
169	// the root.
170	//================================================================
171	public Iterator<T> iteratorPreOrder()
172	{
173	ArrayUnorderedList<T> templist = new ArrayUnorderedList<T>();
174	preorder (0, templist);
175	return templist.iterator();
176	} // method preorder
177
178	//================================================================
179	// Performs a recursive preorder traversal.
180	//================================================================
181	protected void preorder (int node, ArrayUnorderedList<T> templist)
182	{
183	if (node < tree.length)
184	if (tree[node] != null)
185	{
186	templist.addToRear(tree[node]);
187	inorder ((node+1)*2-1, templist);
188	inorder ((node+1)*(2+1)-1, templist);
189	}//if
190
191
192
193	} // method preorder
194
195	//================================================================
196	// Performs an postorder traversal on the binary tree by calling
197	// an overloaded, recursive postorder method that starts
198	// with the root.
199	//================================================================
200	public Iterator<T> iteratorPostOrder()
201	{
202	ArrayUnorderedList<T> templist = new ArrayUnorderedList<T>();
203	postorder (0, templist);
204	return templist.iterator();
205	} // method postorder
206
207	//================================================================
208	// Performs a recursive postorder traversal.
209	//================================================================
210	protected void postorder (int node, ArrayUnorderedList<T> templist)
211	{
212	if (node < tree.length)
213	if (tree[node] != null)
214	{
215	inorder ((node+1)*2-1, templist);
216	inorder ((node+1)*(2+1)-1, templist);
217	templist.addToRear(tree[node]);
218
219	}//if
220
221
222	} // method postorder
223
224	//================================================================
225	// Performs a levelorder traversal on the binary tree, using a
226	// templist.
227	//================================================================
228	public Iterator<T> iteratorLevelOrder()
229	{
230	ArrayUnorderedList<T> templist = new ArrayUnorderedList<T>();
231	for (int ct=0; ct<count; ct++)
232	templist.addToRear(tree[ct]);
233	return templist.iterator();
234	} // method levelorder
235	} // class BinaryTree