内容学习于：edu.aliyun.com
1. 二叉树结构
在进行链表结构开发的过程之中会发现所有的数据按照收尾相连的状态进行保存，那么当要进行某一个数据查询的时候(判断该数据是否存在)，这种情况下它所面对的时间复杂度是“O(n)”， 如果说现在它的数据量小(不超过30个)情况下，那么性能上是不会有太大差别的，而一旦保存的数据量很大，这个时候时间复杂度就会严重损耗程序的运行性能，那么现在对于数据的存储结构就必须发生改变，应该可以尽可能的减少检索次数为出发点进行设计，对于现在的数据结构而言，最好的性能就是“O(logn)”，所以现在要想实现它就可以利用二叉树的结构来完成。
如果要想实现一棵树结构的定义，那么就需要去考虑数据的存储形式，在二叉树的实现之中其基本的实现原理如下:取第一个数据为保存的根节点，小于等于根节点的数据要放在节点的左子树，而大于节点的数据要放在该节点的右子树
如下图所示：
如果要进行数据检索的话，此时就需要进行每个节点的判断，但是它的判断是区分左右的，所以不会是整个的结构都进行判断处理，那么它的时间复杂度就是O(logn)。而对于二叉树而言，在进行数据获取的时候也有三种形式:<mark>前序遍历(根-左-右)、中序遍历(左-根-右)、后序遍历(左-右-根)</mark>，那么现在只是以中序遍历为主，则以上的数据进行中序遍历的时候最终的结果:30，50，75，80，100， 可以发现二叉树中的内容全部都属于排序的结果。
2. 二叉树基础实现
在实现二叉树的处理之中最为关键性的问题在于数据的保存，而且数据由于牵扯到对象比较的问题，那么一定要有比较器的支持，而这个比较器首选的一定就是Comparable，所以本次将保存一个Person类数据:
随后如果要想进行数据的保存，首先一定需要有一个节点类。节点类里面由于牵扯到数据的保存问题，所以必须使用Comparable (可以区分大小)
实现代码：
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{" +
"name='" + name + '\'' +
", age=" + age +
'}' + "\n";
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public int compareTo(Person per) {
return this.age - per.age;
}
}
class BinartTree<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 创建的新节点 */
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);//继续向下判断
}
}
}
/** * 实现所有数据的获取处理，按照中序遍历来完成 */
public void toArrayNode() {
if (this.left != null) {//有左子树
this.left.toArrayNode();//递归调用
}
BinartTree.this.returnData[BinartTree.this.foot++] = this.data;
if (this.right != null) {
this.right.toArrayNode();
}
}
}
//-----------------以下为二叉树的功能操作----------------
private Node root;//保存的是根节点
private int count = 0;//保存的数据个数
private int foot;//脚标
private Object[] returnData;//返回的数据
/** * 进行数据的保存 * * @param data 要保存的数据 * @throws NullPointerException 保存数据为空时抛出的异常 */
public void add(Comparable<T> data) {
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;//返回全部数据
}
}
public class JavaAPIDemo {
public static void main(String[] args) {
BinartTree<Person> tree = new BinartTree<>();
tree.add(new Person("小强-30", 30));
tree.add(new Person("小强-50", 50));
tree.add(new Person("小强-80", 80));
tree.add(new Person("小强-25", 25));
tree.add(new Person("小强-11", 11));
tree.add(new Person("小强-40", 40));
System.out.println(Arrays.toString(tree.toArray()));
}
}
结果：
[Person{name=‘小强-11’, age=11}
, Person{name=‘小强-25’, age=25}
, Person{name=‘小强-30’, age=30}
, Person{name=‘小强-40’, age=40}
, Person{name=‘小强-50’, age=50}
, Person{name=‘小强-80’, age=80}
]
在进行数据添加的时候只是实现了节点关系的保存，而这种关系保存后的结果就是所有的数据都属于有序排列。
3. 数据查询
二叉树与普通的链表相比最大的优势在于其检索速度的提升，传统的链表在进行数据检索的时候往往都需要进行全部数据的检索，而二叉树由于其排列的有序性，所以整体的检索的速度会有很大的提升(小数据量是感受不到的)。
如果说现在要想进行检索处理，那么就有一个实际的情况出现了，下面首先先实现一个简单的信息检索，这个信息检索指的是根据对象的信息来查询。
实现简单的查询操作代码：
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{" +
"name='" + name + '\'' +
", age=" + age +
'}' + "\n";
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public int compareTo(Person per) {
return this.age - per.age;
}
}
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 创建的新节点 */
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);//继续向下判断
}
}
}
/** * 实现所有数据的获取处理，按照中序遍历来完成 */
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 找到返回true，否则返回false */
public boolean containsNode(Comparable<T> data) {
if (data.compareTo((T) this.data) == 0) {
return true;//找到了
} else if (data.compareTo((T) this.data) < 0) {
if (this.left == null)
return false;
else {
return this.left.containsNode(data);
}
} else {
if (this.right == null) {
return false;
} else {
return this.right.containsNode(data);
}
}
}
}
//-----------------以下为二叉树的功能操作----------------
private Node root;//保存的是根节点
private int count = 0;//保存的数据个数
private int foot;//脚标
private Object[] returnData;//返回的数据
/** * 进行数据的保存 * * @param data 要保存的数据 * @throws NullPointerException 保存数据为空时抛出的异常 */
public void add(Comparable<T> data) {
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++;
}
/** * 现在的检索主要依靠的是Comparable实现的数据比较 * * @param data 要查询的数据 * @return 查找到数据返回true，否则返回false */
public boolean contains(Comparable<T> data) {
if (this.count == 0) {
return false;
}
return this.root.containsNode(data);
}
/** * 以对象数组的形式返回全部数据，如果没有返回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;//返回全部数据
}
}
public class JavaAPIDemo {
public static void main(String[] args) {
BinaryTree<Person> tree = new BinaryTree<>();
tree.add(new Person("小强-30", 30));
tree.add(new Person("小强-50", 50));
tree.add(new Person("小强-80", 80));
tree.add(new Person("小强-25", 25));
tree.add(new Person("小强-11", 11));
tree.add(new Person("小强-40", 40));
System.out.println(tree.contains(new Person("小强-80", 70)));
}
}
结果：
false
那么这个时候实际上应该去思考-一个问题了，对于这样的数据保存有什么意义?那么如果说换-一个思路，假设现在要保存的
数据不是一个单独Person类对象，可能是一个复合对象(二元偶对象)，这种对象的主要特点是可以根据“key"获取对应的“value”(对象)，则可以单独定义一个包装的实体类。可以轻松的实现根据某一个key查找对应value数据的处理，时间复杂度很低的
实现复杂的数据查询操作代码：
public class MapBinaryTreeDemo {
public static void main(String[] args) {
MapBinaryTree<Integer, Person> tree = new MapBinaryTree<>();
tree.add(30, new Person("小强-30", 30));
tree.add(50, new Person("小强-50", 50));
tree.add(80, new Person("小强-80", 80));
tree.add(25, new Person("小强-25", 25));
tree.add(11, new Person("小强-11", 11));
tree.add(40, new Person("小强-40", 40));
System.out.println(tree.contains(70));
System.out.println(tree.contains(50));
Object results[] = tree.toArray();
for (Object obj : results) {
MapBinaryTree.Entry<Integer, Person> entry = (MapBinaryTree.Entry<Integer, Person>) obj;
System.out.println(entry.getKey() + "--------" + entry.getValue());
}
}
}
class 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{" +
"name='" + name + '\'' +
", age=" + age +
'}' + "\n";
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
}
/** * 实现二叉树的操作 * * @param <K> 进行数据存储的key，通过它进行查询，这个key的Comparable的子类 * @param <V> 保存的具体数据信心 */
class MapBinaryTree<K extends Comparable<K>, V> {
public static class Entry<K extends Comparable<K>, V> {
private K key;
private V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
public int compareTo(K o) {
return this.key.compareTo(o);
}
}
private class Node {
private MapBinaryTree.Entry<K, V> data;
private Node parent;//父节点
private Node left;//左子树
private Node right;//右子树
public Node(MapBinaryTree.Entry<K, V> data) {
this.data = data;
}
/** * 实现节点数据的适当位置保存 * * @param newNode 创建的新节点 */
public void addNode(Node newNode) {
if (newNode.data.key.compareTo(this.data.key) <= 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();//递归调用
}
MapBinaryTree.this.returnData[MapBinaryTree.this.foot++] = this.data;
if (this.right != null) {
this.right.toArrayNode();
}
}
/** * 进行数据的检索处理 * * @param data 要检索的数据 * @return 找到返回true，否则返回false */
public boolean containsNode(MapBinaryTree.Entry<K, V> data) {
if (data.key.compareTo(this.data.key) == 0) {
return true;//找到了
} else if (data.key.compareTo(this.data.key) < 0) {
if (this.left == null)
return false;
else {
return this.left.containsNode(data);
}
} else {
if (this.right == null) {
return false;
} else {
return this.right.containsNode(data);
}
}
}
}
//-----------------以下为二叉树的功能操作----------------
private Node root;//保存的是根节点
private int count = 0;//保存的数据个数
private int foot;//脚标
private Object[] returnData;//返回的数据
/** * 进行数据的保存 * * @throws NullPointerException 保存数据为空时抛出的异常 */
public void add(K key, V value) {
if (key == null || value == null) {
throw new NullPointerException("保存的数据不能为空");
}
//所有的数据不具备节点关系匹配，那么一定要将其包装在Node类之中
Node newNode = new Node(new MapBinaryTree.Entry(key, value));//保存节点
if (this.root == null) {
this.root = newNode;
} else {//需要为其保存在一个合适的节点
this.root.addNode(newNode);//交由Node类处理
}
this.count++;
}
/** * 现在的检索主要依靠的是Comparable实现的数据比较 * * @return 查找到数据返回true，否则返回false */
public boolean contains(K key) {
if (this.count == 0) {
return false;
}
return this.root.containsNode(new MapBinaryTree.Entry(key, null));
}
/** * 以对象数组的形式返回全部数据，如果没有返回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;//返回全部数据
}
}
结果：
false
true
11--------Person{name=‘小强-11’, age=11}
25--------Person{name=‘小强-25’, age=25}
30--------Person{name=‘小强-30’, age=30}
40--------Person{name=‘小强-40’, age=40}
4. 数据删除
二叉树之中的数据删除操作是非常复杂的，因为在进行数据删除的时候需要考虑的情况是比较多的:
情况一:如果待删除节点没有子节点，那么直接删掉即可
如下图所示：
2、如果待删除节点只有一个子节点，那么直接删掉，并用其子节点去顶替它
只有一颗左子树的情况，如下图所示：
只有一颗右子树的情况，如下图所示：
3、如果待删除节点有两个子节点，这种情况比较复杂:首选找出它的后继节点，然后处理“后继点和“被删除节点的父节点”之间的关系，最后处理“后继节点的子节点”和“被删除节点的子节点”之间的关系。
如下图所示：
删除操作代码：
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{" +
"name='" + name + '\'' +
", age=" + age +
'}' + "\n";
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public int compareTo(Person per) {
return this.age - per.age;
}
}
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 创建的新节点 */
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);//继续向下判断
}
}
}
/** * 实现所有数据的获取处理，按照中序遍历来完成 */
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 找到返回true，否则返回false */
public boolean containsNode(Comparable<T> data) {
if (data.compareTo((T) this.data) == 0) {
return true;//找到了
} else if (data.compareTo((T) this.data) < 0) {
if (this.left == null)
return false;
else {
return this.left.containsNode(data);
}
} else {
if (this.right == null) {
return false;
} else {
return this.right.containsNode(data);
}
}
}
/** * 执行删除数据的查找操作 * * @param data 要删除的数据 * @return 如果该数据存在，返回该数据，否则返回null */
public Node getRemoveNode(Comparable<T> data) {
if (data.compareTo((T) this.data) == 0) {
return this;//找到了
} else if (data.compareTo((T) this.data) < 0) {
if (this.left == null)
return null;
else {
return this.left.getRemoveNode(data);
}
} else {
if (this.right == null) {
return null;
} else {
return this.right.getRemoveNode(data);
}
}
}
}
//-----------------以下为二叉树的功能操作----------------
private Node root;//保存的是根节点
private int count = 0;//保存的数据个数
private int foot;//脚标
private Object[] returnData;//返回的数据
/** * 进行数据的保存 * * @param data 要保存的数据 * @throws NullPointerException 保存数据为空时抛出的异常 */
public void add(Comparable<T> data) {
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++;
}
/** * 现在的检索主要依靠的是Comparable实现的数据比较 * * @param data 要查询的数据 * @return 查找到数据返回true，否则返回false */
public boolean contains(Comparable<T> data) {
if (this.count == 0) {
return false;
}
return this.root.containsNode(data);
}
/** * 以对象数组的形式返回全部数据，如果没有返回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.getRemoveNode(data);//找到要删除的节点
if (removeNode != null) {//找到要删除的对象
//情况1：没有任何节点
if (removeNode.left == null && removeNode.right == null) {
if (this.root.data.compareTo((T) removeNode.data) == 0) {
this.root = null;
this.count--;
return;
}
if (removeNode.data.compareTo((T) removeNode.parent.data) <= 0) {
removeNode.parent.left = null;
} else {
removeNode.parent.right = null;
}
removeNode.parent = null;//删除数据
}
//情况2：有一个节点
else if (removeNode.left == null && removeNode.right != null) {//右边不为空
if (this.root.data.compareTo((T) removeNode.data) == 0) {
this.root = removeNode.right;
this.count--;
return;
}
removeNode.right.parent = removeNode.parent;
if (removeNode.data.compareTo((T) removeNode.parent.data) <= 0) {
removeNode.parent.left = removeNode.right;
} else {
removeNode.parent.right = removeNode.right;
}
if (this.root.data.compareTo((T) removeNode.data) == 0) {
this.root = removeNode.right;
}
removeNode.parent = null;
} else if (removeNode.left != null && removeNode.right == null) {
if (this.root.data.compareTo((T) removeNode.data) == 0) {
this.root = removeNode.left;
this.count--;
return;
}
removeNode.left.parent = removeNode.parent;
if (removeNode.data.compareTo((T) removeNode.parent.data) <= 0) {
removeNode.parent.left = removeNode.left;
} else {
removeNode.parent.right = removeNode.left;
}
if (this.root.data.compareTo((T) removeNode.data) == 0) {
this.root = removeNode.left;
}
removeNode.parent = null;
}
//情况3：两边都有节点
else {
Node moveNode = removeNode.right;//寻找要移动的节点
while (moveNode.left != null) {
moveNode = moveNode.left;//递归寻找最左边的节点
}
//removeNode.parent.left = moveNode;
if (moveNode.data.compareTo((T) moveNode.parent.data) <= 0) {
moveNode.parent.left = null;//断开原来连接
} else {
moveNode.parent.right = null;//断开原来连接
}
moveNode.parent = removeNode.parent;//设置新连接
moveNode.left = removeNode.left;//改变右连接指向
moveNode.right = removeNode.right;//改变右连接指向
if (this.root.data.compareTo((T) removeNode.data) == 0) {
this.root = moveNode;
this.count--;
return;
}
if (removeNode.data.compareTo((T) removeNode.parent.data) <= 0) {
removeNode.parent.left = moveNode;
} else {
removeNode.parent.right = moveNode;
}
removeNode.parent = null;
}
}
this.count--;
}
public int getCount() {
return this.count;
}
}
public class JavaAPIDemo {
public static void main(String[] args) {
BinaryTree<Person> tree = new BinaryTree<>();
tree.add(new Person("小强-80", 80));
tree.add(new Person("小强-50", 50));
tree.add(new Person("小强-90", 90));
tree.add(new Person("小强-30", 30));
tree.add(new Person("小强-60", 60));
tree.add(new Person("小强-55", 55));
tree.add(new Person("小强-70", 70));
tree.add(new Person("小强-85", 85));
tree.add(new Person("小强-83", 83));
tree.add(new Person("小强-87", 87));
tree.add(new Person("小强-95", 95));
tree.add(new Person("小强-10", 10));
// System.out.println("------------第一种情况删除--------------");
// tree.remove(new Person("小强-10", 10));
// System.out.println(Arrays.toString(tree.toArray()));
// System.out.println("------------第二种情况删除--------------");
// tree.remove(new Person("小强-30", 30));
// System.out.println(Arrays.toString(tree.toArray()));
// System.out.println("------------第二种情况删除--------------");
// tree.remove(new Person("小强-70", 70));
// System.out.println(Arrays.toString(tree.toArray()));
// System.out.println("------------第三种情况删除--------------");
// tree.remove(new Person("小强-50", 50));
// System.out.println(Arrays.toString(tree.toArray()));
// System.out.println("------------第三种情况删除--------------");
// tree.remove(new Person("小强-85", 85));
// System.out.println(Arrays.toString(tree.toArray()));
System.out.println("------------第四种情况删除--------------");
tree.remove(new Person("小强-80", 80));
System.out.println(Arrays.toString(tree.toArray()));
}
}
京公网安备 11010502036488号