时代Java，与您同行！关注微信公众号，关注前沿技术，微信搜索：nowjava或时代Java，也可点击这里扫码关注

时代Java

Java 二叉搜索树的一个简单实现（不平衡）。

欢马劈雪

工程师 (已认证)

原创分享签约作者

发表于实例源码

468

二叉搜索树的一个简单实现（不平衡）。

实例源码：

源代码：

执行

执行中...

/**来自 时代Java公众号**/

import java.util.ArrayDeque;

public class BinaryTree {

TreeNode root;

public void insert(int value) {

if (root == null) {

root = new TreeNode();

root.data = value;

} else {

insertNode(value, root);

}

private void insertNode(int value, TreeNode current) {//时 代 J a v a - N o w J a v a . c o m

if (value < current.data) {

if (current.left == null) {

current.left = new TreeNode();

current.left.data = value;

} else {

insertNode(value, current.left);

}

} else {

if (current.right == null) {

current.right = new TreeNode();

current.right.data = value;

} else {

insertNode(value, current.right);

}

public boolean contains(int value) {

if (findNode(value) != null) {

return true;

} else {

return false;

}

private boolean containsRecursion(int value, TreeNode current) {

if (current == null) {

return false;

} else if (current.data == value) {

return true;

} else {

if (value > current.data) {

return containsRecursion(value, current.right);

} else {

return containsRecursion(value, current.left);

}

public TreeNode findNode(int value) {

return findNodeRecursion(value, root);

}

private TreeNode findNodeRecursion(int value, TreeNode current) {

if (current == null) {

return null;

} else if (current.data == value) {

return current;

} else {

if (value > current.data) {

return findNodeRecursion(value, current.right);

} else {

return findNodeRecursion(value, current.left);

}

public TreeNode findParent(int value) {

return findParentRecursion(value, root);

}

private TreeNode findParentRecursion(int value, TreeNode current) {

if (root.data == value) {

return null;

}

if (value < current.data) {

if (current.left == null) {

return null;

} else if (current.left.data == value) {

return current;

} else {

return findParentRecursion(value, current.left);

}

} else {

if (current.right == null) {

return null;

} else if (current.right.data == value) {

return current;

} else {

return findParentRecursion(value, current.right);

}

public boolean remove(int value) {

TreeNode nodeToRemove = findNode(value);

if (nodeToRemove == null) {

return false;

}

TreeNode parent = findParent(value);

if (root.left == null && root.right == null) {

root = null;

} else if (nodeToRemove.left == null && nodeToRemove.right == null) {

if (value < parent.data) {

parent.left = null;

} else {

parent.right = null;

}

} else if (nodeToRemove.left == null) {

if (value < parent.data) {

parent.left = nodeToRemove.right;

} else {

parent.right = nodeToRemove.right;

}

} else if (nodeToRemove.right == null) {

if (value < parent.data) {

parent.left = nodeToRemove.left;

} else {

parent.right = nodeToRemove.left;

}

} else {

TreeNode largestValue = nodeToRemove.left;

while (largestValue.right != null) {

largestValue = largestValue.right;

}

TreeNode parentOfLargest = findParent(largestValue.data);

if (parentOfLargest.left == largestValue) {

if (largestValue.left == null) {

parentOfLargest.left = null;

} else {

parentOfLargest.left = largestValue.left;

}

} else {

parentOfLargest.right = null;

}

nodeToRemove.data = largestValue.data;

}

return true;

}

public TreeNode findMin() {

if (root == null) {

return null;

}

return findMinRecursion(root);

}

private TreeNode findMinRecursion(TreeNode current) {

if (current.left == null) {

return current;

} else {

return findMinRecursion(current.left);

}

public TreeNode findMax() {

if (root == null) {

return null;

}

return findMaxRecursion(root);

}

private TreeNode findMaxRecursion(TreeNode current) {

if (current.right == null) {

return current;

} else {

return findMaxRecursion(current.right);

}

public void traversePreorder() {

traversePreorderHelper(root);

}

private void traversePreorderHelper(TreeNode current) {

if (current != null) {

System.out.println(current.data);

traversePreorderHelper(current.left);

traversePreorderHelper(current.right);

}

public void traversePostorder() {

traversePostorderHelper(root);

}

private void traversePostorderHelper(TreeNode current) {

if (current != null) {

traversePostorderHelper(current.left);

traversePostorderHelper(current.right);

System.out.println(current.data);

}

public void traverseInorder() {

traverseInorderHelper(root);

}

private void traverseInorderHelper(TreeNode current) {

if (current != null) {

traverseInorderHelper(current.left);

System.out.println(current.data);

traverseInorderHelper(current.right);

}

public void traverseBreadth() {

traverseBreadthHelper(root);

}

private void traverseBreadthHelper(TreeNode current) {

ArrayDeque<TreeNode> deq = new ArrayDeque<TreeNode>();

while (current != null) {

System.out.println(current.data);

if (current.left != null) {

deq.add(current.left);

}

if (current.right != null) {

deq.add(current.right);

}

if (!deq.isEmpty()) {

current = deq.remove();

} else {

current = null;

}

public static void main(String[] args) {

BinaryTree bt = new BinaryTree();

bt.insert(42);

bt.insert(13);

bt.insert(666);

bt.insert(10);

bt.insert(11);

bt.insert(7);

bt.insert(9);

bt.insert(4);

System.out.println("1: " + bt.contains(1));

System.out.println("10: " + bt.contains(10));

System.out.println("42: " + bt.contains(42));

System.out.println("13: " + bt.contains(13));

System.out.println("11: " + bt.contains(11));

System.out.println("7: " + bt.contains(7));
/**代码未完, 请加载全部代码(NowJava.com).**/

编辑/阅读全部代码

执行结果：

本文系作者在时代Java发表，未经许可，不得转载。如有侵权，请联系nowjava@qq.com删除。

编辑于 2020-03-26 09:23:272020-03-26 09:23:27

实例源码

实例源码订阅