二叉树的删除操作
1. 首先要先写出两个方法，一个查找要删除的节点，另一个方法查找待删除节点的父节点，也可合并两个方法
2. 然后编写删除节点的方法，又分为三种情况
2.1 删除的是根节点
1)只有一个根节点的情况
2)根节点只有一个分支的情况
3)根节点有两个分支的情况
2.2 删除的是叶子节点
2.3 删除的是非叶子节点
1)被删除的节点只有一个分支(分为左和右)的情况
2)被删除的节点只有一个分支(分为左和右)(其中又是其父节点的左右)的情况
只贴出来了写在BinarySortTree中的方法，完整类见上一篇博客
public int delLeftMax(SNode sNode) {
//传进来的节点往右边找最大
SNode res = sNode;
while(res.getRight() != null) {
res = res.getRight();
}
delNode(res.getVal());
return res.getVal();
}
public boolean delNode(int val) {
//删除的节点尽量不要含有重复值,未线索化的删除方法,删除节点可能有叶子节点，只含有一个节点的节点，含有两个节点的节点
if(this.root == null) {
System.out.println("二叉树为空~~无法删除节点");
return false;
}
//删除的是根节点且只有一个根节点
if(this.root.getVal() == val && this.root.getLeft() == null && this.root.getRight() == null) { // 删除的是根节点且只有一个根节点，那么直接删除
this.root = null;
}
else { // 删除的不是根节点
SNode targetNode = searchNode(val);
SNode parentNode = searchParentNode(val);
if(parentNode == null) {
//删除的是根节点，但是根节点下还有别的节点
if(targetNode.getRight() == null) {
this.root = targetNode.getLeft();
}
else if(targetNode.getLeft() == null) {
this.root = targetNode.getRight();
}
else {
targetNode.setVal(delLeftMax(targetNode.getLeft()));
}
return true;
}
//先处理删除的是叶子节点的情况
if(targetNode.getLeft() == null && targetNode.getRight() == null) {
if(parentNode.getRight() != null && parentNode.getRight().getVal() == val) parentNode.setRight(null);
else parentNode.setLeft(null);
}
//删除的是有两个节点的节点
else if(targetNode.getLeft() != null && targetNode.getRight() != null) {
targetNode.setVal(delLeftMax(targetNode.getLeft()));
}
//删除的是只有一个节点的节点
else {
if(targetNode.getRight() != null && parentNode.getRight().getVal() == val) {
parentNode.setRight(targetNode.getRight());
}
else if(targetNode.getRight() != null && parentNode.getLeft().getVal() == val) {
parentNode.setLeft(targetNode.getRight());
}
else if(targetNode.getLeft() != null && parentNode.getLeft().getVal() == val) {
parentNode.setLeft(targetNode.getLeft());
}
else {
parentNode.setRight(targetNode.getLeft());
}
}
}
return true;
}
public SNode searchParentNode(int val) {
if(this.root == null) throw new RuntimeException("二叉树为空~~对应的节点不存在~~~");
if(this.root.getVal() == val) return null; // 要查找的是根节点
return searchParentNode(this.root, val);
}
public SNode searchParentNode(SNode sNode, int val) {
if(sNode == null) throw new RuntimeException("没有查找到对应的节点~~~");
if(sNode.getVal() > val) {
if(sNode.getLeft() != null && sNode.getLeft().getVal() == val) return sNode;
return searchParentNode(sNode.getLeft(), val);
}
else {
if(sNode.getRight() != null && sNode.getRight().getVal() == val) return sNode;
return searchParentNode(sNode.getRight(), val);
}
}
public SNode searchNode(int val) {
if(this.root == null) throw new RuntimeException("二叉树为空~~对应的节点不存在~~~");
return searchNode(this.root, val);
}
public SNode searchNode(SNode sNode, int val) {
//根据所给的值查找该节点
if(sNode == null) throw new RuntimeException("没有查找到对应的节点~~~");
if(sNode.getVal() == val) return sNode;
if(sNode.getVal() > val) return searchNode(sNode.getLeft(), val);
return searchNode(sNode.getRight(), val);
}
晚上任务(堆排序or赫夫曼树or赫夫曼编解码or平衡二叉树)
堆排序(不是很好理解 //堆排序
public static void heapSort(int[] arr) {
//必须知道第一个非叶子节点是arr.length/2 - 1，然后从该节点调整使其成为大顶堆
//经过这一次循环以后已经是大顶堆了
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
//将第一个元素与最后一个元素交换
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, i, 0);
adjustHeap(arr, 0, i);
}
}
//调整使以i为根节点的子树成为大顶堆
public static void adjustHeap(int[] arr, int i, int length) {
int temp = arr[i];
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
if((k + 1) < length && arr[k] < arr[k + 1]) {
k = k + 1;
}
if(arr[k] > temp) {
arr[i] = arr[k];
i = k;
}
else break; // 此处直接break的原因是本来就是从最后一个非叶子节点开始比较的，如果没有发生交换就代表已经是大顶堆了
}
arr[i] = temp;
}
根据一个无序数组构建赫夫曼树(首先要排序再构建，原理是wpl最小)
import lombok.Data;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class HuffmanTreeDemo {
public static void main(String[] args) {
int[] arr = new int[]{13, 9, 8, 2, 3, 6, 0, 15};
//直接根据这个数组构建赫夫曼树，最小wpl
HuffmanTree huffmanTree = new HuffmanTree(arr);
huffmanTree.createHuffmanTree();
huffmanTree.preList();
}
}
class HuffmanTree {
private Node root;
private List list;
public HuffmanTree(int[] arr) {
list = new ArrayList<>();
for(int ele: arr) {
list.add(new Node(ele));
}
}
public void createHuffmanTree() {
while(list.size() > 1) {
Collections.sort(list);
Node left = list.remove(0);
Node right = list.remove(0);
Node parent = new Node(left.getVal() + right.getVal());
parent.setLeft(left);
parent.setRight(right);
list.add(parent);
}
this.root = list.get(0);
}
public void preList() {
if(this.root == null) return;
this.root.preList();
}
}
@Data
class Node implements Comparable{
private int val;
private Node left;
private Node right;
public Node(int val) {
this.val = val;
}
//前序遍历
public void preList() {
System.out.println(this);
if(this.left != null) this.left.preList();
if(this.right != null) this.right.preList();
}
@Override
public String toString() {
return "Node{" +
"val=" + val +
'}';
}
@Override
public int compareTo(Node o) {
return this.val - o.val;
}
}
今天复习的比较少了~~明天再继续赫夫曼编解码及AVL平衡二叉树
