二叉树介绍
在进行链表结构开发的过程之中会发现所有的数据按照首尾相连的状态进行保存，那么当要进行某一个数据查询的时候（判断该数据是否存在），这种情况下的时间复杂度是“O(n)”，如果说链表的数据量小的情况下，性能上是不会有很大差别的，而一旦数据量很大，这个时候时间复杂度就会很大程度上损耗程序的运行性能，因此数据的存储结构必然要做出改变，应该可以尽可能的减少检索次数为出发点进行设计。对于现在的数据结构而言，最好的性能就是“O(logn)”，所以要想实现它，就可以利用二叉树的结构来完成。
如果要实现一棵树的结构的定义，那么需要去考虑数据的存储形式，在二叉树的是实现中，其基本的实现原理如下：取第一个数据为保存的根节点，小于该节点的数据放在该节点的左子树，而大于该节点的数据要放在该节点的右子树。
二叉树
如果要进行数据检索的话，此时就需要进行每个节点的判断，但是它的判断是区分左右的，所以不会是整个结构都进行判断处理，所以它的时间复杂度就是“O(logn)”。
而对于二叉树而言，在进行数据获取的时候也有三种形式：前序遍历（根-左-右）、中序遍历（左-根-右）、后序遍历（左-右-根），那么现在只是以中序遍历为主，则以上的数据进行中序遍历的时候最终的结果：10、20、25、30、38、50、80、100；
二叉树的基础实现
数据添加
在实现二叉树的处理之中最为关键的问题在于数据的保存，而且数据由于涉及到对象比较的问题，那么一定要有比较器的支持，而这个比较器首选一定是Comparable，随后如果想要进行数据的保存，首先一定要有一个节点类，节点类中由于涉及数据保存问题，所以必须使用Comparable（可以区分大小）；
import java.util.Arrays;
public class JavaApiDemo {
public static void main(String[] args) throws Exception{
BinaryTree<Person> tree=new BinaryTree();
tree.add(new Person("张三",30));
tree.add(new Person("李四",31));
tree.add(new Person("王五",28));
tree.add(new Person("赵六",38));
tree.add(new Person("孙七",37));
System.out.println(Arrays.toString(tree.toArray()));
//[【Person类对象】姓名：王五、年龄：28, 【Person类对象】姓名：张三、年龄：30, 【Person类对象】姓名：李四、年龄：31, 【Person类对象】姓名：孙七、年龄：37, 【Person类对象】姓名：赵六、年龄：38]
}
}
/**
* 实现二叉树操作
* @param <T> 要进行二叉树的实现
*/
class BinaryTree<T extends Comparable<T>>{
private class Node{
private Comparable<T> data;//存放Comparable,可以比较大小
private Node parent;//父节点
private Node left;//左子树
private Node right;//右子树
public Node(Comparable<T> data){//构造方法直接进行数据的存储
this.data=data;
}
/**
* 实现节点数据的适当位置的存储
* @param newNode 创建的新节点
* @throws IllegalArgumentException 保存的数据已存在
*/
public void addNode(Node newNode)throws IllegalArgumentException {
int rs=newNode.data.compareTo((T)this.data);
if(rs==0){
throw new IllegalArgumentException("添加失败，保存的数据已存在");
}
if(rs<0){//比当前节点数据小
if(this.left==null){//判断是否有左子树
//当前没有左子树
this.left=newNode;//保存左子树
newNode.parent=this;//更新父节点
}else{
//需要向左边继续判断
this.left.addNode(newNode);//继续向下判断
}
}else{
//比根节点的数据大
if(this.right==null){
//当前没有右子树
this.right=newNode;//保存左子树
newNode.parent=this;//更新父节点
}else{
this.right.addNode(newNode);//继续向下判断
}
}
}
/**
* 实现所有数据的获取处理，按照中序遍历的形式来完成
*/
public void toArrayNode() {
if(this.left!=null){
this.left.toArrayNode();
}
BinaryTree.this.returnData[BinaryTree.this.foot++]=this.data;
if(this.right!=null){
this.right.toArrayNode();
}
}
}
//-------------------以下为二叉树的功能实现--------------
private Node root;//根节点
private int count;//数据个数
private Object[] returnData;//返回的数据
private int foot=0;//脚标控制
/**
* 进行数据的保存
* @param data 要保存的数据内容
* @throws NullPointerException 保存数据为空时抛出的异常
* @throws IllegalArgumentException 保存的数据已存在
*/
public void add(Comparable<T> data)throws NullPointerException,IllegalArgumentException{
if(data==null){
throw new NullPointerException("保存的数据不允许为空！");
}
//所有的数据本身不具备节点关系的匹配，那么一定要将其包装在Node类之中
Node newNode=new Node(data);//包装节点
if(this.root==null){//现在没有根节点，则将第一个节点作为根节点
this.root=newNode;
}else{
this.root.addNode(newNode);//交由node类进行处理
}
this.count++;
}
/**
* 以对象数组的形式返回全部数据，如果没有数据就返回null
* @return 全部数据
*/
public Object[] toArray(){
if(this.count==0){
return null;
}
this.returnData=new Object[this.count];//保存长度为数组长度
this.foot=0;//脚标清零
this.root.toArrayNode();//直接通过Node类负责
return this.returnData;//返回全部的数据
}
}
class Person implements Comparable<Person>{
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "【Person类对象】姓名：" + this.name + "、年龄：" + this.age;
}
@Override
public int compareTo(Person person) {
return this.age-person.age;//升序
// return person.age-this.age;//降序
}
}
在进行数据添加的时候只是实现了节点关系的保存，而这种关系的保存后的结果就是所有的数据都是有序排列。
数据删除
二叉树中数据删除操作是非常复杂的，因为在进行数据删除的时候需要考虑很多情况：
root：根节点、isRoot：待删除节点是否为根节点
removeNode：待删除节点、removeParentNode：待删除节点父节点
parent：父节点、left：左子节点、right：右子节点
isLeftNode：待删除节点是否为父节点的左子节点，true为左子节点，false为右子节点
情况1、如果待删除节点没有子节点；
//不包含子节点
if(isRoot){
this.root=null;
}else{
removeNode.parent = null;//父节点断开引用
if(isLeftNode){
removeParentNode.left=null;
}else{
removeParentNode.right=null;
}
}
情况1
情况2、如果待删除节点只有一个左子节点；
//有左子树、没有右子树
if(isRoot){
this.root=this.root.left;
}else{
removeNode.left.parent=removeNode.parent;
if(isLeftNode){
removeParentNode.left=removeNode.left;
}else{
removeParentNode.right=removeNode.left;
}
}
情况2
情况3、如果待删除节点只有一个右子节点；
//有右子树、没有左子树
if(isRoot){
this.root=this.root.right;
}else{
removeNode.right.parent=removeNode.parent;
if(isLeftNode){
removeParentNode.left=removeNode.right;
}else{
removeParentNode.right=removeNode.right;
}
}
情况3
情况4、如果待删除节点有两个子节点：
//有左子树和右子树，将右边节点中最左边的节点找到，改变其指向
Node moveNode=removeNode.right;//移动的节点
if(moveNode.hasLeft()){
while (moveNode.hasLeft()){
//还有左边的节点,一直向左找
moveNode=moveNode.left;
}
//当前moveNode就是有节点的最小左节点
if(moveNode.hasRight()){
//如果后继节点有右子树，右子树将替换其原始的位置
moveNode.parent.left=moveNode.right;
}else{
//后继节点不包含右子树
moveNode.parent.left=null;
}
moveNode.right=removeNode.right;//改变原始的有节点的指向
}
moveNode.left=removeNode.left;
if(isRoot){
this.root=moveNode;
}else{
moveNode.parent=removeNode.parent;
if(isLeftNode){
removeParentNode.left=moveNode;
}else{
removeParentNode.right=moveNode;
}
}
情况4
下面通过具体的代码实现操作功能。
public class JavaApiDemo {
public static void main(String[] args) throws Exception{
BinaryTree<Person> tree=new BinaryTree();
tree.add(new Person("张三",80));
tree.add(new Person("李四",50));
tree.add(new Person("王五",90));
tree.add(new Person("赵六",30));
tree.add(new Person("孙七",60));
tree.add(new Person("周八",85));
tree.add(new Person("吴九",95));
tree.add(new Person("郑十",10));
tree.add(new Person("刘一",55));
tree.add(new Person("陈二",70));
tree.remove(new Person("张三",80));
Object[] arrays=tree.toArray();
for (Object array:arrays){
System.out.println(array);
}
/**
* 【Person类对象】姓名：郑十、年龄：10
* 【Person类对象】姓名：赵六、年龄：30
* 【Person类对象】姓名：李四、年龄：50
* 【Person类对象】姓名：刘一、年龄：55
* 【Person类对象】姓名：孙七、年龄：60
* 【Person类对象】姓名：陈二、年龄：70
* 【Person类对象】姓名：周八、年龄：85
* 【Person类对象】姓名：王五、年龄：90
* 【Person类对象】姓名：吴九、年龄：95
*/
}
}
/**
* 实现二叉树操作
* @param <T> 要进行二叉树的实现
*/
class BinaryTree<T extends Comparable<T>>{
private class Node{
private Comparable<T> data;//存放Comparable,可以比较大小
private Node parent;//父节点
private Node left;//左子树
private Node right;//右子树
public Node(Comparable<T> data){//构造方法直接进行数据的存储
this.data=data;
}
public boolean hasLeft(){
return left!=null;
}
public boolean hasRight(){
return right!=null;
}
/**
* 实现节点数据的适当位置的存储
* @param newNode 创建的新节点
* @throws IllegalArgumentException 保存的数据已存在
*/
public void addNode(Node newNode)throws IllegalArgumentException {
int rs=newNode.data.compareTo((T)this.data);
if(rs==0){
throw new IllegalArgumentException("添加失败，保存的数据已存在");
}
if(rs<0){//比当前节点数据小
if(this.left==null){//判断是否有左子树
//当前没有左子树
this.left=newNode;//保存左子树
newNode.parent=this;//更新父节点
}else{
//需要向左边继续判断
this.left.addNode(newNode);//继续向下判断
}
}else{
//比根节点的数据大
if(this.right==null){
//当前没有右子树
this.right=newNode;//保存左子树
newNode.parent=this;//更新父节点
}else{
this.right.addNode(newNode);//继续向下判断
}
}
}
/**
* 实现所有数据的获取处理，按照中序遍历的形式来完成
*/
public void toArrayNode() {
if(this.left!=null){
this.left.toArrayNode();
}
BinaryTree.this.returnData[BinaryTree.this.foot++]=this.data;
if(this.right!=null){
this.right.toArrayNode();
}
}
/**
* 获取要删除的节点对象
* @param data 比较的对象
* @return 要删除的节点对象，
*/
public Node findNode(Comparable<T> data) {
int rs=data.compareTo((T)this.data);
if(rs==0){
return this;//查找到了
}
if (rs < 0) {
if (this.left != null) {
return this.left.findNode(data);
}
return null;
}
if (this.right != null) {
return this.right.findNode(data);
}
return null;
}
}
//-------------------以下为二叉树的功能实现--------------
private Node root;//根节点
private int count;//数据个数
private Object[] returnData;//返回的数据
private int foot=0;//脚标控制
/**
* 进行数据的保存
* @param data 要保存的数据内容
* @throws NullPointerException 保存数据为空时抛出的异常
* @throws IllegalArgumentException 保存的数据已存在
*/
public void add(Comparable<T> data)throws NullPointerException,IllegalArgumentException{
if(data==null){
throw new NullPointerException("保存的数据不允许为空！");
}
//所有的数据本身不具备节点关系的匹配，那么一定要将其包装在Node类之中
Node newNode=new Node(data);//包装节点
if(this.root==null){//现在没有根节点，则将第一个节点作为根节点
this.root=newNode;
}else{
this.root.addNode(newNode);//交由node类进行处理
}
this.count++;
}
/**
* 以对象数组的形式返回全部数据，如果没有数据就返回null
* @return 全部数据
*/
public Object[] toArray(){
if(this.count==0){
return null;
}
this.returnData=new Object[this.count];//保存长度为数组长度
this.foot=0;//脚标清零
this.root.toArrayNode();//直接通过Node类负责
return this.returnData;//返回全部的数据
}
/**
* 执行数据的删除处理
* @param data 需要删除的数据
*/
public void remove(Comparable<T> data) {
if(this.root==null){//根节点不存在
return;
}
Node removeNode = this.root.findNode(data);
if (removeNode == null) {
return;
}
this.count--;
Node removeParentNode=removeNode.parent;
boolean isRoot=removeParentNode==null;
Boolean isLeftNode=null;
if(isRoot==false){
isLeftNode=data.compareTo((T)removeParentNode.data)<0;
}
//找到要删除的节点信息了
if (!removeNode.hasLeft() && !removeNode.hasRight()) {
if(isRoot){
this.root=null;
}else{
//不包含子节点
removeNode.parent = null;//父节点断开引用
if(isLeftNode){
removeParentNode.left=null;
}else{
removeParentNode.right=null;
}
}
} else if (removeNode.hasLeft() && !removeNode.hasRight()) {
//有左子树、没有右子树
if(isRoot){
this.root=this.root.left;
}else{
removeNode.left.parent=removeNode.parent;
if(isLeftNode){
removeParentNode.left=removeNode.left;
}else{
removeParentNode.right=removeNode.left;
}
}
} else if (!removeNode.hasLeft() && removeNode.hasRight()) {
//有右子树、没有左子树
if(isRoot){
this.root=this.root.right;
}else{
removeNode.right.parent=removeNode.parent;
if(isLeftNode){
removeParentNode.left=removeNode.right;
}else{
removeParentNode.right=removeNode.right;
}
}
}else{
//有左子树和右子树，将右边节点中最左边的节点找到，改变其指向
Node moveNode=removeNode.right;//移动的节点
if(moveNode.hasLeft()){
while (moveNode.hasLeft()){
//还有左边的节点,一直向左找
moveNode=moveNode.left;
}
//当前moveNode就是有节点的最小左节点
if(moveNode.hasRight()){
//如果后继节点有右子树，右子树将替换其原始的位置
moveNode.parent.left=moveNode.right;
}else{
//后继节点不包含右子树
moveNode.parent.left=null;
}
moveNode.right=removeNode.right;//改变原始的有节点的指向
}
moveNode.left=removeNode.left;
if(isRoot){
this.root=moveNode;
}else{
moveNode.parent=removeNode.parent;
if(isLeftNode){
removeParentNode.left=moveNode;
}else{
removeParentNode.right=moveNode;
}
}
}
}
}
class Person implements Comparable<Person>{
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "【Person类对象】姓名：" + this.name + "、年龄：" + this.age;
}
@Override
public int compareTo(Person person) {
return this.age-person.age;//升序
// return person.age-this.age;//降序
}
}
可见，二叉树数据结构删除操作是非常繁琐的，所以如果不是必须的情况下，不建议进行删除操作。
