二叉树
大约 9 分钟
二叉树
二叉树简介
对于这种数据结构的面试题最早是在乐视面试的时候经常会被问到，就直接让学生去写一个二叉树，只要谁写出来了 ofer 就送给谁，在后来这种数据结构的面试问题基本上就成为了几乎所有的互联网公司都一定会询问话题:。
- 为什么项目中需要二叉树?
- 二叉树的基本实现原理是什么?
- Java 类集讲解之中的 HashMap 工作原理。
二叉树(Binary Tree、BT)是一种平衡的数据结构，其主要的目的是为了提升数据的査询性能，在之前讲解过了一次关于链表的技术实现，在链表技术实现的过程之中，有一个 contains()方法，这个方法主要是判断指定的数据是否存在于链表之中，而它进行排査的方法也非常简单:通过循环的形式获取每一个节点，而后判断节点中的数据是否符合于查询要求，如果符合，那么就表示有此数据存在，直接返回一个 true，但是如果要从时间复杂度去思考，这种 contains()数据査询它的时间复杂度为“O(n)”，但是也需要清楚链表存储数据的目的并不是为了让你查询使用，只是为了方便用户的使用提供了查询，但是现在如果说要想提升数据查询性能，那么又该怎么办呢?在学习 Java 类库的时候学习过一个 Arrays.binarySearch()，表示的是一种二分查找法，其主要的特点是避免全部数据的判断，所以其时间复杂度为“O(log2n)”，在整个的计算机的世界里面，现在为止最为常见的优化方式也在于此。所以这样的话就有了二叉树结构的产生，也就是说它的出现是为了解决数据查询问题。
链表与二叉树的区别是什么?
- 链表进行数据存储的目的是为了进行内容的输出(学习到 Java 类集框架，要使用“Colection”接口就属于链表);
- 二叉树存储数据的目的是为了进行数据的查询使用(学习到 Java 类集框架，要使用“Map”接口就属于树)。
如果要想理解二叉树对于性能的提升操作，最佳的做法就是自己来创建一个属于自己的二叉树，对于任何的数据结构来讲，由于数据本身都不能够形成关系的排列，那么一定要在程序类中基于 Node 节点进行控制，而树结构的 Node 节点和链表结构最大的不同在于:每一个节点中要保存有两个子节点，一个称为“左子树”，另外一个称为“右子树”。
- 那么对于这两个节点的数据保存，需要按照如下的原则进行:。
- 取第一个数据作为根节点的保存数据;
- 比根节点小的数据放在左子树(也可以保存相等的数据，或者就于脆不保存相等)
- 比根节点大的数据放在右子树。
- 当所有的数据全部保存完成之后则可以按照“中序遍历”的方式进行全部数据的获取;
关于二叉树的三种遍历模式
- 前序遍历:根-左-右;
- 中序变量:左-根-右;
- 后序遍历:左-右-根。
题目的分析:
前序遍历顺序(ADCEFGHB)就可以确定根节点是 A;
中序遍历顺序(CDFEGHAB)由于已经确定了根节点 A 存在，所以自然 B 一定是根节点右节点;
根据中序节点推断出基本的左子树的所有的节点顺序(前序:“DCEFGH”、中序:“CDFEGH”)，可以发现 D 一定是一个根节点
二叉树数据存储
获取二叉树数据
现在对于数据来讲已经将部分的内容保存在了二叉树的结构之中，但是对于这个时候还存在有另外一个问题:需要考虑把所存储的数据取出来，按照正常的设计模式来讲，应该采用中序遍历的模式，但是此时就会有一个比较尴尬局面:只能够采用对象数组的形式返回全部的数据内容，就首先一定要获取保存数据的个数，就需要追加有一个 size0 方法，同时还需要去考虑数据的取出问题，因为如果使用循环的方式取出难度较高，而且复杂度比较高，所以对于二又树的处理我个人的建议是使用递归。 此时所使用的是一种中序遍历的形式实现了整个代码的处理逻辑，所以最终的结果就采用了排序的模式进行存储。使用二叉树是为了数据的存储结构性，而存储的结构性所带来的最重要的特点就是整个的程序的检索性能会有所提升。
查询二叉树数据
使用二叉树实现数据存储的意义就在于可以快速的实现数据检索的定位操作，因为如果使用链表时间复杂度远远要高于二叉树的结构，所以对于二叉树来讲最重要的概念就是检索。 由于在二叉树的结构之中需要有排序的需求，那么既然要进行数据的排序处理，那么在整个实现机制上使用了 Comparable 比较器，所以本次的数据检索的查询判断就将基于比较器来实现。
二叉树数据删除
二叉树节点删除的三种情况:
- 1、如果待删除节点没有子节点，那么直接删掉即可;
- 2、如果待删除节点只有一个子节点，那么直接删掉，并用其子节点去顶替它;
- 3、如果待删除节点有两个子节点，这种情况比较复杂:首选找出它的后继节点，然后处理“后继节点”和“被删除节点的父节点”之间的关系，最后处理“后继节点的子节点”和“被删除节点的子节点”之间的关系。
案例
public interface IBinaryTree<E> { //定义二叉树标准接口
public void add(E data);
public int size();
public Object[] toArray();
public boolean contains(E data);
public void remove(E data);
}
class BinaryTreeImpl<E> implements IBinaryTree<E> {
private class Node { //内部类只为该外部类使用
private Comparable<E> data; //要存储数据，全部进行强制性转型
private Node left; //左子树
private Node right; //右子树
private Node parent; //根树
public Node(Comparable<E> data) {
this.data = data;
}
public void toArrayNode() {
if (this.left != null) {
this.left.toArrayNode(); //递归调用
}
BinaryTreeImpl.this.data[BinaryTreeImpl.this.foot++] = (E) this.data;
System.out.println("*******" + this.data);
if (this.right != null) {
this.right.toArrayNode();
}
}
public Node containsNode(E data) {
if (this.data.compareTo(data) == 0) {
return this;
} else {
if (this.data.compareTo(data) < 0) {
if (this.right != null) {
return this.right.containsNode(data);
} else {
return null;
}
} else {
if (this.left != null) {
return this.left.containsNode(data);
} else {
return null;
}
}
}
}
}
private Node root;
private int count; //保存数据个数
private int foot; //描述数组索引
private Object[] data; //返回对象数组
@Override
public void add(E data) {
if (data == null) {
throw new NullPointerException("存储在二叉树结构数据不允许为空！");
}
if (!(data instanceof Comparable)) {
throw new ClassCastException("要存储的数据没有实现java.lang.Comparable接口");
}
Node newNode = new Node((Comparable) data);
if (this.root == null) {
this.root = newNode;
} else {
Node currentNode = this.root; //设置当前节点
while (currentNode != newNode) { // 点钱节点不是新节点,表示新节点未保存
if (currentNode.data.compareTo(data) <= 0) { //比根节点大
if (currentNode.right != null) { //当前节点有右节点
currentNode = currentNode.right; //修改当前的节点
} else { //当前节点没有右节点
currentNode.right = newNode; //将新节点存在右节点
newNode.parent = currentNode; //设置父节点
currentNode = newNode; //结束循环
}
} else {
//同右节点
if (currentNode.left != null) {
currentNode = currentNode.left;
} else {
currentNode.left = newNode;
newNode.parent = currentNode;
currentNode = newNode;
}
}
}
}
this.count++;
}
@Override
public int size() {
return this.count;
}
@Override
public Object[] toArray() {
if (this.count == 0) {
return null;
}
this.data = new Object[this.count];
this.foot = 0;//清零标记
this.root.toArrayNode();
return this.data;
}
@Override
public boolean contains(E data) {
if (data == null) {
throw new NullPointerException("存储在二叉树结构数据不允许为空！");
}
if (!(data instanceof Comparable)) {
throw new ClassCastException("要存储的数据没有实现java.lang.Comparable接口");
}
if (this.size() == 0) {
return false;
}
return this.root.containsNode(data) != null;
}
@Override
public void remove(E data) {
if (data == null) {
throw new NullPointerException("存储在二叉树结构数据不允许为空！");
}
if (!(data instanceof Comparable)) {
throw new ClassCastException("要存储的数据没有实现java.lang.Comparable接口");
}
System.out.println(data);
if (this.contains(data)) {
if (this.root.data.compareTo(data) == 0) {
this.root = this.moveNode(data);
}
Node moveNode = this.moveNode(data);
if (moveNode != null) {
this.root = moveNode;
}
} else {
this.moveNode(data);
}
this.count--;
}
private Node moveNode(E data) {
Node moveSubNode = null; //假设当前节点为要移动的子节点
Node deleteNode = this.root.containsNode(data);
if (deleteNode == null) {
return null;
}
//如果待删除节点没有子节点，那么直接删掉即可
if (deleteNode.left == null && deleteNode.right == null) {
if (deleteNode.parent != null) {
if (deleteNode.parent.data.compareTo(data) <= 0) {
deleteNode.parent.right = null;
} else {
deleteNode.parent.left = null;
}
deleteNode.parent = null;
}
}
//如果待删除节点只有一个子节点，那么直接删掉，并用其子节点去顶替它;
if ((deleteNode.left != null & deleteNode.right == null) ||
(deleteNode.right != null & deleteNode.left == null)) {
moveSubNode = null;
if (deleteNode.left != null) {
moveSubNode = deleteNode.left;
} else {
moveSubNode = deleteNode.right;
}
if (deleteNode.parent != null) {
if (deleteNode.parent.data.compareTo(data) <= 0) {
deleteNode.parent.right = moveSubNode;
} else {
deleteNode.parent.left = moveSubNode;
}
}
moveSubNode.parent = deleteNode.parent;
}
//如果待删除节点有两个子节点
if (deleteNode.left != null && deleteNode.right != null) {
System.out.println("**********" + data);
moveSubNode = deleteNode.right;
while ((moveSubNode.left != null)) {
moveSubNode = moveSubNode.left;
}
// if (moveSubNode.right != null) {
// moveSubNode.parent.left = moveSubNode.right;
// moveSubNode.right.parent = moveSubNode.parent;
// } else {
// if (deleteNode.right != moveSubNode) {
// moveSubNode.parent.left = null;
// }
// }
moveSubNode.parent = deleteNode.parent;
moveSubNode.left = deleteNode.left;
if (deleteNode.right != moveSubNode) {
moveSubNode.right = deleteNode.right;
}
if (deleteNode.parent != null) {
if (deleteNode.parent.data.compareTo(data) <= 0) {
deleteNode.parent.right = moveSubNode;
} else {
deleteNode.parent.left = moveSubNode;
}
}
}
return moveSubNode;
}
}
class Book implements Comparable<Book> {
private String title;
private String author;
private double price;
public Book(String title, String author, double price) {
this.title = title;
this.author = author;
this.price = price;
}
@Override
public String toString() {
return "【Book】图书名称：" + this.title + "、图书作者" + this.author + "、图书价格：" + this.price;
}
@Override
public int compareTo(Book o) {
if (this.price > o.price) {
return 1;
} else if (this.price < o.price) {
return -1;
} else {
return 0;
}
}
}
class Test {
public static void main(String[] args) {
IBinaryTree<Integer> binaryTree = new BinaryTreeImpl<>();
binaryTree.add(6);
binaryTree.add(9);
binaryTree.add(97);
binaryTree.add(2);
binaryTree.add(3);
System.out.println(binaryTree.size());
for (Object obj : binaryTree.toArray()) {
System.out.print(obj + "、");
}
System.out.println();
System.out.println(binaryTree.contains(2));
System.out.println(binaryTree.contains(197));
}
}
class Test1 {
public static void main(String[] args) {
IBinaryTree<Book> binaryTree = new BinaryTreeImpl<>();
binaryTree.add(new Book("java基础1", "李兴华1", 99.0));
binaryTree.add(new Book("java基础2", "李兴华2", 99.12));
binaryTree.add(new Book("java基础3", "李兴华3", 38.0));
binaryTree.add(new Book("java基础4", "李兴华4", 29.0));
binaryTree.add(new Book("java基础5", "李兴华5", 199.0));
System.out.println(binaryTree.size());
for (Object obj : binaryTree.toArray()) {
System.out.print(obj + "、");
}
System.out.println();
System.out.println(binaryTree.contains(new Book("java基础111", "12李兴华112", 99.122)));
}
}
class Test2 {
public static void main(String[] args) {
IBinaryTree binaryTree = new BinaryTreeImpl();
int number[] = new int[]{80, 50, 90, 30, 60, 10, 86, 95};
for (int temp : number) {
binaryTree.add(temp);
}
// System.out.println("原始数据:" + Arrays.toString(binaryTree.toArray()));
binaryTree.remove(50);
binaryTree.remove(80);
binaryTree.remove(90);
System.out.println("获取全部数据:" + Arrays.toString(binaryTree.toArray()));
;
}
}