一、定义
- 查找二叉树又叫二叉排序树，如果同时满足以下性质：
- 左右子树都是
二叉树；
- 如果
左子树不为空，那么左子树上面的所有节点的关键字都比根节点的关键字小；
- 如果
右子树不为空，那么右子树上面的所有节点的关键字都比跟节点的关键字大；
- 好处：方便查找，可以提高查找效率，查找二叉树越平衡，查找的效率的越稳定，效率越高，这种树就是
平衡二叉树；
二、代码实现
public class SearchBinaryTree {
private TreeNode root;//跟节点
/**
* 创建查找二叉树，如果关键字比根节点的关键字大，就往右边插入，
* 如果关键字比根节点小，就往左边插入
* @param data 带插入的数据
* @return
*/
public TreeNode put(int data) {
TreeNode node = null;
TreeNode parent = null;
//首先判断根节点，如果根节点为空，则新创建的节点为根节点
if (root == null) {
node = new TreeNode(0, data);
root = node;
return node;
} else {
//如果不是根节点，就需要不停地遍历已有的节点，找到满足条件的节点的位置，然后插入节点
//和根节点进行比较，首先要拿到根节点
node = root;
while (node != null) {
//把当前结点制定为父节点，然后比较左右孩子和当前节点的大小
parent = node;
//如果要插入的数据比当前结点要大，就需要往右子树上找
if (data > node.data) {
node = node.rightChild;
} else if (data < node.data) {
node = node.leftChild;
} else {
return node;
}
}
//while循环结束，就表示找到了要插入的地方，
// 接下来就是创建节点，然后把这个节点挂在指定的位置
//角标默认是0
node = new TreeNode(0, data);
//节点创建完毕，需要判断放在父节点的左边还是右边
if (data < parent.data) {
parent.leftChild = node;
} else {
parent.rightChild = node;
}
//指定这个节点的父节点
node.parent = parent;
return node;
}
}
/**
* 删除二叉查找树中的某个节点，
* <strong>因为是二叉查找树，所以是删除某个节点后，需要对剩下的节点进行
* 重新排序，使之依然是二叉查找树
* </strong>
* @param data
*/
public void deleteNode(int data) {
//要想删除某个节点，必须先找到这个节点
TreeNode node = searchNode(data);
//如果node为空，表示没有找到
if (node == null) {
throw new NoSuchElementException("没有指定的节点");
} else {
delete(node);
}
}
/**
* 删除节点
* @param node 要删除的节点
*/
private void delete(TreeNode node) {
if (node == null) {
throw new NoSuchElementException("没有这个节点");
} else {
//如果当前节点不为空，就需要判断这个节点的父节点，左右孩子节点是否为空
TreeNode parent = node.parent;
//如果 当前节点为叶子节点，直接删除
if (node.leftChild == null && node.rightChild == null) {
//需要判断是父亲的左儿子还是右儿子
if (parent.leftChild == node) {
parent.leftChild = null;
node.parent = null;
} else {
parent.rightChild = null;
node.parent = null;
}
} else if (node.leftChild != null && node.rightChild == null) {
//如果被删除的节点有左孩子没有右孩子
//这是还需要判断这个节点是在父节点的左子树上，还是在右子树上
//如果这个节点在左子树上，就需要把这个节点的左孩子放在parent的左子树上
if (parent.leftChild == node) {
parent.leftChild = node.leftChild;
} else {
parent.rightChild = node.leftChild;
}
} else if (node.leftChild == null && node.rightChild != null) {
//如果被删除的节点有右孩子而没有左孩子
if (parent.leftChild == node) {
parent.leftChild = node.rightChild;
} else {
parent.rightChild = node.rightChild;
}
} else if (node.leftChild != null && node.rightChild != null) {
//如果被删除的节点既有左孩子又有右孩子
//找后继节点
TreeNode next = getNextNode(node);
delete(next);
node.data = next.data;
}
}
}
/**
* 找到某个节点的后继节点
* @param node
* @return
*/
private TreeNode getNextNode(TreeNode node) {
if (node == null) {
return null;
} else {
//如果这个节点的右子树不为空，就在右子树里面找到key最小的节点
if (node.rightChild != null) {
return getMinTreeNode(node);
} else {
TreeNode parent = node.parent;
while (parent == null && node == parent.rightChild) {
node = parent;
parent = parent.parent;
}
return parent;
}
}
}
/**
* 找到这个节点的子树下面key最小的节点,最小的节点一定在该节点的左子树上的最末端
* @param node
* @return
*/
private TreeNode getMinTreeNode(TreeNode node) {
if (node == null) {
return null;
} else {
while (node.leftChild != null) {
node = node.leftChild;
}
}
return node;
}
private TreeNode searchNode(int data) {
TreeNode node;
//先从根节点开始找
node = root;
if (node == null) {
return null;
} else {
while (node != null && data != node.data) {
if (data > node.data) {
node = node.rightChild;
} else if (data < node.data) {
node = node.leftChild;
} else {
return node;
}
}
//当while循环结束后，就表示已经遍历完了整个二叉查找树，
// 有可能找到，有可能找不到，即node有可能为null
return node;
}
}
/**
* 中序遍历二叉查找树，如果树构建的正确，中序遍历出来应该是升序的
* @param node
*/
public void midOrderTraverse(TreeNode node) {
midOrderTraverse(node.leftChild);
System.out.print(node.data + " ");
midOrderTraverse(node.rightChild);
}
private static final class TreeNode {
private int key;//二叉查找树的关键字，通过这个关键字对节点进行排序
private TreeNode leftChild;
private TreeNode rightChild;
private TreeNode parent;
private int data;
public TreeNode(int key, int data) {
this.key = key;
this.data = data;
this.leftChild = null;
this.rightChild = null;
this.parent = null;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
public TreeNode getLeftChild() {
return leftChild;
}
public void setLeftChild(TreeNode leftChild) {
this.leftChild = leftChild;
}
public TreeNode getRightChild() {
return rightChild;
}
public void setRightChild(TreeNode rightChild) {
this.rightChild = rightChild;
}
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
}
}
