二叉排序树-java代码实现

理论知识参考：https://blog.csdn.net/dengjili/article/details/111503799

定义节点

public class Node {
	private int value;
	private Node leftNode;
	private Node rightNode;
	// setter getter
}

采用层次遍历输出

public class LevelTraversal {
	public static void traversal(Node node) {
		System.out.println("----------------------");
		Queue<Node> queue = new LinkedBlockingDeque<>();
		queue.add(node);
		
		while (!queue.isEmpty()) {
			Node pollNode = queue.poll();
			System.out.println(pollNode.getValue());
			Node leftNode = pollNode.getLeftNode();
			if (leftNode != null) {
				queue.add(leftNode);
			}
			Node rightNode = pollNode.getRightNode();
			if (rightNode != null) {
				queue.add(rightNode);
			}
		}
	}
}

排序树增删查实现

public class BinarySortTree {

	public static Node insert(Node node, int value) {
		if (node == null) {
			node = new Node(value);
		} else {
			int currentValue = node.getValue();
			if (currentValue > value) {
				Node leftNode = node.getLeftNode();
				leftNode = insert(leftNode, value);
				node.setLeftNode(leftNode);
			} else if (currentValue < value) {
				Node rightNode = node.getRightNode();
				rightNode = insert(rightNode, value);
				node.setRightNode(rightNode);
			} 
			// don't deal with currentValue equals with value
		}
		return node;
	}
	
	public static Node delete(Node root, int value) {
		Node isExistNode = search(root, value);
		if (isExistNode == null) {
			return root;
		}
		
		// 标记待删除节点的父结点，其中若删除的是根节点，则parentNode为空
		Node parentNode = null;
		Node currentNode = root;
		while (currentNode != null && currentNode.getValue() != value) {
			parentNode = currentNode;
			if (currentNode.getValue() > value) {
				currentNode = currentNode.getLeftNode();
			} else {
				currentNode = currentNode.getRightNode();
			}
		}
		
		// 删除，分三种情况处理
		// 1. 叶子节点
		if (currentNode.getLeftNode() == null && currentNode.getRightNode() == null) {
			if (parentNode != null) {
				if (parentNode.getValue() > value) {
					parentNode.setLeftNode(null);
				} else {
					parentNode.setRightNode(null);
				}
			} else {
				root = null;
			}
		}
		
		// 2. 只存在一个子节点
		else if (currentNode.getLeftNode() == null && currentNode.getRightNode() != null) {
			if (parentNode != null) {
				if (parentNode.getValue() > value) {
					parentNode.setLeftNode(currentNode.getRightNode());
				} else {
					parentNode.setRightNode(currentNode.getRightNode());
				}
			} else {
				root = currentNode.getRightNode();
			}
		} 
		else if (currentNode.getLeftNode() != null && currentNode.getRightNode() == null) {
			if (parentNode != null) {
				if (parentNode.getValue() > value) {
					parentNode.setLeftNode(currentNode.getLeftNode());
				} else {
					parentNode.setRightNode(currentNode.getLeftNode());
				}
			} else {
				root = currentNode.getLeftNode();
			}
		}
		// 3. 存在两个子节点（采用替代法-可重用代码：找出被删除节点的右子树，找出最大的结点，替换被删除的结点）
		else if (currentNode.getLeftNode() != null && currentNode.getRightNode() != null) {
			// 3.1  找出右子树最大节点
			Node currentMaxNode = currentNode;
			while (currentMaxNode.getRightNode() != null) {
				currentMaxNode = currentMaxNode.getRightNode();
			}
			// 3.2 删除右子树最大节点
			root = delete(root, currentMaxNode.getValue());
			// 3.3 替换待删除节点
			currentMaxNode.setLeftNode(currentNode.getLeftNode());
			currentMaxNode.setRightNode(currentNode.getRightNode());
			// 3.4 设置父结点子引用
			if (parentNode != null) {
				if (parentNode.getValue() > value) {
					parentNode.setLeftNode(currentMaxNode);
				} else {
					parentNode.setRightNode(currentMaxNode);
				}
			} else {
				root = currentMaxNode;
			}
		}
		
		return root;
	}
	
	public static Node search(Node node, int value) {
		if (node == null) {
			return null;
		}
		int currentValue = node.getValue();
		if (value == currentValue) {
			return node;
		} else if (currentValue > value) {
			Node leftNode = node.getLeftNode();
			return search(leftNode, value);
		} else {
			Node rightNode = node.getRightNode();
			return search(rightNode, value);
		}
	}
	
	public static Node search2(Node node, int value) {
		Node currentNode = node;
		while (currentNode != null) {
			int currentValue = currentNode.getValue();
			if (value == currentValue) {
				return currentNode;
			} else if (currentValue > value) {
				currentNode = currentNode.getLeftNode();
			} else {
				currentNode = currentNode.getRightNode();
			}
		}
		return null;
	}
	
	public static Node createBST(int[] nums) {
		Node root = null;
		for (int value : nums) {
			root = insert(root, value);
		}
		return root;
	}
	
}

测试类

public class BinarySortTreeTest {

	public static void main(String[] args) {
		int nums[] = { 4, 1, 2, 5, 0, 7, 9, 8, 3, 6 };
		Node tree = BinarySortTree.createBST(nums);
		LevelTraversal.traversal(tree);
		tree = BinarySortTree.delete(tree, 5);
		LevelTraversal.traversal(tree);
		
		Node node = BinarySortTree.search2(tree, 8);
		System.out.println();
		System.out.println(node.getValue());
	}

}

输出结果

----------------------
4
1
5
0
2
7
3
6
9
8
----------------------
4
1
7
0
2
6
9
3
8

8

操作过程二叉排序树

创建成功后的二叉树

                 4
			   /	\ 
			1          5
		   /   \          \ 
		 0   	2           7
		 		  \        /  \
					3	  6    9
					          /
					         8
删除节点5后的二叉树				 
							 
                 4
			   /	\ 
			1          7
		   /   \      /   \ 
		 0   	2    6      9
		 		  \        /  
					3	  8   
					
					
							 
							

本文地址：https://blog.csdn.net/dengjili/article/details/111992147