二叉树结构简介
- 在进行链表结构开发的过程之中会发现所有的数据按照首尾相连的状态进行保存，那么当要进行某一个数据查询的时候（判断该数据是否存在），这种情况下它所面对的时间复杂度是“O(n)”，如果说现在它的数据量小（不超过30个）的情况下，那么性能上是不会有太大的差别的，而一旦保存的数据量很大，这个时候时间复杂度就会严重损耗程序的运行性能，那么对于数据的存储结构就必须发生改变，尽可能的减少检索次数进行设计，对于现在的数据结构而言，最好的性能就是“O(logn)”，所以现在要想实现它就可以利用二叉树的结构来完成；
- 如果想要实现一棵树结构的定义，那么就需要去考虑数据的存储形式，在二叉树的实现之中其基本实现原理如下：
- 取第一个数据为保存的根结点，小于等于根结点的数据要放在节点的左子树，而大于根结点的数据要放在节点的右子树；
此图来源于李兴华老师
- 如果要进行数据检索的话，此时就需要进行每个节点的判断，但是它的判断是区分左右的，所以不会是整个的结构都进行判断处理，那么他的时间复杂度就是O(logn)；
- 对于二叉树而言，进行数据获取的时候有三种形式：前序遍历（根-左-右）、中序遍历（左-根-右）、后序遍历（左-右-根）；
- 现在以中序遍历为主，以上数据中序遍历的结果：10、20、25、30、38、50、80、100，可以发现二叉树中的内容全部都属于排序的结果；
二叉树基础实现
- 在实现二叉树的处理之中最为关键性的问题在于数据的保存，而且数据由于牵扯到对象比较的问题，那么一定有比较器的支持，而这个比较器首选的一定是Comparable1，所以本次将保存一个Person类数据：
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 int compareTo(Person per) {
return this.age - per.age;
}
@Override
public String toString() {
return "【Person类对象】姓名：" + this.name + "、年龄：" + this.age + "\n";
}
public void setName(String name) {
this.name = name;
}
public void setAge(int age) {
this.age = age;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
}
- 如果想要进行数据的保存，首先一定需要一个节点类，节点类里面由于牵扯到数据的保存问题，所以必须使用Comparable（可以区分大小）；
import java.util.Arrays;
/**
* @Description: 实现二叉树操作
* @Author: mars_wu
* @Date: 2021/1/4 下午4:24
*/
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;
}
/**
* @Description: 实现节点数据的适当位置存储
* @Param: [newNode创建的新节点]
* @return: void
* @Author: mars_wu
* @Date: 2021/1/4 下午4:35
*/
public void addNode(Node newNode) {
if (newNode.data.compareTo((T)this.data) <= 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);
}
}
}
/**
* @Description: 实现所有数据的获取处理，按照中序遍历的形式完成
* @Author: mars_wu
* @Date: 2021/1/4 下午5:12
*/
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;
/**
* @Description: 进行数据保存
* @Param: [data要保存的数据内容为null时抛出异常NullPointerException]
* @return: void
* @Author: mars_wu
* @Date: 2021/1/4 下午4:28
*/
public void add(Comparable<T> data) {
if (data == null) {
throw new NullPointerException("保存的数据不允许为空");
}
Node newNode = new Node(data);
if (this.root == null) {
this.root = newNode;
} else {
this.root.addNode(newNode);
}
this.count++;
}
/**
* @Description: 以对象数组的形式返回全部数据，没有数据时返回null
* @return: java.lang.Object[] 全部数据
* @Author: mars_wu
* @Date: 2021/1/4 下午5:09
*/
public Object [] toArray() {
if (this.count == 0) {
return null;
}
this.returnData = new Object[this.count];
this.foot = 0;
this.root.toArrayNode();
return this.returnData;
}
}
public class BinaryTreeApi {
public static void main(String[] args) throws Exception {
BinaryTree<Person> tree = new BinaryTree<Person>();
tree.add(new Person("张三-50", 50));
tree.add(new Person("李四-80", 80));
tree.add(new Person("王五-30", 30));
tree.add(new Person("牛六-10", 10));
tree.add(new Person("刘七-60", 60));
tree.add(new Person("吴八-20", 20));
tree.add(new Person("赵九-70", 70));
System.out.println(Arrays.toString(tree.toArray()));
}
}
- 在进行数据添加的时候只是实现了节点关系的保存，而这种关系保存后的结果就是所有的数据都属于有序排列；
