KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > jegg > btree > BinaryTree


1 /*
2  * Copyright (c) 2004, Bruce Lowery
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are met:
7  *
8  * - Redistributions of source code must retain the above copyright notice,
9  * this list of conditions and the following disclaimer.
10  * - Redistributions in binary form must reproduce the above copyright
11  * notice, this list of conditions and the following disclaimer in the
12  * documentation and/or other materials provided with the distribution.
13  * - Neither the name of JEGG nor the names of its contributors may be used
14  * to endorse or promote products derived from this software without
15  * specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
21  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27  * POSSIBILITY OF SUCH DAMAGE.
28  */
29 package jegg.btree;
30
31 /**
32  *
33  */
34 public class BinaryTree
35 {
36     private Node root;
37     public BinaryTree()
38     {
39         // EMPTY
40 }
41     public void insert(final int pos, final Object JavaDoc obj)
42     {
43         if (null == root)
44         {
45             root = new Node(pos,obj);
46         }
47         else
48         {
49             Node cur = root;
50             while (null != cur)
51             {
52                 int cur_pos = cur.getPosition();
53                 if (cur_pos == pos)
54                 {
55                     cur.setObject(obj);
56                     break;
57                 }
58                 else
59                 if (cur_pos > pos)
60                 {
61                     Node nxt = cur.getLesser();
62                     if (null == nxt)
63                     {
64                         cur.setLesser(new Node(pos,obj));
65                         break;
66                     }
67                     cur = nxt;
68                 }
69                 else
70                 if (cur_pos < pos)
71                 {
72                     Node nxt = cur.getGreater();
73                     if (null == nxt)
74                     {
75                         cur.setGreater(new Node(pos,obj));
76                         break;
77                     }
78                     cur = nxt;
79                 }
80             }
81         }
82     }
83     public Object JavaDoc get(int pos)
84     {
85         Node cur = root;
86         Object JavaDoc o = null;
87         while (null != cur)
88         {
89             int cur_pos = cur.getPosition();
90             if (cur_pos == pos)
91             {
92                 o = cur.getObject();
93                 break;
94             }
95             else
96             if (cur_pos > pos)
97             {
98                 cur = cur.getLesser();
99             }
100             else
101             if (cur_pos < pos)
102             {
103                 cur = cur.getGreater();
104             }
105         }
106         return o;
107     }
108     public Object JavaDoc getAtLeast(int pos)
109     {
110         Node cur = root;
111         Object JavaDoc o = null;
112         while (null != cur)
113         {
114             int cur_pos = cur.getPosition();
115             if (cur_pos >= pos)
116             {
117                 o = cur.getObject();
118                 break;
119             }
120             else
121             {
122                 cur = cur.getGreater();
123             }
124         }
125         return o;
126     }
127     public Object JavaDoc getAtMost(int pos)
128     {
129         Node cur = root;
130         Object JavaDoc o = null;
131         while (null != cur)
132         {
133             int cur_pos = cur.getPosition();
134             if (cur_pos <= pos)
135             {
136                 o = cur.getObject();
137                 break;
138             }
139             else
140             {
141                 cur = cur.getLesser();
142             }
143         }
144         return o;
145     }
146 }
147
Popular Tags