查找二叉树
随着大数据时代的来临，树形结构得到了越来越广泛的应用，废话不多说，直接开始我们的正题，查找二叉树。
何为查找二叉树
查找二叉树是二叉树的一种，又名查找树，搜索树。查找二叉树具有如下特点;
1.必须是二叉树
2.任意节点的左子树上所有的数据都比该节点数据小，或者为空树
3.任意节点的右子树上所有的数据都比该节点数据大，或者为空树
应用场景
顾名思义，查找二叉树的作用就是快速查找 ，使用于数据量特别大时候的快速查找，时间复杂度介于O(log2n)到O(n)之间，数据量越大，越接近于O(log2n)，性能越优，大数据时代的必备技能之一。
代码实现
一.使用孩子双亲表示法表示树
public class Node <T extends Comparable>{
T item;
Node<T> leftChild;
Node<T> rightChild;
Node<T> parent;
public Node(T item) {
this.item = item;
}
}
二.定义属性变量
Node root;
int size;
三.实现必要的增删查询和遍历方法
add 方法实现
public boolean add(T item) {
Node<T> newNode = new Node<T>(item);
if (root == null) {
//如果是空树
root = newNode;
size++;
return true;
}
Node node = root;
Node parent = null;
while (node != null) {
parent = node;
if (node.item.compareTo(item) == 0) {
//去掉重复的，不进行添加操作
return false;
} else if (node.item .compareTo(item) >0) {
//如果加入的节点比做节点小
node = node.leftChild;
} else {
//如果加入的节点比做节点大
node = node.rightChild;
}
}
if (parent.item .compareTo(item)>0) {
parent.leftChild = newNode;
} else {
parent.rightChild = newNode;
}
newNode.parent = parent;
size++;
return true;
}
get方法实现
public Node get(T item) {
if (root == null) {
return null;
}
Node node = root;
while (node != null) {
if (node.item.compareTo(item)<0) {
node = node.rightChild;
} else if (node.item.compareTo(item)>0) {
node = node.leftChild;
} else {
return node;
}
}
return null;
}
遍历
/**
* 采取中序遍历的方式对树进行遍历
*/
public void midOrderTraseval(){
midOrderTraseval(root);
}
private void midOrderTraseval(Node<T> node) {
if (node == null) {
return;
}
midOrderTraseval(node.leftChild);
System.out.print(node.item +" ");
midOrderTraseval(node.rightChild);
}
delete方法（难点）
思路：
1.如果删除的节点左右子树都为空，即叶子节点时：
Node<T> left = node.leftChild;
Node<T> right = node.rightChild;
Node<T> parent = node.parent;
//第一种情况 node 为叶子节点
if (left == null && right == null) {
if(parent == null){
root = null;
}else {
if (parent.leftChild == node) {
parent.leftChild = null;
} else {
parent.rightChild = null;
}
}
node.parent = null;
}
2.如果删除的节点只有右子树为空时：
else if (left != null && right == null) {
//第二种情况，只有左节点，没有右节点
if(parent == null){
root = left;
}else {
if (parent.leftChild == node) {
parent.leftChild = left;
} else {
parent.rightChild = left;
}
}
left.parent = parent;
node.parent = null;
node.leftChild = null;
}
3.如果删除的节点只有左子树为空时：
else if (left == null && right != null) {
//第三种情况，只有右节点，没有左节点
if(parent == null){
root = right;
}else {
if (parent.leftChild == node) {
parent.leftChild = right;
} else {
parent.rightChild = right;
}
}
right.parent = parent;
node.parent = null;
node.rightChild = null;
}
4.删除节点的左右子树均不为空时：
else {
//左右两边都有节点的
Node lleftNode = getLeftChildNode(right);
lleftNode.leftChild = left;
left.parent = lleftNode;
if(lleftNode.rightChild !=null){
if(lleftNode.parent != node){
lleftNode.parent.leftChild = lleftNode.rightChild;
lleftNode.rightChild.parent = lleftNode.parent;
}
}
if(lleftNode == right){
lleftNode.rightChild =null;
}else {
lleftNode.rightChild = right;
}
right.parent = lleftNode;
if(parent == null){
lleftNode.parent = null;
root = lleftNode;
}else {
if(parent.leftChild == node){
parent.leftChild = lleftNode;
}else {
parent.rightChild = lleftNode;
}
lleftNode.parent = parent;
}
node.leftChild = null;
node.rightChild =null;
node.parent = null;
}
完整代码
package com.example.administrator.myapplication;
/**
* Created by Administrator on 2018-12-09.
*/
public class SearchBinaryTree<T extends Comparable> {
Node root;
int size;
public class Node <T extends Comparable>{
T item;
Node<T> leftChild;
Node<T> rightChild;
Node<T> parent;
public Node(T item) {
this.item = item;
}
}
public int size() {
return size;
}
public boolean add(T item) {
Node<T> newNode = new Node<T>(item);
if (root == null) {
//如果是空树
root = newNode;
size++;
return true;
}
Node node = root;
Node parent = null;
while (node != null) {
parent = node;
if (node.item.compareTo(item) == 0) {
//去掉重复的，不进行添加操作
return false;
} else if (node.item .compareTo(item) >0) {
//如果加入的节点比做节点小
node = node.leftChild;
} else {
//如果加入的节点比做节点大
node = node.rightChild;
}
}
if (parent.item .compareTo(item)>0) {
parent.leftChild = newNode;
} else {
parent.rightChild = newNode;
}
newNode.parent = parent;
size++;
return true;
}
public Node get(T item) {
if (root == null) {
return null;
}
Node node = root;
while (node != null) {
if (node.item.compareTo(item)<0) {
node = node.rightChild;
} else if (node.item.compareTo(item)>0) {
node = node.leftChild;
} else {
return node;
}
}
return null;
}
/**
* 采取中序遍历的方式对树进行遍历
*/
public void midOrderTraseval(){
midOrderTraseval(root);
}
private void midOrderTraseval(Node<T> node) {
if (node == null) {
return;
}
midOrderTraseval(node.leftChild);
System.out.print(node.item +" ");
midOrderTraseval(node.rightChild);
}
public Node<T> delete(T item){
Node<T> node = get(item);
if(node !=null){
delete(node);
}
return node;
}
private void delete(Node<T> node) {
if (node == null) {
return;
}
Node<T> left = node.leftChild;
Node<T> right = node.rightChild;
Node<T> parent = node.parent;
//第一种情况 node 为叶子节点
if (left == null && right == null) {
if(parent == null){
root = null;
}else {
if (parent.leftChild == node) {
parent.leftChild = null;
} else {
parent.rightChild = null;
}
}
node.parent = null;
} else if (left != null && right == null) {
//第二种情况，只有左节点，没有右节点
if(parent == null){
root = left;
}else {
if (parent.leftChild == node) {
parent.leftChild = left;
} else {
parent.rightChild = left;
}
}
left.parent = parent;
node.parent = null;
node.leftChild = null;
}else if (left == null && right != null) {
//第三种情况，只有右节点，没有左节点
if(parent == null){
root = right;
}else {
if (parent.leftChild == node) {
parent.leftChild = right;
} else {
parent.rightChild = right;
}
}
right.parent = parent;
node.parent = null;
node.rightChild = null;
}else {
//左右两边都有节点的
Node lleftNode = getLeftChildNode(right);
lleftNode.leftChild = left;
left.parent = lleftNode;
if(lleftNode.rightChild !=null){
if(lleftNode.parent != node){
lleftNode.parent.leftChild = lleftNode.rightChild;
lleftNode.rightChild.parent = lleftNode.parent;
}
}
if(lleftNode == right){
lleftNode.rightChild =null;
}else {
lleftNode.rightChild = right;
}
right.parent = lleftNode;
if(parent == null){
lleftNode.parent = null;
root = lleftNode;
}else {
if(parent.leftChild == node){
parent.leftChild = lleftNode;
}else {
parent.rightChild = lleftNode;
}
lleftNode.parent = parent;
}
node.leftChild = null;
node.rightChild =null;
node.parent = null;
}
size--;
}
private Node<T> getLeftChildNode(Node<T> node){
Node<T> leftChild = node;
Node<T> newNode = node;
while (newNode!=null){
leftChild = newNode;
newNode = newNode.leftChild;
}
return leftChild;
}
}
测试及结果打印
@Test
public void testSearchTree(){
SearchBinaryTree<Integer> tree = new SearchBinaryTree();
int[] array = new int[]{5,4,9,2,0,7,3,1,8};
for (int i : array) {
tree.add(i);
}
for (int i : array) {
tree.midOrderTraseval();
System.out.println("-----------------------");
tree.delete(i);
}
for (int i : array) {
tree.add(i);
}
tree.midOrderTraseval();
}
结果打印
0 1 2 3 4 5 7 8 9 -----------------------
0 1 2 3 4 7 8 9 -----------------------
0 1 2 3 7 8 9 -----------------------
0 1 2 3 7 8 -----------------------
0 1 3 7 8 -----------------------
1 3 7 8 -----------------------
1 3 8 -----------------------
1 8 -----------------------
8 -----------------------
0 1 2 3 4 5 7 8 9
完美收工：
初次写技术博客，各位大牛请多包涵，共同进步！
