二叉树就是每个节点最多有两个分叉的树。这里我们写一写一个典型的例子二叉搜索树，它存在的实际意义是什么呢?
在P1.1链表中，我们清楚了链表的优势是善于删除添加节点，但是其取值很慢；数组的优势是善于取值，但是不利于删除添加节点。
而二叉搜索树，正是两者的折中方案。首先，它是树状结构，因此它便于插入和删除节点，需要花费LogN级别的时间，其次，它
在每一个节点上都满足`左子树 <= 当前节点 <= 右子树`,因此便于使用二叉搜索，所以查找数据和取数据也是LogN级别的。
| 时间比较 | 链表 | 二叉搜索树 | 数组 |
| 取值 | N | LogN | C |
| 查找 | N | LogN | 有序数组:LogN 无序数组:N |
| 插入和删除 | C | LogN | N |
常见的二叉搜索树操作有:
1.插入新节点
2.按值查找节点
3.删除节点
4.三种遍历方式
5.二叉搜索树的宽度
6.二叉搜索树最大距离
TODO : 待解析
Java代码:
package ds4.binaryTree; import java.util.ArrayDeque;
import java.util.Queue; /**
* 二叉搜索树
*/
public class BinarySearchTree { static class Node {
long data;
Node left;
Node right; public Node(long data) {
this.data = data;
} @Override
public String toString() {
return "N["+data+"]";
}
} static class Tree{
Node root;
Tree(){} /**
* 添加节点: 时间消耗LogN
* @param node
*/
public void addNode(Node node){
if(node == null){
return;
} if(this.root == null){
this.root = node;
return;
}
Node current = root;
Node parent = current;
while(current != null){
parent = current;
if(current.data >= node.data){
current = current.left;
}else{
current = current.right;
}
} if(parent.data >= node.data){
parent.left = node;
}else{
parent.right = node;
}
} /**
* 查找节点
* 时间消耗LogN
* @param data
* @return
*/
public Node fineNodeByVal(long data){
Node result = null;
if(this.root == null){
return result;
} Node current = this.root;
while(current != null){
if(current.data > data){
current = current.left;
}else if(current.data < data){
current = current.right;
}else{
result = current;
break;
}
}
return result;
} /**
* 删除某个节点
* @param node
*/
public void removeNode(Node node){
if(this.root == null){
return;
} if(node == null){
return;
} if(this.root == node){
this.root = null;
node.left = node.right = null;
return;
} // 寻找其父节点
Node current = root;
Node parent = current;
while(current != null){
if(current == node){
break;
}
parent = current;
if(current.data < node.data){
current = current.right;
}else{
current = current.left;
}
}
if(current == null){
System.out.println("没有找到这个节点!");
return;
} if(node.left == null && node.right == null){ //左右都为空
// 找到其父节点直接删除即可
if(parent.left == null){
parent.left = null;
}else{
parent.right = null;
}
return;
}else if(node.left != null && node.right == null){ // 左子树不为空，而右子树为空
// 找到其父节点直接嫁接
if(parent.left == null){
parent.left = node.left;
}else{
parent.right = node.left;
} }else if(node.right != null && node.left == null){ // 右子树不为空，左子树为空
//找到父节点直接嫁接
if(parent.right == node){
parent.right = node.right;
}else{
parent.left = node.right;
}
}else{ // 左右子树都不为空
//找到左枝最靠右节点，删除；并找到带删除父节点，将待删除节点用左枝最右节点替代
Node current1 = node;
Node parent1 = node;
while (current1.right != null){
parent1 = current1;
current1 = current1.right;
}
if(parent1.right == current1){
parent1.right = null;
}else{
parent1.left = null;
}
// 到这里current1为最右左节点，parent1为current1的父节点，已经解除了父子关系
current1.left = node.left;
current1.right = node.right; if(parent.right == current){
parent.right = current1;
}else{
parent.left = current1;
} node.left = null;
node.right = null;
}
} /**
* 先根遍历
*/
public void firstRootIndex(Node root){
if(root != null){
System.out.println(root.data);
if(root.left != null){
firstRootIndex(root.left);
} if(root.right != null){
firstRootIndex(root.right);
}
}
} /**
* 后根遍历
* @param root
*/
public void lastRootIndex(Node root){
if(root != null){
if(root.left != null){
lastRootIndex(root.left);
}
if(root.right != null){
lastRootIndex(root.right);
}
System.out.println(root.data);
}
} /**
* 中序遍历
* @param root
*/
public void midRootIndex(Node root){
if(root != null){
if(root.left != null){
lastRootIndex(root.left);
}
System.out.println(root.data);
if(root.right != null){
lastRootIndex(root.right);
}
}
} /**
* 层序遍历
* @param root
*/
public void layerIndex(Node root){
// 1.当前层
Queue<Node> currentLayer = new ArrayDeque<Node>();
// 2.临时存储下一层节点
Queue<Node> sonLayer = new ArrayDeque<Node>(); if(this.root == null){
return;
}else{
currentLayer.add(this.root);
} while(currentLayer.size() != 0){
// 1.当前层节点出队列下一层入队列
sonLayer.clear();
while(currentLayer.size() != 0){
Node node = currentLayer.poll();
// 2.遍历本层节点
System.out.print(node); if(node.left != null){
sonLayer.add(node.left);
}
if(node.right != null){
sonLayer.add(node.right);
}
}
System.out.println();
// 3.将sonLayer赋给currentLayer,sonLayer重新创建对象
currentLayer = sonLayer;
sonLayer = new ArrayDeque<Node>();
} } /**
* 计算树的宽度
* 也就是树中节点数最多的层次对应的节点数
* 思路1: 进行一次树的遍历，也就是过一遍树的所有节点，将每一层的数据存储在Map数据结构中
* 思路2: 设置队列进行层序遍历，将这层的节点数量计算一下，然后出队列，下一层的节点入队列
*
* 思路2提供了除去以上三种遍历方式以外的第三种遍历方式
*/
public int computeWidth(){
int maxSize = 0;
// 1.当前层
Queue<Node> currentLayer = new ArrayDeque<Node>();
// 2.临时存储下一层节点
Queue<Node> sonLayer = new ArrayDeque<Node>(); if(this.root == null){
return maxSize;
}else{
currentLayer.add(this.root);
} while(currentLayer.size() != 0){
// 1. 计算当前层size
int currentSize = currentLayer.size();
maxSize = maxSize>currentSize?maxSize:currentSize;
// 2.当前层节点出队列下一层入队列
sonLayer.clear();
while(currentLayer.size() != 0){
Node node = currentLayer.poll();
if(node.left != null){
sonLayer.add(node.left);
}
if(node.right != null){
sonLayer.add(node.right);
}
}
// 3.将sonLayer赋给currentLayer,sonLayer重新创建对象
currentLayer = sonLayer;
sonLayer = new ArrayDeque<Node>();
} return maxSize;
} /**
* 计算二叉树中两点的最大距离
* 思路1: 左枝树长 + 右枝树长 算法:节省时间，占空间
* 思路2: 迭代 算法:节省空间，占用时间
*/
public int computeMaxDistance(){
if(this.root == null){
return 0;
} return computeDepth(this.root.left) + computeDepth(this.root.right);
} /**
* 计算二叉树的深度
* 和刚才计算宽度的思路一样，只是用深度来计算
* @return
*/
public int computeDepth(Node root){
int depth = 0;
// 1.当前层
Queue<Node> currentLayer = new ArrayDeque<Node>();
// 2.临时存储下一层节点
Queue<Node> sonLayer = new ArrayDeque<Node>(); if(root == null){
return depth;
}else{
currentLayer.add(root);
} while(currentLayer.size() != 0){
// 1. 计算当前层depth
depth ++;
// 2.当前层节点出队列下一层入队列
sonLayer.clear();
while(currentLayer.size() != 0){
Node node = currentLayer.poll();
if(node.left != null){
sonLayer.add(node.left);
}
if(node.right != null){
sonLayer.add(node.right);
}
}
// 3.将sonLayer赋给currentLayer,sonLayer重新创建对象
currentLayer = sonLayer;
sonLayer = new ArrayDeque<Node>();
} return depth;
} } public static void main(String[] args) {
Tree tree = new Tree();
tree.addNode(new Node(100));
tree.addNode(new Node(200));
tree.addNode(new Node(20));
tree.addNode(new Node(177));
Node nodeToRemove = new Node(88);
tree.addNode(nodeToRemove);
tree.addNode(new Node(90));
tree.addNode(new Node(60));
// 层序遍历
System.out.println("层次遍历");
tree.layerIndex(tree.root);
// 先根遍历
System.out.println("先根遍历");
tree.firstRootIndex(tree.root);
// 计算宽度与深度
tree.addNode(new Node(188));
System.out.println("width:"+tree.computeWidth());
System.out.println("depth:"+tree.computeDepth(tree.root));
// 删除节点
tree.removeNode(nodeToRemove);
// 层序遍历
System.out.println("层序遍历");
tree.layerIndex(tree.root);
// 后根遍历
System.out.println("后根遍历");
tree.lastRootIndex(tree.root);
System.out.println("最大距离:"+tree.computeMaxDistance()); }
}
result:
层次遍历
N[100]
N[20]N[200]
N[88]N[177]
N[60]N[90]
先根遍历
100
20
88
60
90
200
177
width:3
depth:4
层序遍历
N[100]
N[20]N[200]
N[90]N[177]
N[60]N[188]
后根遍历
60
90
20
188
177
200
100
最大距离:6