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

爱被打了一巴掌 2022-11-08 14:21 147阅读 0赞

/\*\*来自 时代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) \{

ArrayDequedeq = new ArrayDeque();

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_Java 二叉搜索树的一个简单实现（不平衡）。

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 AVL树平衡二叉搜索树详解--实现插入

相关二叉搜索树、平衡二叉树

相关 LeetCode_二叉搜索树_简单_700.二叉搜索树中的搜索

相关二叉搜索树的实现

相关平衡二叉搜索树的创建

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

相关 [标程]: 二叉搜索树和平衡二叉搜索树

相关平衡二叉搜索树的实现原理

相关 python实现二叉搜索树

相关二叉搜索树实现