JavaArithmetic/src/datastructure/BST/BST.java at master · sqlcyi2008/JavaArithmetic · GitHub

Repository navigation

History

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

package datastructure.BST;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Stack;

public class BST<E extends Comparable<E>> {

private class Node {

public E e;

public Node left, right;

public Node(E e) {

this.e = e;

left = null;

right = null;

}

private Node root;

private int size;

public BST() {

root = null;

size = 0;

}

public int size() {

return size;

}

public boolean isEmpty() {

return size == 0;

}

// 向二分搜索树中添加新的元素e

public void add(E e) {

root = add(root, e);

}

// 向以node为根的二分搜索树中插入元素e，递归算法

// 返回插入新节点后二分搜索树的根

private Node add(Node node, E e) {

if (node == null) {

size++;

return new Node(e);

}

if (e.compareTo(node.e) < 0)

node.left = add(node.left, e);

else if (e.compareTo(node.e) > 0)

node.right = add(node.right, e);

return node;

}

// 看二分搜索树中是否包含元素e

public boolean contains(E e) {

return contains(root, e);

}

// 看以node为根的二分搜索树中是否包含元素e, 递归算法

private boolean contains(Node node, E e) {

if (node == null)

return false;

if (e.compareTo(node.e) == 0)

return true;

else if (e.compareTo(node.e) < 0)

return contains(node.left, e);

else // e.compareTo(node.e) > 0

return contains(node.right, e);

}

// 二分搜索树的前序遍历

public void preOrder() {

preOrder(root);

}

// 前序遍历以node为根的二分搜索树, 递归算法

private void preOrder(Node node) {

if (node == null)

return;

System.out.println(node.e);

preOrder(node.left);

preOrder(node.right);

}

// 二分搜索树的非递归先序遍历

public void preOrderNR() {

Stack<Node> stack = new Stack<>();

stack.push(root);

while (!stack.isEmpty()) {

Node cur = stack.pop();

System.out.println(cur.e);

if (cur.right != null)

stack.push(cur.right);

if (cur.left != null)

stack.push(cur.left);

}

// 二分搜索树的中序遍历

public void inOrder() {

inOrder(root);

}

// 中序遍历以node为根的二分搜索树, 递归算法

private void inOrder(Node node) {

if (node == null)

return;

inOrder(node.left);

System.out.println(node.e);

inOrder(node.right);

}

// 二分搜索树的后序遍历

public void postOrder() {

postOrder(root);

}

// 后序遍历以node为根的二分搜索树, 递归算法

private void postOrder(Node node) {

if (node == null)

return;

postOrder(node.left);

postOrder(node.right);

System.out.println(node.e);

}

// 二分搜索树的层序遍历

public void levelOrder() {

Queue<Node> q = new LinkedList<>();

q.add(root);

while (!q.isEmpty()) {

Node cur = q.remove();

System.out.println(cur.e);

if (cur.left != null)

q.add(cur.left);

if (cur.right != null)

q.add(cur.right);

}

// 寻找二分搜索树的最小元素

public E minimum() {

if (size == 0)

throw new IllegalArgumentException("BST is empty!");

return minimum(root).e;

}

// 返回以node为根的二分搜索树的最小值所在的节点

private Node minimum(Node node) {

if (node.left == null)

return node;

return minimum(node.left);

}

// 寻找二分搜索树的最大元素

public E maximum() {

if (size == 0)

throw new IllegalArgumentException("BST is empty");

return maximum(root).e;

}

// 返回以node为根的二分搜索树的最大值所在的节点

private Node maximum(Node node) {

if (node.right == null)

return node;

return maximum(node.right);

}

// 从二分搜索树中删除最小值所在节点, 返回最小值

public E removeMin() {

E ret = minimum();

root = removeMin(root);

return ret;

}

// 删除掉以node为根的二分搜索树中的最小节点

// 返回删除节点后新的二分搜索树的根

private Node removeMin(Node node) {

// 如果当前最小节点是有右子树的，那么将其作为删除后的左子树！

if (node.left == null) {

Node rightNode = node.right;

node.right = null;

size--;

return rightNode;

}

node.left = removeMin(node.left);

return node;

}

// 从二分搜索树中删除最大值所在节点

public E removeMax() {

E ret = maximum();

root = removeMax(root);

return ret;

}

// 删除掉以node为根的二分搜索树中的最大节点

// 返回删除节点后新的二分搜索树的根

private Node removeMax(Node node) {

if (node.right == null) {

Node leftNode = node.left;

node.left = null;

size--;

return leftNode;

}

node.right = removeMax(node.right);

return node;

}

// 从二分搜索树中删除元素为e的节点

public void remove(E e) {

root = remove(root, e);

}

// 删除掉以node为根的二分搜索树中值为e的节点, 递归算法

// 返回删除节点后新的二分搜索树的根

private Node remove(Node node, E e) {

if (node == null)

return null;

if (e.compareTo(node.e) < 0) {

node.left = remove(node.left, e);

return node;

} else if (e.compareTo(node.e) > 0) {

node.right = remove(node.right, e);

return node;

} else { // e.compareTo(node.e) == 0

// 待删除节点左子树为空的情况

if (node.left == null) {

Node rightNode = node.right;

node.right = null;

size--;

return rightNode;

}

// 待删除节点右子树为空的情况

if (node.right == null) {

Node leftNode = node.left;

node.left = null;

size--;

return leftNode;

}

// 待删除节点左右子树均不为空的情况

// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点

// 用这个节点顶替待删除节点的位置

Node successor = minimum(node.right);

successor.right = removeMin(node.right);

successor.left = node.left;

node.left = node.right = null;

return successor;

}

@Override

public String toString() {

StringBuilder res = new StringBuilder();

generateBSTString(root, 0, res);

return res.toString();

}

// 生成以node为根节点，深度为depth的描述二叉树的字符串

private void generateBSTString(Node node, int depth, StringBuilder res) {

if (node == null) {

res.append(generateDepthString(depth) + "null\n");

return;

}

res.append(generateDepthString(depth) + node.e + "\n");

generateBSTString(node.left, depth + 1, res);

generateBSTString(node.right, depth + 1, res);

}

private String generateDepthString(int depth) {

StringBuilder res = new StringBuilder();

for (int i = 0; i < depth; i++)

res.append("--");

return res.toString();

}

JavaArithmetic/src/datastructure/BST/BST.java at master · sqlcyi2008/JavaArithmetic · GitHub

Repository navigation

Expand file tree

Breadcrumbs

BST.java

Latest commit

History

Breadcrumbs

BST.java

File metadata and controls