[数据结构与算法]【记录数据结构复习day4(java)】

昨天的二叉树遍历已添加至原博客

二叉树的删除操作
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<Node> 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<Node>{
    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平衡二叉树