二叉查找树的java实现

java

  1 package 查找;

2

3 import java.util.ArrayList;

4 import java.util.List;

5

6 public class BST<Key extends Comparable<Key>, Value> {

7 private class Node {

8 private Key key; // 键

9 private Value value;// 值

10 private Node left, right; // 指向子树的链接

11 private int n; // 以该节点为根的子树中的节点总数

12

13 public Node(Key key, Value val, int n) {

14 this.key = key;

15 this.value = val;

16 this.n = n;

17 }

18 }

19

20 private Node root;

21

22 public int size() {

23 return size(root);

24 }

25

26 private int size(Node x) {

27 if (x == null)

28 return 0;

29 else

30 return x.n;

31 }

32

33 /**

34 * 如果树是空的,则查找未命中 如果被查找的键小于根节点,则在左子树中继续查找 如果被查找的键大于根节点,则在右子树中继续查找

35 * 如果被查找的键和根节点的键相等,查找命中

36 *

37 * @param key

38 * @return

39 */

40 public Value get(Key key) {

41 return get(root, key);

42 }

43

44 private Value get(Node x, Key key) {

45 if (x == null)

46 return null;

47 int cmp = key.compareTo(x.key);

48 if (cmp < 0)

49 return get(x.left, key);

50 else if (cmp > 0)

51 return get(x.right, key);

52 else

53 return x.value;

54 }

55

56 /**

57 * 二叉查找树的一个很重要的特性就是插入的实现难度和查找差不多。

58 * 当查找到一个不存在与树中的节点(null)时,new 新节点,并将上一路径指向该节点

59 *

60 * @param key

61 * @param val

62 */

63 public void put(Key key, Value val) {

64 root = put(root, key, val);

65 }

66

67 private Node put(Node x, Key key, Value val) {

68 if (x == null)

69 return new Node(key, val, 1);

70 int cmp = key.compareTo(x.key);

71 if (cmp < 0)

72 x.left = put(x.left, key, val);

73 else if (cmp > 0)

74 x.right = put(x.right, key, val);

75 else

76 x.value = val;

77 x.n = 1 + size(x.left) + size(x.right); // 要及时更新节点的子树数量

78 return x;

79 }

80

81 public Key min() {

82 return min(root).key;

83 }

84

85 private Node min(Node x) {

86 if (x.left == null)

87 return x;

88 return min(x.left);

89 }

90

91 public Key max() {

92 return max(root).key;

93 }

94

95 private Node max(Node x) {

96 if (x.right == null)

97 return x;

98 return max(x.right);

99 }

100

101 /**

102 * 向下取整:找出小于等于该键的最大键

103 *

104 * @param key

105 * @return

106 */

107 public Key floor(Key key) {

108 Node x = floor(root, key);

109 if (x == null)

110 return null;

111 else

112 return x.key;

113 }

114

115 /**

116 * 如果给定的键key小于二叉查找树的根节点的键,那么小于等于key的最大键一定出现在根节点的左子树中

117 * 如果给定的键key大于二叉查找树的根节点,那么只有当根节点右子树中存在大于等于key的节点时,

118 * 小于等于key的最大键才会出现在右子树中,否则根节点就是小于等于key的最大键

119 *

120 * @param x

121 * @param key

122 * @return

123 */

124 private Node floor(Node x, Key key) {

125 if (x == null)

126 return null;

127 int cmp = key.compareTo(x.key);

128 if (cmp == 0)

129 return x;

130 else if (cmp < 0)

131 return floor(x.left, key);

132 else {

133 Node t = floor(x.right, key);

134 if (t == null)

135 return x;

136 else

137 return t;

138 }

139 }

140

141 /**

142 * 向上取整:找出大于等于该键的最小键

143 *

144 * @param key

145 * @return

146 */

147 public Key ceiling(Key key) {

148 Node x = ceiling(root, key);

149 if (x == null)

150 return null;

151 else

152 return x.key;

153 }

154

155 /**

156 * 如果给定的键key大于二叉查找树的根节点的键,那么大于等于key的最小键一定出现在根节点的右子树中

157 * 如果给定的键key小于二叉查找树的根节点,那么只有当根节点左子树中存在大于等于key的节点时,

158 * 大于等于key的最小键才会出现在左子树中,否则根节点就是大于等于key的最小键

159 *

160 * @param x

161 * @param key

162 * @return

163 */

164 private Node ceiling(Node x, Key key) {

165 if (x == null)

166 return null;

167 int cmp = key.compareTo(x.key);

168 if (cmp == 0)

169 return x;

170 else if (cmp > 0) {

171 return ceiling(x.right, key);

172 } else {

173 Node t = floor(x.left, key);

174 if (t == null)

175 return x;

176 else

177 return t;

178 }

179 }

180

181 /**

182 * 选择排名为k的节点

183 *

184 * @param k

185 * @return

186 */

187 public Key select(int k) {

188 return select(root, k).key;

189 }

190

191 private Node select(Node x, int k) {

192 if (x == null)

193 return null;

194 int t = size(x.left);

195 if (t > k)

196 return select(x.left, k);

197 else if (t < k)

198 return select(x.right, k - t - 1);// 根节点也要排除掉

199 else

200 return x;

201 }

202

203 /**

204 * 查找给定键值的排名

205 *

206 * @param key

207 * @return

208 */

209 public int rank(Key key) {

210 return rank(key, root);

211 }

212

213 private int rank(Key key, Node x) {

214 if (x == null)

215 return 0;

216 int cmp = key.compareTo(x.key);

217 if (cmp < 0)

218 return rank(key, x.left);

219 else if (cmp > 0)

220 return 1 + size(x.left) + rank(key, x.right);

221 else

222 return size(x.left);

223 }

224 /**

225 * 删除最小键值对

226 */

227 public void deleteMin(){

228 root = deleteMin(root);

229 }

230 /**

231 * 不断深入根节点的左子树直到遇见一个空链接,然后将指向该节点的链接指向该结点的右子树

232 * 此时已经没有任何链接指向要被删除的结点,因此它会被垃圾收集器清理掉

233 * @param x

234 * @return

235 */

236 private Node deleteMin(Node x){

237 if(x.left == null) return x.right;

238 x.left = deleteMin(x.left);

239 x.n = 1 + size(x.left)+size(x.right);

240 return x;

241 }

242

243 public void deleteMax(){

244 root = deleteMax(root);

245 }

246 private Node deleteMax(Node x){

247 if(x.right == null ) return x.left;

248 x.right = deleteMax(x.right);

249 x.n = size(x.left)+size(x.right) + 1;

250 return x;

251 }

252

253 public void delete(Key key){

254 root = delete(root,key);

255 }

256 private Node delete(Node x, Key key){

257 if(x == null) return null;

258 int cmp = key.compareTo(x.key);

259 if(cmp < 0) x.left = delete(x.left,key);

260 else if(cmp > 0) x.right = delete(x.right,key);

261 else{

262 if(x.right == null) return x.left;

263 if(x.left == null ) return x.right;

264 /**

265 * 如果被删除节点有两个子树,将被删除节点暂记为t

266 * 从t的右子树中选取最小的节点x,将这个节点x的左子树设为t的左子树

267 * 这个节点x的右子树设为t的右子树中删除了最小节点的子树,这样就成功替换了t的位置

268 */

269 Node t = x;

270 x = min(t.right);

271 x.right = deleteMin(t.right);

272 x.left = t.left;

273 }

274 x.n = size(x.left) + size(x.right) +1;

275 return x;

276 }

277

278 public String toString(){

279 StringBuilder sb = new StringBuilder();

280 toString(root,sb);

281 sb.deleteCharAt(sb.length()-1);

282 return sb.toString();

283 }

284 private void toString(Node x, StringBuilder sb){

285 if(x == null ) return;

286 toString(x.left,sb);

287 sb.append("<"+x.key+","+x.value+">,");

288 toString(x.right,sb);

289 }

290

291 public List<Key> keys(){

292 return keys(min(),max());

293 }

294 public List<Key> keys(Key lo, Key hi){

295 List<Key> list = new ArrayList<Key>();

296 keys(root, list, lo, hi);

297 return list;

298 }

299 private void keys(Node x, List<Key> list, Key lo, Key hi){

300 if(x == null) return;

301 int cmplo = lo.compareTo(x.key);

302 int cmphi = hi.compareTo(x.key);

303 if(cmplo < 0 ) keys(x.left,list,lo,hi);

304 if(cmplo <= 0 && cmphi >= 0) list.add(x.key);

305 if(cmphi > 0 ) keys(x.right,list,lo,hi);

306 }

307 public static void main(String[] args){

308 BST<Integer,String> bst = new BST<Integer,String>();

309 bst.put(5, "e");

310 bst.put(1, "a");

311 bst.put(4, "d");

312 bst.put(9, "i");

313 bst.put(10, "j");

314 bst.put(2, "b");

315 bst.put(7, "g");

316 bst.put(3, "c");

317 bst.put(8, "h");

318 bst.put(6, "f");

319 List<Integer> keys = bst.keys();

320 for(int key : keys){

321 System.out.print("<"+key+","+bst.get(key)+">,");

322 }

323 System.out.println();

324 bst.deleteMin();

325 System.out.println(bst.toString());

326 bst.deleteMax();

327 System.out.println(bst.toString());

328 bst.delete(7);

329 System.out.println(bst.toString());

330 }

331 }

树还是应该做成可视化的方便查看和调试,后续我将更新一个可视化的生成图的版本出来,恩,一定要记得这件事

以上是 二叉查找树的java实现 的全部内容, 来源链接: utcz.com/z/393417.html

回到顶部