简介
二叉查找树（Binary Search Tree），又被成为二叉搜索树。
它是特殊的二叉树：对于二叉树，假设x为二叉树中的任意一个节点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个节点，则key[y]<key[x];如果y是x的右子树的一个节点，则key[y]>key[x]。那么，这棵树就是二叉查找树。如图
image.png
在二叉查找树中：
- 若任意节点的左子树不空，则左子树上所有节点的值均小于他的根节点的值；
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 任意节点的左、右子树也分别为二叉查找树；
- 没有键值相等的节点。
遍历
这里讲解前序遍历、中序遍历和后续遍历3中方式。
- 前序遍历
若二叉树非空，则执行以下操作：
- 访问根节点
- 先序遍历左子树
- 先序遍历右子树
- 中序遍历
若二叉树非空，则执行以下操作：
- 中序遍历左子树
- 访问根节点
- 中序遍历右子树
- 后序遍历
若二叉树非空，则执行以下操作：
- 后序遍历左子树
- 后序遍历右子树
- 访问根节点
public class Node {
public int key;
public int value;
public Node leftChild;
public Node rightChild;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
public class Tree {
private Node root; //保存树的根
/**
* 查找指定节点
*/
public Node find(int key) {
Node currentNode = root;
while (null != currentNode && currentNode.key != key) {
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
} else {
currentNode = currentNode.rigthChild;
}
}
return currentNode;
}
/**
* 插入节点
*/
public void insert(int key, int value) {
if (null == root) {
root = new Node(key, value);
return;
}
Node currentNode = root;
Node parentNode = root;
boolean isLeftChild = true;
while (currentNode != null) {
parentNode = currentNode;
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
isLeftChild = true;
} else {
currentNode = currentNode.rigthChild;
isLeftChild = false;
}
}
Node newNode = new Node(key, value);
if (isLeftChild) {
parentNode.leftChild = newNode;
} else {
parentNode.rigthChild = newNode;
}
}
/**
* 删除指定节点
*/
public boolean delete(int key) {
Node currentNode = root;
Node parentNode = root;
boolean isLeftChild = true;
while (null != currentNode && currentNode.key != key) {
parentNode = currentNode;
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
isLeftChild = true;
} else {
currentNode = currentNode.rigthChild;
isLeftChild = false;
}
}
if (currentNode == null) {
return false;
}
if (currentNode.leftChild == null && currentNode.rigthChild == null) {
if (currentNode == root) { //要删除的节点为叶子节点
root = null;
} else if (isLeftChild) {
parentNode.leftChild = null;
} else {
parentNode.rigthChild = null;
}
} else if (currentNode.rigthChild == null) { //要删除的节点只有左孩子
if (currentNode == root) {
root = currentNode.leftChild;
} else if (isLeftChild) {
parentNode.leftChild = currentNode.leftChild;
} else {
parentNode.rigthChild = currentNode.leftChild;
}
} else if (currentNode.leftChild == null) {
if (currentNode == root) {
root = currentNode.rigthChild;
} else if (isLeftChild) {
parentNode.leftChild = currentNode.rigthChild;
} else {
parentNode.rigthChild = currentNode.leftChild;
}
} else {
//要删除的节点既有左孩子又有有孩子
//思路:用待删除节点右子树中的key值最小的节点的值来替代要删除的节点的值,然后删除右子树中key值最小的节点
//右子树key最小的节点一定不含左子树,所以删除这个key最小的节点一定是属于叶子节点或者只有右子树的节点
Node directPostNode = getDirectPostNode(currentNode);
currentNode.key = directPostNode.key;
currentNode.value = directPostNode.value;
}
return true;
}
/**
* 得到待删除节点的直接后继节点
*/
private Node getDirectPostNode(Node delNode) {
Node parentNode = delNode;//用来保存待删除节点的直接后继节点的父亲节点
Node directPostNode = delNode; //用来保存待删除节点的直接后继节点
Node currentNode = delNode.rigthChild;
while (currentNode != null) {
parentNode = directPostNode;
directPostNode = currentNode;
currentNode = currentNode.leftChild;
}
if (directPostNode != delNode.rigthChild) { //从树中删除此直接后继节点
parentNode.leftChild = directPostNode.rigthChild;
directPostNode.rigthChild = null;
}
return directPostNode;
}
/**
* 先序遍历树
*/
public void preOrder(Node rootNode) {
if (null != rootNode) {
System.out.println(rootNode.key + " " + rootNode.value);
preOrder(rootNode.leftChild);
preOrder(rootNode.rigthChild);
}
}
/**
* 中序遍历树
*/
public void inOrder(Node rootNode) {
if (null != rootNode) {
inOrder(rootNode.leftChild);
System.out.println(rootNode.key + " " + rootNode.value);
inOrder(rootNode.rigthChild);
}
}
/**
* 后序遍历树
*/
public void postOrder(Node rootNode) {
if (null != rootNode) {
postOrder(rootNode.leftChild);
postOrder(rootNode.rigthChild);
System.out.println(rootNode.key + " " + rootNode.value);
}
}
}
