1、二叉排序树性质
二叉排序树也是一棵二叉树，所谓二叉树，就是“任何节点最多只允许两个子节点”，这两个子节点称为左右子节点。如下便是一个二叉树。
- 1、若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 2、若它的右子树不空，则右子树上所有节点的值均大于其根节点的值。
- 3、换句话说就是：任何节点的键值一定大于其左子树中的每一个节点的键值，并小于其右子树中的每一个节点的键值。
如下便是一颗二叉排序树：
2、二叉树排序的基本原理
使用第一个元素作为根节点，如果之后的元素比第一个小，则放到左子树，否则放到右子树，之后按中序遍历。
二叉树的遍历方式有三种， 前序、中序、后序 。
前序（先序）遍历顺序: 根节点、左子树、右子树
中序遍历顺序：左子树、根节点、右子树
后序遍历顺序：左子树、右子树、根节点
3、二叉树节点定义
public class TreeNode {
// 左节点
private TreeNode lefTreeNode;
// 右节点
private TreeNode rightNode;
// 数据
private int value;
private boolean isDelete;
public TreeNode getLefTreeNode() {
return lefTreeNode;
}
public void setLefTreeNode(TreeNode lefTreeNode) {
this.lefTreeNode = lefTreeNode;
}
public TreeNode getRightNode() {
return rightNode;
}
public void setRightNode(TreeNode rightNode) {
this.rightNode = rightNode;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public boolean isDelete() {
return isDelete;
}
public void setDelete(boolean isDelete) {
this.isDelete = isDelete;
}
public TreeNode() {
super();
}
public TreeNode(int value) {
this(null, null, value, false);
}
public TreeNode(TreeNode lefTreeNode, TreeNode rightNode, int value, boolean isDelete) {
super();
this.lefTreeNode = lefTreeNode;
this.rightNode = rightNode;
this.value = value;
this.isDelete = isDelete;
}
@Override
public String toString() {
return "TreeNode [lefTreeNode=" + lefTreeNode + ", rightNode=" + rightNode + ", value=" + value + ", isDelete="
+ isDelete + "]";
}
public void display() {
System.out.print(this.value + "\t");
}
}
4、二叉树定义
public class BinaryTree {
// 根节点
private TreeNode root;
public TreeNode getRoot() {
return root;
}
/**
* 插入操作
*
* @param value
*/
public void insert(int value) {
TreeNode newNode = new TreeNode(value);
if (root == null) {
root = newNode;
root.setLefTreeNode(null);
root.setRightNode(null);
} else {
TreeNode currentNode = root;
TreeNode parentNode;
while (true) {
parentNode = currentNode;
// 往右放
if (newNode.getValue() > currentNode.getValue()) {
currentNode = currentNode.getRightNode();
if (currentNode == null) {
parentNode.setRightNode(newNode);
return;
}
} else {
// 往左放
currentNode = currentNode.getLefTreeNode();
if (currentNode == null) {
parentNode.setLefTreeNode(newNode);
return;
}
}
}
}
}
/**
* 查找
*
* @param key
* @return
*/
public TreeNode find(int key) {
TreeNode currentNode = root;
if (currentNode != null) {
while (currentNode.getValue() != key) {
if (currentNode.getValue() > key) {
currentNode = currentNode.getLefTreeNode();
} else {
currentNode = currentNode.getRightNode();
}
if (currentNode == null) {
return null;
}
}
if (currentNode.isDelete()) {
System.out.println(key + "已被假删除");
return null;
} else {
System.out.println(key + "已被找到");
return currentNode;
}
} else {
System.out.println(key + "未被找到");
return null;
}
}
/**
* //中序遍历(递归)： 1、调用自身来遍历节点的左子树 2、访问这个节点 3、调用自身来遍历节点的右子树 先序（前序）: 根节点、左子树、右子树
* 中序：左子树、根节点、右子树 后序：左子树、右子树、根节点
*/
public void inOrderTraverse() {
System.out.print("中序遍历:");
inOrder(root);
System.out.println();
}
/**
* 中序遍历(递归)： 1、调用自身来遍历节点的左子树 2、访问这个节点 3、调用自身来遍历节点的右子树 先序（前序）: 根节点、左子树、右子树
* 中序：左子树、根节点、右子树 后序：左子树、右子树、根节点
*
* @param treeNode
*/
public void inOrder(TreeNode treeNode) {
if (treeNode != null && treeNode.isDelete() == false) {
inOrder(treeNode.getLefTreeNode());
treeNode.display();
inOrder(treeNode.getRightNode());
}
}
/**
* 中序非递归遍历： 1）对于任意节点current，若该节点不为空则将该节点压栈，并将左子树节点置为current，重复此操作，直到current为空。
* 2）若左子树为空，栈顶节点出栈，访问节点后将该节点的右子树置为current 3) 重复1、2步操作，直到current为空且栈内节点为空。
* 先序（前序）: 根节点、左子树、右子树 中序：左子树、根节点、右子树 后序：左子树、右子树、根节点
*/
public void inOrderByStack() {
System.out.print("中序非递归遍历:");
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.getLefTreeNode();
}
if (!stack.isEmpty()) {
current = stack.pop();
current.display();
current = current.getRightNode();
}
}
System.out.println();
}
/**
* //前序遍历(递归)： 1、访问这个节点 2、调用自身来遍历节点的左子树 3、调用自身来遍历节点的右子树 先序（前序）: 根节点、左子树、右子树
* 中序：左子树、根节点、右子树 后序：左子树、右子树、根节点
*/
public void preOrderTraverse() {
System.out.print("前序遍历:");
preOrderTraverse(root);
System.out.println();
}
private void preOrderTraverse(TreeNode node) {
if (node == null)
return;
node.display();
preOrderTraverse(node.getLefTreeNode());
preOrderTraverse(node.getRightNode());
}
/**
* 前序非递归遍历：
* 1）对于任意节点current，若该节点不为空则访问该节点后再将节点压栈，并将左子树节点置为current，重复此操作，直到current为空。
* 2）若左子树为空，栈顶节点出栈，将该节点的右子树置为current 3) 重复1、2步操作，直到current为空且栈内节点为空。 先序（前序）:
* 根节点、左子树、右子树 中序：左子树、根节点、右子树 后序：左子树、右子树、根节点
*/
public void preOrderByStack() {
System.out.print("前序非递归遍历:");
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current.display();
current = current.getLefTreeNode();
}
if (!stack.isEmpty()) {
current = stack.pop();
current = current.getRightNode();
}
}
System.out.println();
}
/**
* //后序遍历(递归)： 1、调用自身来遍历节点的左子树 2、调用自身来遍历节点的右子树 3、访问这个节点 先序（前序）: 根节点、左子树、右子树
* 中序：左子树、根节点、右子树 后序：左子树、右子树、根节点
*/
public void postOrderTraverse() {
System.out.print("后序遍历:");
postOrderTraverse(root);
System.out.println();
}
private void postOrderTraverse(TreeNode node) {
if (node == null)
return;
postOrderTraverse(node.getLefTreeNode());
postOrderTraverse(node.getRightNode());
node.display();
}
public int getMinValue() {
TreeNode current = root;
while (true) {
if (current.getLefTreeNode() == null)
return current.getValue();
current = current.getLefTreeNode();
}
}
public int getMaxValue() {
TreeNode current = root;
while (true) {
if (current.getRightNode() == null)
return current.getValue();
current = current.getRightNode();
}
}
/**
*
* 得到后继节点，即删除节点的左后代
*/
private TreeNode getSuccessor(TreeNode delNode) {
TreeNode successor = delNode;
TreeNode successorParent = null;
TreeNode current = delNode.getRightNode();
while (current != null) {
successorParent = successor;
successor = current;
current = current.getLefTreeNode();
}
// 如果后继节点不是删除节点的右子节点时，
if (successor != delNode.getRightNode()) {
// 要将后继节点的右子节点指向后继结点父节点的左子节点，
successorParent.setLefTreeNode(successor.getRightNode());
// 并将删除节点的右子节点指向后继结点的右子节点
successor.setRightNode(delNode.getRightNode());
}
// 任何情况下，都需要将删除节点的左子节点指向后继节点的左子节点
successor.setLefTreeNode(delNode.getLefTreeNode());
return successor;
}
/**
* 删除节点
* @param value
* @return
*/
public boolean delete(int value) {
System.out.println("删除节点: "+value);
TreeNode current = root; // 需要删除的节点
TreeNode parent = null; // 需要删除的节点的父节点
boolean isLeftChild = true; // 需要删除的节点是否父节点的左子树
while (true) {
if (value == current.getValue()) {
break;
} else if (value < current.getValue()) {
isLeftChild = true;
parent = current;
current = current.getLefTreeNode();
} else {
isLeftChild = false;
parent = current;
current = current.getRightNode();
}
// 找不到需要删除的节点，直接返回
if (current == null)
return false;
}
// 分情况考虑
// 1、需要删除的节点为叶子节点
if (current.getLefTreeNode() == null && current.getRightNode() == null) {
// 如果该叶节点为根节点，将根节点置为null
if (current == root) {
root = null;
} else {
// 如果该叶节点是父节点的左子节点，将父节点的左子节点置为null
if (isLeftChild) {
parent.setLefTreeNode(null);
} else { // 如果该叶节点是父节点的右子节点，将父节点的右子节点置为null
parent.setRightNode(null);
}
}
}
// 2.1、需要删除的节点有一个子节点，且该子节点为左子节点
else if (current.getRightNode() == null) {
// 如果该节点为根节点，将根节点的左子节点变为根节点
if (current == root) {
root = current.getLefTreeNode();
} else {
// 如果该节点是父节点的左子节点，将该节点的左子节点变为父节点的左子节点
if (isLeftChild) {
parent.setLefTreeNode(current.getLefTreeNode());
} else { // 如果该节点是父节点的右子节点，将该节点的左子节点变为父节点的右子节点
parent.setRightNode(current.getLefTreeNode());
}
}
}
// 2.2、需要删除的节点有一个子节点，且该子节点为右子节点
else if (current.getLefTreeNode() == null) {
// 如果该节点为根节点，将根节点的右子节点变为根节点
if (current == root) {
root = current.getRightNode();
} else {
// 如果该节点是父节点的左子节点，将该节点的右子节点变为父节点的左子节点
if (isLeftChild) {
parent.setLefTreeNode(current.getRightNode());
} else { // 如果该节点是父节点的右子节点，将该节点的右子节点变为父节点的右子节点
parent.setRightNode(current.getRightNode());
}
}
}
// 3、需要删除的节点有两个子节点，需要寻找该节点的后续节点替代删除节点
else {
TreeNode successor = getSuccessor(current);
// 如果该节点为根节点，将后继节点变为根节点，并将根节点的左子节点变为后继节点的左子节点
if (current == root) {
root = successor;
} else {
// 如果该节点是父节点的左子节点，将该节点的后继节点变为父节点的左子节点
if (isLeftChild) {
parent.setLefTreeNode(successor);
} else { // 如果该节点是父节点的右子节点，将该节点的后继节点变为父节点的右子节点
parent.setRightNode(successor);
}
}
}
current = null;
return true;
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
// 添加数据测试
tree.insert(30);
tree.insert(50);
tree.insert(10);
tree.insert(40);
tree.insert(20);
tree.insert(3);
tree.insert(49);
tree.insert(13);
System.out.println("root = " + tree.getRoot().getValue());
// 排序测试
tree.inOrderTraverse();
tree.preOrderTraverse();
tree.postOrderTraverse();
// 查找测试
tree.find(10);
// 删除测试
// tree.find(40).setDelete(true);
tree.find(40);
System.out.println("最小值：" + tree.getMinValue() + "，最大值：" + tree.getMaxValue());
tree.inOrderTraverse();
tree.delete(3); // 删除叶子节点
tree.inOrderTraverse();
tree.preOrderTraverse();
tree.postOrderTraverse();
tree.delete(50); // 删除只有一个左子节点的节点
// tree.delete(248); // 删除只有一个右子节点的节点
// tree.delete(248); // 删除只有一个右子节点的节点
// tree.delete(580); // 删除有两个子节点的节点，且后继节点为删除节点的右子节点的左后代
// tree.delete(888); // 删除有两个子节点的节点，且后继节点为删除节点的右子节点
// tree.delete(52); // 删除有两个子节点的节点，且删除节点为根节点
tree.inOrderTraverse();
tree.preOrderTraverse();
tree.postOrderTraverse();
}
}
// root = 30
// 中序遍历:3 10 13 20 30 40 49 50
// 前序遍历:30 10 3 20 13 50 40 49
// 后序遍历:3 13 20 10 49 40 50 30
// 10已被找到
// 40已被找到
// 最小值：3，最大值：50
// 中序遍历:3 10 13 20 30 40 49 50
// 删除节点: 3
// 中序遍历:10 13 20 30 40 49 50
// 前序遍历:30 10 20 13 50 40 49
// 后序遍历:13 20 10 49 40 50 30
// 删除节点: 50
// 中序遍历:10 13 20 30 40 49
// 前序遍历:30 10 20 13 40 49
// 后序遍历:13 20 10 49 40 30
5、二叉排序树的查找
5.1 二叉排序树查找最大最小值
要在二叉树中找出查找最大最小元素是极简单的事情，从根节点一直往左走，直到无路可走就可得到最小值；从根节点一直往右走，直到无路可走，就可以得到最大值。
// 查找最小值
public int getMinValue() {
TreeNode current = root;
while (true) {
if (current.getLefTreeNode() == null)
return current.getValue();
current = current.getLefTreeNode();
}
}
// 查找最大值
public int getMaxValue() {
TreeNode current = root;
while (true) {
if (current.getRightNode() == null)
return current.getValue();
current = current.getRightNode();
}
}
5.2 二叉排序树查找单个元素
// 二叉排序树查找单个元素
public TreeNode find(int key) {
TreeNode currentNode = root;
if (currentNode != null) {
while (currentNode.getValue() != key) {
if (currentNode.getValue() > key) {
currentNode = currentNode.getLefTreeNode();
} else {
currentNode = currentNode.getRightNode();
}
if (currentNode == null) {
return null;
}
}
if (currentNode.isDelete()) {
return null;
} else {
return currentNode;
}
} else {
return null;
}
}
6、二叉排序树插入
插入新元素时，可以从根节点开始，遇键值较大者就向左，遇键值较小者就向右，一直到末端，就是插入点。
// 二叉排序树插入新数据
public void insert(int value) {
TreeNode newNode = new TreeNode(value);
if (root == null) {
root = newNode;
root.setLefTreeNode(null);
root.setRightNode(null);
} else {
TreeNode currentNode = root;
TreeNode parentNode;
while (true) {
parentNode = currentNode;
// 往右放
if (newNode.getValue() > currentNode.getValue()) {
currentNode = currentNode.getRightNode();
if (currentNode == null) {
parentNode.setRightNode(newNode);
return;
}
} else {
// 往左放
currentNode = currentNode.getLefTreeNode();
if (currentNode == null) {
parentNode.setLefTreeNode(newNode);
return;
}
}
}
}
}
7、二叉排序树删除
对于二叉排序树中的节点A，对它的删除分为两种情况：
- 1）删除节点A为叶子节点，即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构，则可以直接删除此子结点。
- 2）删除节点A只有一个子节点：只有一个左子节点或只有一个右子节点，就直接将A的子节点连至A的父节点上，并将A删除；
- 3）删除节点有两个子节点：这种情况比较复杂，需要寻找后继节点，即比要删除的节点的关键值次高的节点是它的后继节点。说得简单一些，后继节点就是比要删除的节点的关键值要大的节点集合中的最小值。（右子节点的左后代）
/**
* 得到后继节点，即删除节点的左后代
*/
private TreeNode getSuccessor(TreeNode delNode) {
TreeNode successor = delNode;
TreeNode successorParent = null;
TreeNode current = delNode.getRightNode();
while (current != null) {
successorParent = successor;
successor = current;
current = current.getLefTreeNode();
}
// 如果后继节点不是删除节点的右子节点时，
if (successor != delNode.getRightNode()) {
// 要将后继节点的右子节点指向后继结点父节点的左子节点，
successorParent.setLefTreeNode(successor.getRightNode());
// 并将删除节点的右子节点指向后继结点的右子节点
successor.setRightNode(delNode.getRightNode());
}
// 任何情况下，都需要将删除节点的左子节点指向后继节点的左子节点
successor.setLefTreeNode(delNode.getLefTreeNode());
return successor;
}
- a)如果后继节点是刚好是要删除节点的右子节点
- b)如果后继节点为要删除节点的右子节点的左后代：
删除节点代码
public boolean delete(int value) {
System.out.println("删除节点: "+value);
TreeNode current = root; // 需要删除的节点
TreeNode parent = null; // 需要删除的节点的父节点
boolean isLeftChild = true; // 需要删除的节点是否父节点的左子树
while (true) {
if (value == current.getValue()) {
break;
} else if (value < current.getValue()) {
isLeftChild = true;
parent = current;
current = current.getLefTreeNode();
} else {
isLeftChild = false;
parent = current;
current = current.getRightNode();
}
// 找不到需要删除的节点，直接返回
if (current == null)
return false;
}
// 分情况考虑
// 1、需要删除的节点为叶子节点
if (current.getLefTreeNode() == null && current.getRightNode() == null) {
// 如果该叶节点为根节点，将根节点置为null
if (current == root) {
root = null;
} else {
// 如果该叶节点是父节点的左子节点，将父节点的左子节点置为null
if (isLeftChild) {
parent.setLefTreeNode(null);
} else { // 如果该叶节点是父节点的右子节点，将父节点的右子节点置为null
parent.setRightNode(null);
}
}
}
// 2.1、需要删除的节点有一个子节点，且该子节点为左子节点
else if (current.getRightNode() == null) {
// 如果该节点为根节点，将根节点的左子节点变为根节点
if (current == root) {
root = current.getLefTreeNode();
} else {
// 如果该节点是父节点的左子节点，将该节点的左子节点变为父节点的左子节点
if (isLeftChild) {
parent.setLefTreeNode(current.getLefTreeNode());
} else { // 如果该节点是父节点的右子节点，将该节点的左子节点变为父节点的右子节点
parent.setRightNode(current.getLefTreeNode());
}
}
}
// 2.2、需要删除的节点有一个子节点，且该子节点为右子节点
else if (current.getLefTreeNode() == null) {
// 如果该节点为根节点，将根节点的右子节点变为根节点
if (current == root) {
root = current.getRightNode();
} else {
// 如果该节点是父节点的左子节点，将该节点的右子节点变为父节点的左子节点
if (isLeftChild) {
parent.setLefTreeNode(current.getRightNode());
} else { // 如果该节点是父节点的右子节点，将该节点的右子节点变为父节点的右子节点
parent.setRightNode(current.getRightNode());
}
}
}
// 3、需要删除的节点有两个子节点，需要寻找该节点的后续节点替代删除节点
else {
TreeNode successor = getSuccessor(current);
// 如果该节点为根节点，将后继节点变为根节点，并将根节点的左子节点变为后继节点的左子节点
if (current == root) {
root = successor;
} else {
// 如果该节点是父节点的左子节点，将该节点的后继节点变为父节点的左子节点
if (isLeftChild) {
parent.setLefTreeNode(successor);
} else { // 如果该节点是父节点的右子节点，将该节点的后继节点变为父节点的右子节点
parent.setRightNode(successor);
}
}
}
current = null;
return true;
}
8、二叉排序树遍历
二叉排序树遍历分为：先序（前序）、中序、后序。
- 前序遍历顺序为：根节点、左子树、右子树;
- 中序遍历顺序为：左子树、根节点、右子树;
- 后序遍历顺序为：左子树、右子树、根节点。其中中序遍历为升序排列。
8.1 中序遍历代码
/**
* 中序遍历(递归)：
* 1、调用自身来遍历节点的左子树 2、访问这个节点 3、调用自身来遍历节点的右子树
*/
public void inOrderTraverse() {
System.out.print("中序遍历:");
inOrder(root);
System.out.println();
}
/**
* 中序遍历(递归)：
* 1、调用自身来遍历节点的左子树 2、访问这个节点 3、调用自身来遍历节点的右子树
*
* @param treeNode
*/
public void inOrder(TreeNode treeNode) {
if (treeNode != null && treeNode.isDelete() == false) {
inOrder(treeNode.getLefTreeNode());
treeNode.display();
inOrder(treeNode.getRightNode());
}
}
/**
* 中序非递归遍历：
* 1）对于任意节点current，若该节点不为空则将该节点压栈，并将左子树节点置为current，重复此操作，直到current为空。
* 2）若左子树为空，栈顶节点出栈，访问节点后将该节点的右子树置为current 3) 重复1、2步操作，直到current为空且栈内节点为空。
*/
public void inOrderByStack() {
System.out.print("中序非递归遍历:");
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.getLefTreeNode();
}
if (!stack.isEmpty()) {
current = stack.pop();
current.display();
current = current.getRightNode();
}
}
System.out.println();
}
8.2 前序遍历代码
/**
* 前序遍历(递归)：
* 1、访问这个节点 2、调用自身来遍历节点的左子树 3、调用自身来遍历节点的右子树
*/
public void preOrderTraverse() {
System.out.print("前序遍历:");
preOrderTraverse(root);
System.out.println();
}
private void preOrderTraverse(TreeNode node) {
if (node == null)
return;
node.display();
preOrderTraverse(node.getLefTreeNode());
preOrderTraverse(node.getRightNode());
}
/**
* 前序非递归遍历：
* 1）对于任意节点current，若该节点不为空则访问该节点后再将节点压栈，并将左子树节点置为current，重复此操作，直到current为空。
* 2）若左子树为空，栈顶节点出栈，将该节点的右子树置为current 3) 重复1、2步操作，直到current为空且栈内节点为空。
*/
public void preOrderByStack() {
System.out.print("前序非递归遍历:");
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current.display();
current = current.getLefTreeNode();
}
if (!stack.isEmpty()) {
current = stack.pop();
current = current.getRightNode();
}
}
System.out.println();
}
8.3 后续遍历代码
/**
* 后序遍历(递归)：
* 1、调用自身来遍历节点的左子树 2、调用自身来遍历节点的右子树 3、访问这个节点
*/
public void postOrderTraverse() {
System.out.print("后序遍历:");
postOrderTraverse(root);
System.out.println();
}
private void postOrderTraverse(TreeNode node) {
if (node == null)
return;
postOrderTraverse(node.getLefTreeNode());
postOrderTraverse(node.getRightNode());
node.display();
}
评论区