2021年2月17日 二叉树
二叉树的插入、前序遍历、中序遍历、后序遍历、查找节点、删除节点
首先需要一个节点Node类
public class Node {
public long data;
public Node leftNode;
public Node rightNode;
Node(long value){
this.data = value;
}
}接下来是二叉树，有一个根节点root
1、插入节点图示
2、删除节点
2.1 删除的节点没有子节点
2.2 删除的节点有一个子节点
2.2.1
(1)删除节点的右节点为空，删除的节点为右节点
(2)删除节点的右节点为空，删除的节点为左节点
2.2.2删除节点的左节点为空
(1)删除节点的左节点为空，删除的节点为左节点
(2)删除节点的左节点为空，删除的节点为左节点
2.3删除节点有两个子节点
package tree;
public class Tree {
public Node root;
public void insert(long value){//中序插入节点
//封装节点
Node newNode = new Node(value);
//创建一个当前节点
Node currentNode = root;
//父节点
Node parent;
if (root==null){//第一次插入
root = newNode;
return;
}else {
while (true) {
//因为插入时需要父节点指向，这里需要记录下parent节点
parent = currentNode;
if (value < currentNode.data) {//值比当前节点小，则往左走
currentNode = currentNode.leftNode;
if (currentNode==null){//如果当前节点为空，即走到了一个空节点，使用父节点赋值
parent.leftNode = newNode;
return;
}
} else {//值比当前节点大，则往右走
currentNode = currentNode.rightNode;
if (currentNode==null){//如果当前节点为空，即走到了一个空节点，使用父节点赋值
parent.rightNode = newNode;
return;
}
}
}
}
}
/**
* 寻找一个节点，若找到返回节点，没有返回null
* @param value
* @return
*/
public Node find(long value){
Node current = root;
while (current.data!=value){//循环直到找到当前节点的值等于value
if (current.data>value){
current = current.leftNode;
}else {
current = current.rightNode;
}
if (current == null){
return null;
}
}
return current;
}
public boolean delete(long value){//删除节点，二叉树难的部分
//需要使用当前节点进行遍历，记录父亲节点方便指向
Node current = root;
Node parent = root;
//记录下当前是否为左节点
boolean isLeft = true;
//1、首先要找到要删除的节点，这里与find()函数类似
while (current.data!=value){
parent = current;//这里将当前节点的值赋值给parent，后面current要指向leftNode或rightNode
if (current.data>value){
current = current.leftNode;
isLeft = true;//记录下isLeft的值
}else {
current = current.rightNode;
isLeft = false;//记录下isLeft的值
}
if (current==null){
return false;
}
}
//2、找到要删除的节点为current，接下来要对该节点进行删除
//2.1删除要分为三种情况：
//第一种：要删除的节点左右都为null
// 只需要利用parent与isLeft即可
if (current.leftNode==null && current.rightNode==null){
if (current==root) {
root = null;
}else if (isLeft){
parent.leftNode=null;
return true;
}else {
parent.rightNode=null;
return true;
}
//第二种：左节点为空或右节点为空
//右节点为空，那么左节点必定不为空
}else if (current.rightNode == null){
if (current==root){
root = current.leftNode;
}else if (isLeft){
parent.leftNode = current.leftNode;
//删除的节点是左节点，把删除节点的左节点赋值给parent的左节点，见图1
}else {
parent.rightNode = current.leftNode;
//删除的节点是右节点，把删除节点的左节点赋值给parent的右节点，见图2
}
//左节点为空，那么右节点必定不为空
}else if (current.leftNode == null){
if (current==root){
root = current.rightNode;
}else if (isLeft){
parent.leftNode = current.rightNode;
//删除的节点是左节点，把删除节点的右节点赋值给parent的左节点，见图3
}else {
parent.rightNode = current.rightNode;
//删除的节点是右节点，把删除节点的右节点赋值给parent的右节点，见图4
}
}else {
//第三种：删除的节点有两个子节点
Node successor = getSuccessor(current);
//1、先找到successor节点即要替换的节点
if (successor == root){
root = successor;
}else if (isLeft){
//如果删除的节点是左边的，也就是说parent缺少了左节点，将替换的节点赋值给parent的左节点
parent.leftNode = successor;
}else {
//如果删除的节点是右边的，也就是说parent缺少了右节点，将替换的节点赋值给parent的右节点
parent.rightNode = successor;
}
}
return false;
}
/**
* 给定要删除的节点delNode，返回一个替换的节点
* 替换节点：找到一个比当前节点大的最小节点
* 换言之，应先查找删除节点的右节点，再查找最左节点，见图5
* @param delNode
* @return
*/
public Node getSuccessor(Node delNode){
//替换节点
Node successor = delNode;
//替换节点的父节点
Node successorParent = delNode;
//用于遍历的当前节点，初始值为删除节点的右节点
Node current = delNode.rightNode;
//1、current最左边的节点
while (current!=null){
//successorParent记录successor的父节点
successorParent = successor;
//successor为当前节点
successor = current;
//current左移
current = current.leftNode;
//current为null时，successor为current的父节点，successorParent为successor的父节点
}
//2、如果替换节点不是删除节点的右节点
if (successor != delNode.rightNode){
//successor一定没有左节点了，successorParent就缺少了一个左节点，此时将successor的右节点接给successorParent的左节点
successorParent.leftNode = successor.rightNode;
//把删除节点的右节点赋值给successor的右节点
successor.rightNode = delNode.rightNode;
}
//无论替换节点是不是删除节点的右节点，替换节点的左节点都要指向删除节点的左节点
successor.leftNode = delNode.leftNode;
return successor;
}
public void firstOrder(Node local){
if (local==null)return;
//中左右
System.out.print(local.data+" ");
firstOrder(local.leftNode);
firstOrder(local.rightNode);
}
public void beforeOrder(Node local){
if (local==null){return;}
//左中右
beforeOrder(local.leftNode);
System.out.print(local.data+" ");
beforeOrder(local.rightNode);
}
public void laterOrder(Node local){
if (local==null){return;}
//左右中
laterOrder(local.leftNode);
laterOrder(local.rightNode);
System.out.print(local.data+" ");
}
}
测试类
public class TestTree {
public static void main(String[] args) {
Tree tree = new Tree();
tree.insert(30);
tree.insert(50);
tree.insert(20);
tree.insert(15);
tree.insert(25);
tree.insert(35);
tree.insert(55);
tree.insert(10);
tree.insert(18);
tree.insert(21);
tree.insert(27);
tree.insert(33);
tree.insert(40);
tree.insert(51);
tree.insert(60);
System.out.println("前序遍历");
tree.firstOrder(tree.root);
System.out.println();
System.out.println("中序遍历");
tree.beforeOrder(tree.root);
System.out.println();
System.out.println("后序遍历");
tree.laterOrder(tree.root);
System.out.println();
// 删除有两个子节点的
System.out.println("删除20：");
tree.delete(20);
tree.beforeOrder(tree.root);
System.out.println();
System.out.println("删除50：");
tree.delete(50);
tree.beforeOrder(tree.root);System.out.println();
System.out.println("删除35：");
tree.delete(35);
tree.beforeOrder(tree.root);System.out.println();
System.out.println("删除55：");
tree.delete(55);
tree.beforeOrder(tree.root);System.out.println();
System.out.println("删除15：");
tree.delete(15);
tree.beforeOrder(tree.root);System.out.println();
System.out.println("删除25：");
tree.delete(25);
tree.beforeOrder(tree.root);System.out.println();
}
}
样例输出
