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();
}
评论区