前言
在上一篇写了一个简单的双向链表，难度是简简单单，这次来尝试二叉树，难度是也还行吧，多少有点夸张的成分了，不过对于大佬来说这些就是简简单单。
难度列表：
- 集合：有手就行
- 链表：简简单单
- 队列：基础操作
- 二叉树：也还行吧
- 平衡二叉树：普普通通
- 红黑树：有点难度了
- 堆/栈：难度提升了
- 图：今天是高端局
属性
二叉树是有一个根节点的，大部分操作都是基于根节点进行向下处理，所以需要显式的定义一个根节点root。
代码语言：javascript复制private Node root;二叉树的每个节点都有左右节点跟它自身的属性值，所以Node内容中需要有左右节点的属性left和right，至于自身属性Demo还是用数值类型Integer
代码如下：
代码语言：javascript复制 private class Node{
private Node left;
private Node right;
private Integer data;
public Node(Integer data){
this.data = data;
}
}ADD
第一步：判断root是否为空，为空则初始化root节点，否则执行add方法
private void add(int data) {
if (Objects.isNull(root)){
root = new Node(data);
}else{
root.add(data);
}
}第二步：add方法，判断参数值是否小于节点值，小于挪移到左节点处理，大于挪移到右节点处理
代码语言：javascript复制 private void add(Integer data) {
if (this.data >= data){
// left
}else{
// right
}
}第三步：判断左/右节点是否为空，为空则初始化节点，否则递归进行add方法
private void add(Integer data) {
if (this.data >= data){
if (Objects.isNull(this.left)){
this.left = new Node(data);
}else{
this.left.add(data);
}
}else{
if (Objects.isNull(this.right)){
this.right = new Node(data);
}else{
this.right.add(data);
}
}
}GET
二叉搜索树查询值有三种遍历方式：
- 前序遍历
- 中序遍历
- 后续遍历
这里不每一个都将了，就选择最常用的中序遍历作为我们查询值内容的遍历方式
代码如下：
代码语言：javascript复制 public Node get(Integer data) {
Node now = this;
if (now.data == data){
return now;
}else{
if (now.left != null){
Node left = now.left.get(data);
if (left != null){
return left;
}
}
if (now.right != null){
Node right = now.right.get(data);
if (right != null){
return right;
}
}
}
return null;
}Delete
删除操作是二叉搜索树里最复杂的了，根据删除节点的不同需要进行调整，分类有以下几类：
- 叶子节点：叶子节点是左右节点属性都没有的节点，这种的可以直接删除
- 单向非叶子节点：单向非叶子节点代表左右节点只有一个节点存在，这种的直接将指向
删除节点的指针指向子节点即可 - 双向非叶子节点：如果删除节点的左右节点都存在，这种的是
最复杂的，因为如果删除这种节点需要对子节点进行挪移， 找到左节点的最右节点进行替换现在删除节点的位置，之前节点位置删除。
删除代码：
代码语言：javascript复制 public Node delete(Node parrent, Integer data) {
if (this != null){
if (this.data == data){
if (this.left == null && this.right == null){
if (parrent.left != null && parrent.left.data == data){
parrent.left = null;
}else {
parrent.right = null;
}
}else if(this.left != null && this.right == null){
parrent.left = this.left;
}else if(this.left == null && this.right != null){
parrent.right = this.right;
}else{
Node node = this.left.getRightNode(this.left);
node.left = this.left;
node.right = this.right;
if (parrent.left != null && parrent.left.data == data){
parrent.left = node;
}else {
parrent.right = node;
}
}
}else{
if (data > this.data) {
this.right.delete(this,data);
} else {
this.left.delete(this,data);
}
return this;
}
}
return null;
}获取最左叶子节点并删除返回
这个获取最左节点的方式我写了两种，一种是递归、一种是循环
递归方式：
代码语言：javascript复制 private Node getRightNode(Node node){
if(this.right != null){
return this.right.getRightNode(this);
}
node.right = null;
return this;
}循环方式：
代码语言：javascript复制 private Node getRightNode(Node node){
Node now = this;
Node buffer = this;
while(now.right != null){
buffer = now;
now = now.right;
}
buffer.right = null;
return now;
}验证
往树结构内写入部分数据并删除其中节点，查看输出内容是否对应。
代码如下：
代码语言：javascript复制 public static void main(String[] args) {
OrdinaryBinaryTree tree = new OrdinaryBinaryTree();
tree.add(4);tree.add(7);tree.add(8);tree.add(2);
tree.add(-1);tree.add(3);tree.add(0);tree.add(11);tree.add(14);tree.add(21);tree.add(9);
tree.print();
tree.delete(2);
tree.print();
}结果：
图形化结构：原始数据
图形化结构：删除后结构
