九、哈希表

9.1 、哈希表(散列)-Google 上机题

1) 看一个实际需求，google 公司的一个上机题:

2) 有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址..),当输入该员工的id 时,要求查找到该员工的所有信息.

3) 要求: 不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列)

9.2、哈希表的基本介绍

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

9.3 、google 公司的一个上机题:

要求:

1) 不使用数据库,,速度越快越好=>哈希表(散列)

2) 添加时，保证按照 id 从低到高插入 [课后思考：如果 id 不是从低到高插入，但要求各条链表仍是从低到高，怎么解决?] 3) 使用链表来实现哈希表, 该链表不带表头[即: 链表的第一个结点就存放雇员信息]

4) 思路分析并画出示意图

5）代码实现

/**
 * description
 * 哈希表案例的测试
 *
 * @author xujicheng
 * @date 2022年11月30日 10:18
 */
public class HashTableDemo {
    public static void main(String[] args) {
        //创建哈希表
        HashTable hashTable = new HashTable(7);

        //写一个简单的菜单来测试
        String key = "";
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("add：添加雇员");
            System.out.println("list：显示雇员");
            System.out.println("find: 查找雇员");
            System.out.println("delete: 删除雇员");
            System.out.println("exit：退出系统");
            key = scanner.next();
            switch (key) {
                case "add":
                    System.out.println("输入id");
                    int id = scanner.nextInt();
                    System.out.println("输入名字");
                    String name = scanner.next();
                    //创建雇员
                    Emp emp = new Emp(id, name);
                    hashTable.add(emp);
                    break;
                case "list":
                    hashTable.list();
                    break;
                case "find":
                    System.out.println("请输入要查找的id");
                    id = scanner.nextInt();
                    hashTable.findEmpById(id);
                    break;
                case "delete":
                    System.out.println("请输入要删除的id");
                    id = scanner.nextInt();
                    hashTable.deleteEmpById(id);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                    break;
                default:
                    break;
            }
        }
    }
}

/**
 * description
 * 哈希表,管理多条链表
 *
 * @author xujicheng
 * @date 2022年11月30日 10:45
 */
public class HashTable {

    private EmpLinkedList[] empLinkedListArray;

    private int size;  //表示共有多少条链表

    /**
     * 构造器
     *
     * @param size 数组大小
     */
    public HashTable(int size) {
        this.size = size;
        //初始化empLinkedListArray
        empLinkedListArray = new EmpLinkedList[size];
        //不要忘了初始化每个链表
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i] = new EmpLinkedList();
        }
    }

    /**
     * 添加雇员
     *
     * @param emp 雇员
     */
    public void add(Emp emp) {
        //根据雇员的id得到该员工应当添加到哪条链表
        int empLinkedListNo = hashFun(emp.id);
        //将emp 添加到对应的链表中
        empLinkedListArray[empLinkedListNo].add(emp);
    }

    //遍历所有的链表,遍历哈希表
    public void list() {
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i].List(i);
        }
    }

    //编写散列函数，使用取模法
    public int hashFun(int id) {
        return id % size;
    }

    //根据输入的id查找雇员
    public void findEmpById(int id) {
        //使用散列函数确定到哪条链表查找
        int empLinkedListNO = hashFun(id);
        Emp emp = empLinkedListArray[empLinkedListNO].findEmpById(id);
        if (emp != null) { //找到
            System.out.printf("在第%d 条链表中找到 雇员 id = %d\n", (empLinkedListNO + 1), id);
        } else {
            System.out.println("在哈希表中没有找到该雇员");
        }
    }

    public void deleteEmpById(int id) {
        //使用散列函数确定到哪条链表查找
        int empLinkedListNO = hashFun(id);
        //从对应的链表中删除
        empLinkedListArray[empLinkedListNO].deleteEmpById(id);
    }
}


/**
 * description
 * 表示一个雇员
 *
 * @author xujicheng
 * @date 2022年11月30日 10:21
 */
public class Emp {

    public int id;  //id
    public String name; //名字
    public Emp next;  //指向下一个节点的下一个引用，默认为空

    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }
}

/**
 * description
 * 创建一个EmpLinkedList，表示链表
 *
 * @author xujicheng
 * @date 2022年11月30日 10:28
 */
public class EmpLinkedList {

    //头指针，指向第一个Emp，因此我们这个链表的head是直接指向第一个Emp,默认为空
    private Emp head;

    /**
     * 添加雇员到链表
     * 说明:
     * 1、假定当添加雇员时，id是自增的，即id的分配是从小到大
     * 2、因此我们将雇员直接加入到本链表的最后即可
     *
     * @param emp 雇员
     */
    public void add(Emp emp) {
        //如果是添加第一个雇员
        if (head == null) {
            head = emp;
            return;
        }
        //如果不是添加第一个雇员，则使用一个辅助的指针帮助我们定位到最后
        Emp curEmp = head;
        while (true) {
            if (curEmp.next == null) { //说明到链表最后
                break;
            }
            curEmp = curEmp.next; //后移，直到到最后
        }
        //退出时直接将emp加到最后即可
        curEmp.next = emp;
    }

    //遍历链表的雇员信息
    public void List(int no) {
        if (head == null) { //说明链表为空
            System.out.println("第 " + (no + 1) + " 链表为空");
            return;
        }
        System.out.print("第 " + (no + 1) + " 链表的信息为");
        Emp curEmp = head;  //辅助指针
        while (true) {
            System.out.printf("=> id=%d name=%s\t", curEmp.id, curEmp.name);
            if (curEmp.next == null) { //说明链表已经到最后了
                break;
            }
            curEmp = curEmp.next;  //让curEmp后移
        }
        System.out.println();   //换行
    }

    /**
     * 根据id查找雇员
     *
     * @param id id
     * @return 找到就返回雇员对象，找不到就返回空
     */
    public Emp findEmpById(int id) {
        //先判断链表是否为空
        if (head == null) { //说明链表为空
            System.out.println("链表为空");
            return null;
        }
        //辅助指针
        Emp curEmp = head;
        while (true) {
            if (curEmp.id == id) { //找到
                return curEmp;   //这时curEmp就指向要查找的雇员
            }
            //退出条件
            if (curEmp.next == null) { //说明遍历当前链表没有找到该雇员
                curEmp = null;
                break;
            }
            curEmp = curEmp.next;  //后移，继续判断
        }
        return curEmp;
    }

    /**
     * 根据雇员id删除雇员
     * 删除思路：
     * 1、head节点不能动，因此我们需要辅助节点找到待删除节点的前一个节点
     * 2、我们在比较时，是head.next.id 和需要删除的节点的id进行比较
     *
     * @param id 需要删除的雇员id
     * @return
     */
    public void deleteEmpById(int id) {

        //先判断链表是否为空
        if (head == null) {
            System.out.println("没有找到第" + id + "号员工");
            return;
        }
        if (head.id == id) {
            //如果头节点的id等于要删除的id，则头节点指向下一个
            head = head.next;
            return;
        }

        Emp curEmp = head;
        boolean flag = false;  //标识
        while (true) {
            if (curEmp.next == null) {  //说明已经到了链表的最后
                break;
            }
            if (curEmp.next.id == id) {
                //说明找到了待删除节点的前一个节点
                flag = true;
                break;
            }
            curEmp = curEmp.next;  //后移，实现遍历
        }
        //判断flag
        if (flag) {
            //进行删除操作
            curEmp.next = curEmp.next.next;
        }
    }
}

代码总结：使用哈希表管理链表的方式模拟数据库进行了增删查功能思路都写在代码里了，相当于复习了链表的知识

十、树结构的基础部分

10.1、二叉树

10.1.1 、为什么需要树这种数据结构

1) 数组存储方式的分析

优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。

缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低[示意图]

画出操作示意图：

2) 链式存储方式的分析

优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可，删除效率也很好)。

缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历) 【示意图】

操作示意图：

3) 树存储方式的分析

能提高数据存储，读取的效率, 比如利用 二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度

案例: [7, 3, 10, 1, 5, 9, 12]

分析以二叉排序树来存储数据的效率：

1、查找12，经过两次比较就找到12节点

2、添加13，速度很快

3、删除节点，速度也很快

10.1.2、树示意图

树的常用术语(结合示意图理解):

1) 节点

2) 根节点

3) 父节点

4) 子节点

5) 叶子节点 (没有子节点的节点)

6) 节点的权(节点值)

7) 路径(从 root 节点找到该节点的路线)

8) 层

9) 子树

10) 树的高度(最大层数)

11) 森林 :多颗子树构成森林

10.1.3、二叉树的概念

1) 树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。

2) 二叉树的子节点分为左节点和右节点

3) 示意图

4) 如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1 , n 为层数，则我们称为满二叉树

5) 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树

10.1.4、二叉树遍历的说明

使用前序，中序和后序对下面的二叉树进行遍历.

1) 前序遍历: 先输出父节点，再遍历左子树和右子树

2) 中序遍历: 先遍历左子树，再输出父节点，再遍历右子树

3) 后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点

4) 小结: 看输出父节点的顺序，就确定是前序，中序还是后序

10.1.5 、二叉树遍历应用实例(前序,中序,后序)

二叉树遍历的要求如下：

1）使用前序、中序、后序遍历，请写出各组的输出顺序是什么

2）在三号节点 "卢俊义"，添加一个左子节点 [5, 关胜]，再使用前序、中序、后序输出的顺序是什么

应用实例的说明和思路

分析二叉树的前序、中序、后序的遍历步骤

1、创建一颗二叉树

2、前序遍历

2.1、先输出当前节点(初始的时候是root节点)

2.2、如果左子节点不为空，则递归继续前序遍历

2.3、如果右子节点不为空，则递归继续前序遍历

3、中序遍历

3.1、如果当前节点的左子节点不为空，则递归中序遍历

3.2、输出当前节点

3.3、如果当前节点的右子节点不为空，则递归中序遍历

4、后序遍历

4.1、如果左子节点不为空，则递归后序遍历

4.2、如果右子节点不为空，则递归后序遍历

4.3、输出当前节点

代码实现如下：

/**
 * description
 * 创建HeroNode节点——英雄类
 *
 * @author xujicheng
 * @since 2022年12月01日 15:21
 */
public class HeroNode {

    private int no; //编号
    private String name; //名字
    private HeroNode left;  //指向左边的节点的指针,默认为null
    private HeroNode right;  //指向右边的节点的指针，默认为null

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    //编写前序遍历的方法
    public void preOrder() {
        System.out.println(this);  //先输出父节点
        //递归向左子树前序遍历
        if (this.left != null) {  //左子树不为空的情况下才能遍历
            this.left.preOrder();
        }
        //递归向右子树前序遍历
        if (this.right != null) { //右子树不为空的情况下才能遍历
            this.right.preOrder();
        }
    }

    //编写中序遍历的方法
    public void infixOrder() {
        //递归向左子树中序遍历
        if (this.left != null) {
            this.left.infixOrder();
        }
        //输出当前节点（父节点）
        System.out.println(this);
        //递归向右子树中后序遍历
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    //编写后序遍历的方法
    public void postOrder() {
        //递归向左子树的后序遍历
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        //输出当前节点（父节点）
        System.out.println(this);
    }
}

/**
 * description
 * 定义二叉树
 *
 * @author xujicheng
 * @since 2022年12月01日 16:46
 */
public class BinaryTree {

    //二叉树最重要的是根节点
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    //前序遍历
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("当前二叉树为空，无法遍历");
        }
    }

    //中序遍历
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("当前二叉树为空，无法遍历");
        }
    }

    //后序遍历
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("当前二叉树为空，无法遍历");
        }
    }
}

/**
 * description
 * 实现二叉树前序、中序、后序的遍历
 *
 * @author xujicheng
 * @since 2022年12月01日 15:20
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        //测试之前首先需要创建一颗二叉树
        BinaryTree binaryTree = new BinaryTree();
        //创建需要的节点
        HeroNode root = new HeroNode(1,"宋江");
        HeroNode heroNode2 = new HeroNode(2,"吴用");
        HeroNode heroNode3 = new HeroNode(3,"卢俊义");
        HeroNode heroNode4 = new HeroNode(4,"林冲");

        //说明：先手动创建该二叉树，以后用递归方式创建
        root.setLeft(heroNode2);   //root这个节点左边挂上了heroNode2
        root.setRight(heroNode3);  //root这个节点右边边挂上了heroNode3
        heroNode3.setRight(heroNode4); //heroNode3这个节点右边挂上了heroNode4
        binaryTree.setRoot(root);  //把root节点给到二叉树

        //测试前序遍历
        System.out.println("前序遍历");
        binaryTree.preOrder();

        //测试中序遍历
        System.out.println("中序遍历");
        binaryTree.infixOrder();

          //测试后序遍历
        System.out.println("后序遍历");
        binaryTree.postOrder();
}

代码执行结果如下：

1）第一个要求：

完成了前序中序后序遍历二叉树的测试，前序、中序、后序的输出顺序如下图

2）第二个要求，添加节点后输出顺序

添加后的输出结果为：

得出结论：

二叉树最重要的是根节点，我们定义了跟节点之后可以根据构造器去进行完成二叉树遍历的操作

10.1.6、二叉树-查找指定节点

1) 请编写前序查找，中序查找和后序查找的方法。

2) 并分别使用三种查找方式，查找 heroNO = 5 的节点

3) 并分析各种查找方式，分别比较了多少次

4) 思路分析图解

使用前序、中序、后序的方式来查询指定的节点

前序查找思路：

1、先判断当前节点的no是否等于要查找的
2、如果是相等，则返回当前节点
3、如果不相等，则判断当前节点的左子节点是否为空，如果不为空，则递归前序擦或者
4、如果左递归前序查找，找到节点，则返回，否则继续判断，当前节点的右子节点是否为空，如果不为空，则继续向右递归前序查找

中序查找思路：

1、先判断当前节点的左子节点是否为空，如果不为空，则进行左递归的中序查找
2、如果找到，则返回，如果没有找到，就和当前节点比较，如果是则返回当前节点，否则继续进行右递归的中序查找
3、如果右递归中序查找，找到就返回，否则返回null

后序查找思路：

1、判断当前节点的左节点是否为空，如果不为空，则进行左递归后序查找
2、如果找到，就返回，如果没有找到，就判断当前节点的右子节点是否为空，如果不为空，则右递归进行后序查找，如果找到，就返回；
3、就和当前节点进行比较，如果是则返回，否则返回null

5) 代码实现

在HeroNode类中添加前序、中序、后序的查找方法的具体逻辑

/**
     * 前序遍历查找的方法
     *
     * @param no 需要查找的编号
     * @return 如果找到返回该节点，没有找到返回null即可
     */
    public HeroNode preOrderSearch(int no) {
         System.out.println("进入前序遍历"); //用于测试前序遍历一共比较了几次
        //比较当前节点是否为要寻找的节点
        if (this.no == no) {
            return this;
        }

        HeroNode result = null;  //初始化结果节点
        //如果不是则判断当前节点的左子节点是否为空，如果不为空，则左递归前序查找
        if (this.left != null) {
            result = this.left.preOrderSearch(no);
        }
        if (result != null) { //返回的结果若不为空说明左子树上找到了
            return result;
        }
        //如果左递归前序查找没有找到节点，则继续判断，判断当前节点的右子节点是否为空，不为空继续向右递归
        if (this.right != null) {
            result = this.right.preOrderSearch(no);
        }
        return result;
    }

    /**
     * 中序遍历查找的方法
     *
     * @param no 需要查找的编号
     * @return 如果找到返回该节点，没有找到返回null即可
     */
    public HeroNode infixOrderSearch(int no) {
        HeroNode result = null;  //初始化结果节点
        //先判断当前节点的左子节点是否为空，如果不为空，则进行左递归中序查找
        if (this.left != null) {
            result = this.left.infixOrderSearch(no);
        }
        //判断向左递归进行中序查找的节点是否为空,找到则返回当前对象
        if (result != null) {
            return result;
        }
        System.out.println("进入中序遍历"); //用于测试中序遍历一共比较了几次
        //若没有找到，就比较当前节点是否为要寻找的节点，如果是则返回当前对象
        if (this.no == no) {
            return this;
        }
        //若比较不为需要寻找的节点，就进行右递归中序查找,找到就返回，否则返回此对象即可
        if (this.right != null) {
            result = this.right.infixOrderSearch(no);
        }
        return result;
    }

    /**
     * 后序遍历查找的方法
     *
     * @param no 需要查找的编号
     * @return 如果找到返回该节点，没有找到返回null即可2
     */
    public HeroNode postOrderSearch(int no) {
        HeroNode result = null;  //初始化结果节点
        //判断当前节点的左节点是否为空，如果不为空，则进行左递归后序查找
        if (this.left != null) {
            result = this.left.postOrderSearch(no);
        }
        //若向左递归已经找到了就返回当前对象即可
        if (result != null) {
            return result;
        }
        //如果左子树没有找到，则向右子树进行后序遍历查找
        if (this.right != null) {
            result = this.right.postOrderSearch(no);
        }
        //若向右递归已经找到了就返回当前对象即可
        if (result != null) {
            return result;
        }
        System.out.println("进入后序遍历"); //用于测试后序遍历一共比较了几次
        //若左右递归子树都没有找到，就比较当前节点是不是需要找的节点
        if (this.no == no) {
            return this;
        }
        return result;
    }

在BinaryTree类中去调用

/**
     * 前序遍历查找的方法
     *
     * @param no 需要查找的编号
     * @return 如果找到返回该节点，没有找到返回null即可
     */
    public HeroNode preOrderSearch(int no) {
        //如果头节点不等于空，就调用前序遍历查找的方法即可
        if (root != null) {
            return root.preOrderSearch(no);
        } else { //若为空，说明这是空子树，直接返回null即可
            return null;
        }
    }

    /**
     * 中序遍历查找的方法
     *
     * @param no 需要查找的编号
     * @return 如果找到返回该节点，没有找到返回null即可
     */
    public HeroNode inOrderSearch(int no) {
        //如果头节点不等于空，就调用中序遍历查找的方法即可
        if (root != null) {
            return root.infixOrderSearch(no);
        } else { //若为空，说明这是空子树，直接返回null即可
            return null;
        }
    }

    /**
     * 后序遍历查找的方法
     *
     * @param no 需要查找的编号
     * @return 如果找到返回该节点，没有找到返回null即可2
     */
    public HeroNode postOrderSearch(int no) {
        //如果头节点不等于空，就调用后序遍历查找的方法即可
        if (root != null) {
            return root.postOrderSearch(no);
        } else { //若为空，说明这是空子树，直接返回null即可
            return null;
        }
    }

分别使用三种查找方式，查找 heroNO = 5 的节点，并分析各种查找方式，分别比较了多少次

        System.out.println("前序遍历查找方式");
        HeroNode result = binaryTree.preOrderSearch(5);
        if (result != null) {
            System.out.printf("找到了，信息为no = %d name=%s", result.getNo(), result.getName());
        } else {
            System.out.printf("没有找到为no = %d 的英雄", 5);
        }

        System.out.println("中序遍历查找方式");
        HeroNode result2 = binaryTree.inOrderSearch(5);
        if (result2 != null) {
            System.out.printf("找到了，信息为no = %d name=%s", result2.getNo(), result2.getName());
        } else {
            System.out.printf("没有找到为no = %d 的英雄", 5);
        }

        System.out.println("后序遍历查找方式");
        HeroNode result3 = binaryTree.postOrderSearch(5);
        if (result3 != null) {
            System.out.printf("找到了，信息为no = %d name=%s", result3.getNo(), result3.getName());
        } else {
            System.out.printf("没有找到为no = %d 的英雄", 5);
        }
    }

输出结果如下：

以下是前序查找的比较次数，是四次

以下是中序查找的比较次数，是三次

以下是后序查找的比较次数，是两次

10.1.7、二叉树-删除节点

1) 如果删除的节点是叶子节点，则删除该节点

2) 如果删除的节点是非叶子节点，则删除该子树.

3) 测试，删除掉 5 号叶子节点和 3 号子树.

4) 完成删除思路分析

思路分析

完成删除节点的操作

规定：

1）如果删除的节点是叶子节点，则删除该节点

2）如果删除的节点是非叶子节点，则删除该子树

思路：

首先先处理：

考虑如果树是空树 root ，如果只有一个root节点，则等价将二叉树置空

然后进行下面步骤：

1、因为我们的二叉树是单向的，所以我们是判断当前节点的子节点是需要删除节点，而不能去判断当前这个节点是不是需要删除的节点

2、如果当前节点的左子节点不为空，并且左子节点就是要删除节点就将this.left = null；并且就返回（结束递归删除）

3、如果当前节点的右子节点不为空，并且右子节点就是要删除节点就将this.right= null；并且就返回（结束递归删除）

4、如果第二步和第三步没有删除节点，那么我们就需要向左子树进行递归删除

5、如果第四步也没有删除节点，则应当向右子树进行递归删除

5) 代码实现

在HeroNode类中添加前序、中序、后序的删除方法的具体逻辑
    /**
     * 递归删除节点
     * 1、说明：如果删除的节点是叶子节点，则删除该节点
     * 2、如果删除的节点是非叶子节点，则删除该子树
     *
     * @param no 需要删除的节点编号
     */
    public void deleteNode(int no) {
        //首先判断左子节点是否等于要删除的节点
        if (this.left != null && this.left.no == no) {
            this.left = null;
            return;
        }
        //如果右子节点不为空，并且右子节点就是要删除的节点，就将this.right = null；并且返回结束
        if (this.right != null && this.right.no == no) {
            this.right = null;
            return;
        }
        //以上两步都没有删除节点，我们就需要向左子树进行递归删除
        if (this.left != null) {
            this.left.deleteNode(no);
        }
        //向左子树递归也没有删除节点，那么就向右子树递归删除
        if (this.right != null) {
            this.right.deleteNode(no);
        }
    }
在BinaryTree类中去调用
 /**
     * 删除节点的方法
     *
     * @param no 需要进行删除的节点
     */
    public void deleteNode(int no) {
        if (root != null){
            //如果只有一个root节点，需要立即判断root是不是就是要删除的节点
            if (root.getNo() == no){
                root = null;
            }else {
                //若root不是要删除的节点，就进行递归删除即可
                root.deleteNode(no);
            }
        }else {
            System.out.println("空树，不能删除");
        }
    }
测试，删除掉 5 号叶子节点和 3 号子树.
         //测试删除节点的代码
        System.out.println("删除前，前序遍历");
        binaryTree.preOrder();
        binaryTree.deleteNode(5);
        System.out.println("删除后，前序遍历");
        binaryTree.preOrder();
删除叶子节点5，输出结果如下

删除三号子树，输出结果如下

10.1.8 二叉树-删除节点——课后思考题

思考题(课后练习)

1) 如果要删除的节点是非叶子节点，现在我们不希望将该非叶子节点为根节点的子树删除，需要指定规则, 假如规定如下:

2) 如果该非叶子节点 A 只有一个子节点 B，则子节点 B 替代节点 A

3) 如果该非叶子节点 A 有左子节点 B 和右子节点 C，则让左子节点 B 替代节点 A。

4) 思考，如何完成该删除功能

思路分析：

在删除节点前做一个判断，查看被删除节点下是否只有一个子节点，再判断子节点下也没有叶子节点，经过判断之后再使用辅助指针将需要删除的节点删除，再将被删除子节点下的叶子节点上提提即可。

代码实现：

    /**
     * 递归删除节点
     * 1、说明：如果删除的节点是叶子节点，则删除该节点
     * 2、如果删除的节点是非叶子节点，则删除该子树
     *
     * @param no 需要删除的节点编号
     */
    public void deleteNode(int no) {
        //首先判断左子节点是否为空并且判断是否等于要删除的节点
        if (this.left != null && this.left.no == no) {
            HeroNode tempNode = this.left.right;   //定义一个辅助指针用于将被删除的子节点底下的叶子节点上提
            //若被删除的节点的左子节点下的左子节点不为空，则将左子节点下的左叶子节点直接返回
            if (this.left.left != null) {
                this.setLeft(this.left.left);  //当前节点的左节点下的左节点
                this.left.setRight(tempNode);  //当前左节点下的右节点重新指向指针
                return;
            }
            //若被删除的节点的左子节点下的右子节点不为空，则将右子节点下的右叶子节点直接返回
            if (this.left.right != null) {
                this.setLeft(this.left.right); //当前节点的左节点下的右叶子节点
                return;
            }
            this.left = null;  //若以上都没有找到要删除的节点就将当前节点的左节点置空
            return;
        }
        //判断右子节点是否为空并且判断是否等于要删除的节点
        if (this.right != null && this.right.no == no) {
            HeroNode tempNode1 = this.right.right; //定义一个辅助指针用于将被删除的子节点底下的叶子节点上提
             //若被删除的节点的右子节点下的左子节点不为空，则将右子节点下的左叶子节点直接返回
            if (this.right.left != null) {
                this.setRight(this.right.left); //当前节点的右节点下的左节点
                this.right.setRight(tempNode1); //当前右节点下的右节点重新指向指针
                return;
            }
            //若被删除的节点的右子节点下的右子节点不为空，则将右子节点下的右叶子节点直接返回
            if (this.right.right != null) {
                this.setRight(this.right.right); //当前节点的右节点下的右叶子节点
                return;
            }
            this.right = null;  //若以上都没有找到要删除的节点就将当前节点的右节点置空
            return;
        }
        //以上步骤都没有删除节点，我们就需要向左子树进行递归删除
        if (this.left != null) {
            this.left.deleteNode(no);
        }
        //以上步骤都没有删除节点，我们就需要向右子树进行递归删除
        if (this.right != null) {
            this.right.deleteNode(no);
        }
    }

输出结果如下：

10.2 、顺序存储二叉树

10.2.1、顺序存储二叉树的概念

基本说明

从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组，看右面的示意图。

要求:

1) 右图的二叉树的结点，要求以数组的方式来存放 arr : [1, 2, 3, 4, 5, 6, 6]

2) 要求在遍历数组 arr 时，仍然可以以前序遍历，中序遍历和后序遍历的方式完成结点的遍历

顺序存储二叉树的特点:

1) 顺序二叉树通常只考虑完全二叉树

2) 第 n 个元素的左子节点为 2 * n + 1

3) 第 n 个元素的右子节点为 2 * n + 2

4) 第 n 个元素的父节点为 (n-1) / 2

5) n : 表示二叉树中的第几个元素(按 0 开始编号如图所示)

10.2.2、顺序存储二叉树遍历

前序遍历完成顺序存储的应用实例

需求: 给你一个数组 {1,2,3,4,5,6,7}，要求以二叉树前序遍历的方式进行遍历。前序遍历的结果应当为1,2,4,5,3,6,7

思路分析如下：

1、首先定义一个方法用于完成顺序存储二叉树的前序遍历
2、对需要排序的数组进行非空判断，若数组为空或数据为空无需向下执行
3、对数组下标做出逻辑判断，防止下标越界的问题，左右递归都需要进行逻辑判断，防止下标越界
4、再根据顺序二叉树左节点的公式去完成向左递归遍历公式 = 2 * n + 1
5、再根据顺序二叉树左节点的公式去完成向右递归遍历公式 = 2 * n + 2

代码实现:

/**
 * description
 * 编写一个 ArrayBinaryTree ，实现顺序存储二叉树遍历
 *
 * @author xujicheng
 * @since 2022年12月03日 10:30
 */
public class ArrayBinaryTree {

    private int[] arr; //存储数据节点的数组

    //构造器，用于传递数组以进行排序
    public ArrayBinaryTree(int[] arr) {
        this.arr = arr;
    }

    //重载preOrder方法
    public void preOrder() {
        this.preOrder(0);
    }

    /**
     * 编写一个方法完成顺序存储二叉树的一个前序遍历
     *
     * @param index 表示数组的下标
     */
    public void preOrder(int index) {
        //如果数组为空或者arr.length=0，即非空判断，没有数据无需遍历
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空，无法进行二叉树前序遍历");
        }
        //输出当前元素
        System.out.print(" " + arr[index]);
        //向左递归遍历,做一个判断防止index越界的问题
        if ((index * 2 + 1) < arr.length) {
            preOrder(2 * index + 1);
        }
        //向右递归遍历，也要做一个判断防止index越界
        if ((2 * index + 2) < arr.length) {
            preOrder(2 * index + 2);
        }
    }
}

/**
 * description
 * 以数组的方式存储二叉树并且完成前序遍历
 *
 * @author xujicheng
 * @since 2022年12月03日 10:27
 */
public class ArrBinaryTreeDemo {
    public static void main(String[] args) {
        //首先定义好需要排序的数组
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        //创建一个ArrayBinaryTree
        ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(arr);
        System.out.println("前序遍历输出结果为：");
        arrayBinaryTree.preOrder();
    }
}

输出结果如下：

中序遍历完成顺序存储的应用实例

需求: 给你一个数组 {1,2,3,4,5,6,7}，要求以二叉树中序遍历的方式进行遍历。中序遍历的结果应当为[2，4，5，1，3，6，7]

思路分析：

1、首先定义一个方法用于完成顺序存储二叉树的中序遍历
2、对需要排序的数组进行非空判断，若数组为空或数据为空无需向下执行
3、对数组下标做出逻辑判断，防止下标越界的问题，左右递归都需要进行逻辑判断，防止下标越界
4、再根据顺序二叉树左节点的公式去完成向左递归遍历公式 = 2 * n + 1
5、再根据顺序二叉树左节点的公式去完成向右递归遍历公式 = 2 * n + 2

顺序存储中序遍历的代码实现如下

/**
 * description
 * 编写一个 ArrayBinaryTree ，实现顺序存储二叉树遍历
 *
 * @author xujicheng
 * @since 2022年12月03日 10:30
 */
public class ArrayBinaryTree {

    private int[] arr; //存储数据节点的数组

    //构造器，用于传递数组以进行排序
    public ArrayBinaryTree(int[] arr) {
        this.arr = arr;
    }

    //重载infixOrder方法
    public void infixOrder() {
        this.infixOrder(0);
    }

    /**
     * 编写一个方法完成顺序存储二叉树的一个中序遍历
     *
     * @param index 表示数组的下标
     */
    public void infixOrder(int index) {
        //首先对需要排序数组进行非空判断，若数组为空无需向下执行
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空，无法进行二叉树中序遍历");
        }
        //向左递归遍历,做一个判断防止index越界的问题
        if ((2 * index + 1) < arr.length) {
            infixOrder(2 * index + 1);
        }

        //输出当前元素
        System.out.print(" " + arr[index]);

        //向右递归遍历，做一个判断防止index越界的问题
        if ((2 * index + 2) < arr.length) {
            infixOrder(2 * index + 2);
        }
    }
}

/**
 * description
 * 以数组的方式存储二叉树并且完成遍历
 *
 * @author xujicheng
 * @since 2022年12月03日 10:27
 */
public class ArrBinaryTreeDemo {
    public static void main(String[] args) {
        //首先定义好需要排序的数组
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        //创建一个ArrayBinaryTree
        ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(arr);
        System.out.println("中序遍历输出结果为:");
        arrayBinaryTree.infixOrder();
    }
}

输出结果如下：

后序遍历完成顺序存储的应用实例

需求: 给你一个数组 {1,2,3,4,5,6,7}，要求以二叉树后序遍历的方式进行遍历。后序遍历的结果应当为[4 2 5 1 6 3 7]

思路分析：

1、首先定义一个方法用于完成顺序存储二叉树的中序遍历
2、对需要排序的数组进行非空判断，若数组为空或数据为空无需向下执行
3、对数组下标做出逻辑判断，防止下标越界的问题，左右递归都需要进行逻辑判断，防止下标越界
4、再根据顺序二叉树左节点的公式去完成向左递归遍历公式 = 2 * n + 1
5、再根据顺序二叉树左节点的公式去完成向右递归遍历公式 = 2 * n + 2

顺序存储后序遍历的代码实现如下

/**
 * description
 * 编写一个 ArrayBinaryTree ，实现顺序存储二叉树遍历
 *
 * @author xujicheng
 * @since 2022年12月03日 10:30
 */
public class ArrayBinaryTree {

    private int[] arr; //存储数据节点的数组

    //构造器，用于传递数组以进行排序
    public ArrayBinaryTree(int[] arr) {
        this.arr = arr;
    }

    //重载postOrder方法
    public void postOrder(){
        this.postOrder(0);
    }

    /**
     * 编写一个方法完成顺序存储二叉树的一个后序遍历
     *
     * @param index 表示数组的下标
     */
    public void postOrder(int index) {
        //首先对需要排序数组进行非空判断，若数组为空无需向下执行
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空，无法进行二叉树后序遍历");
        }
        //向左递归遍历,做一个判断防止index越界的问题
        if ((2 * index + 1) < arr.length) {
            postOrder(2 * index + 1);
        }
        //向右递归遍历，做一个判断防止index越界的问题
        if ((2 * index + 2) < arr.length) {
            postOrder(2 * index + 2);
        }
        //输出当前元素
        System.out.print(" " + arr[index]);
    }
}

/**
 * description
 * 以数组的方式存储二叉树并且完成遍历
 *
 * @author xujicheng
 * @since 2022年12月03日 10:27
 */
public class ArrBinaryTreeDemo {
    public static void main(String[] args) {
        //首先定义好需要排序的数组
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        //创建一个ArrayBinaryTree
        ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(arr);
        System.out.println("后序遍历的输出结果为:");
        arrayBinaryTree.postOrder();
    }
}

输出结果如下：

10.3 、线索化二叉树

10.3.1 、先看一个问题

将数列 {1, 3, 6, 8, 10, 14 } 构建成一颗二叉树. n+1=7

问题分析:

1) 当我们对上面的二叉树进行中序遍历时，数列为 {8, 3, 10, 1, 6, 14 }

2) 但是 6, 8, 10, 14 这几个节点的左右指针，并没有完全的利用上.

3) 如果我们希望充分的利用各个节点的左右指针，让各个节点可以指向自己的前后节点,怎么办?

4) 解决方案-线索二叉树

10.3.2 、线索二叉树基本介绍

1) n 个结点的二叉链表中含有 n+1 【公式 2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）

2) 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种

3) 一个结点的前一个结点，称为前驱结点

4) 一个结点的后一个结点，称为后继结点

10.3.3 、线索二叉树应用案例

前序线索化二叉树

在这里插入图片描述

/**
 * description
 * 创建HeroNode节点——英雄类
 *
 * @author xujicheng
 * @since 2022年12月01日 15:21
 */
public class HeroNode {

    private int no; //编号
    private String name; //名字
    private HeroNode left;  //指向左边的节点的指针,默认为null
    private HeroNode right;  //指向右边的节点的指针，默认为null

    //规定如果leftType ==0 表示指向的是左子树，如果为1则表示指向的是前驱节点
    private int leftType;
    //规定如果leftType ==0 表示指向的是右子树，如果为1则表示指向的是后继节点
    private int rightType;

    getter、setter、toString方法、构造器...
}

/**
 * description
 * 定义ThreadedBinaryTree ，实现了线索化功能的二叉树
 *
 * @author xujicheng
 * @since 2022年12月01日 16:46
 */
public class ThreadedBinaryTree {

    //二叉树最重要的是根节点
    private HeroNode root;

    //为了实现线索化，需要创建要给指向当前节点的前序节点的指针,在递归进行线索化是总保留前一个节点
    private HeroNode pre = null;

    /**
     * 编写对二叉树进行前序线索化的方法
     *
     * @param node 需要线索化的节点
     */
    public void preOrderThreadedNodes(HeroNode node) {
        //如果节点为空则不需要线索化
        if (node == null) {
            return;
        }
        //1、线索化当前节点,处理当前节点的前驱节点
        if (node.getLeft() == null) {
            //让当前节点的左指针指向前驱节点
            node.setLeft(pre);
            //修改当前节点的左指针的类型,指向的是前驱节点
            node.setLeftType(1);
        }

        //处理后继节点
        if (pre != null && pre.getRight() == null) {
            //让前驱节点的右指针指向当前节点
            pre.setRight(node);
            //修改前驱节点的右指针类型
            pre.setRightType(1);
        }
        //每处理一个节点后，让当前节点是下一个节点的前驱节点
        pre = node;

        //2、向左线索化二叉树
        if (node.getLeftType() == 0) {
            preOrderThreadedNodes(node.getLeft());
        }

        //3、线索化右子树
        if (node.getRightType() == 0) {
            preOrderThreadedNodes(node.getRight());
        }
    }

中序线索化二叉树

应用案例说明：将下面的二叉树，进行中序线索二叉树。中序遍历的数列为 {8, 3, 10, 1, 14, 6}

思路分析: 中序遍历的结果：{8, 3, 10, 1, 14, 6}

说明: 当线索化二叉树后，Node 节点的属性 left 和 right ，有如下情况:

1) left 指向的是左子树，也可能是指向的前驱节点. 比如 ① 节点 left 指向的左子树, 而⑩节点的left 指向的就是前驱节点.

2) right 指向的是右子树，也可能是指向后继节点，比如 ① 节点 right 指向的是右子树，而⑩节点的right 指向的是后继节点.

代码实现

/**
 * description
 * 创建HeroNode节点——英雄类
 *
 * @author xujicheng
 * @since 2022年12月01日 15:21
 */
public class HeroNode {
   
   

    private int no; //编号
    private String name; //名字
    private HeroNode left;  //指向左边的节点的指针,默认为null
    private HeroNode right;  //指向右边的节点的指针，默认为null
    private HeroNode parent;//默认null,父节点的指针（为了后序线索化使用）

    //规定如果leftType ==0 表示指向的是左子树，如果为1则表示指向的是前驱节点
    private int leftType;
    //规定如果leftType ==0 表示指向的是右子树，如果为1则表示指向的是后继节点
    private int rightType;

    getter、setter、toString方法、构造器...
}

    /**
     * 后序线索化二叉树
     *
     * @param node 就是当前需要线索化的结点
     */
    public void postThreadedNodes(HeroNode node) {
   
   
        if (node == null) {
   
   
            return;
        }
        //设置父节点，后序线索化遍历时需要
        if (node.getLeft() != null) {
   
   
            node.getLeft().setParent(node);
        } else if (node.getRight() != null) {
   
   
            node.getRight().setParent(node);
        }
        postThreadedNodes(node.getLeft());
        postThreadedNodes(node.getRight());
        if (node.getLeft() == null) {
   
   
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if (pre != null && pre.getRight() == null) {
   
   
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
    }

10.3.4 、遍历线索化二叉树

前序遍历线索化的二叉树

代码实现如下：

    /**
     * 遍历前序线索化二叉树
     */
    public void preThreadedList() {
        HeroNode node = root;
        while (node != null) {
            System.out.print(node + " ");
            //如果存在左子节点就往左走，否则往右走，此时右指针一定是前序遍历的下一个节点
            if (node.getLeftType() == 0) {
                node = node.getLeft();
            } else {
                node = node.getRight();
            }
        }
    }

输出结果

中序遍历线索化的二叉树

1) 说明：对前面的中序线索化的二叉树，进行遍历

2) 分析：因为线索化后，各个结点指向有变化，因此原来的遍历方式不能使用，这时需要使用新的方式遍历线索化二叉树，各个节点可以通过线型方式遍历，因此无需使用递归方式，这样也提高了遍历的效率。遍历的次序应当和中序遍历保持一致。

3) 代码：
    //遍历线索化二叉树的方法
 public void threadedList(){
     //定义一个变量用于存储临时当前遍历的节点，从root开始
     HeroNode node = root;
     while (node != null){
         //循环的找 leftType == 1的节点，第一个找到的就是8节点，会随着遍历变化和变化
         while (node.getLeftType() == 0){
             node = node.getLeft();
         }
         //打印当前节点
         System.out.println(node);
         //如果当前节点的右指针指向的是后继节点，就一直输出
         while (node.getRightType() == 1){
             //获取到当前节点的后继节点
             node = node.getRight();
             System.out.println(node);
         }
         //替换这个遍历的节点
         node = node.getRight();
     }
 }
输出结果为：

数据结构和算法的笔记（第九部分）

九、哈希表

9.1 、哈希表(散列)-Google 上机题

9.2、哈希表的基本介绍

9.3 、google 公司的一个上机题:

十、树结构的基础部分

10.1、二叉树

10.1.1 、为什么需要树这种数据结构

10.1.2、树示意图

10.1.3、二叉树的概念

10.1.4、二叉树遍历的说明

10.1.5 、二叉树遍历应用实例(前序,中序,后序)

10.1.6、二叉树-查找指定节点

10.1.7、二叉树-删除节点

10.1.8 二叉树-删除节点——课后思考题

10.2 、顺序存储二叉树

10.2.1、顺序存储二叉树的概念

10.2.2、顺序存储二叉树遍历

前序遍历完成顺序存储的应用实例

中序遍历完成顺序存储的应用实例

后序遍历完成顺序存储的应用实例

10.3 、线索化二叉树

10.3.1 、先看一个问题

10.3.2 、线索二叉树基本介绍

10.3.3 、线索二叉树应用案例

前序线索化二叉树

中序线索化二叉树

10.3.4 、遍历线索化二叉树

前序遍历线索化的二叉树

中序遍历线索化的二叉树

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

数据结构和算法的笔记（第九部分）

九、哈希表

9.1 、哈希表(散列)-Google 上机题

9.2、 哈希表的基本介绍

9.3 、google 公司的一个上机题:

十、树结构的基础部分

10.1、 二叉树

10.1.1 、为什么需要树这种数据结构

10.1.2、 树示意图

10.1.3、 二叉树的概念

10.1.4、 二叉树遍历的说明

10.1.5 、二叉树遍历应用实例(前序,中序,后序)

10.1.6、 二叉树-查找指定节点

10.1.7、 二叉树-删除节点

10.1.8 二叉树-删除节点——课后思考题

10.2 、顺序存储二叉树

10.2.1、 顺序存储二叉树的概念

10.2.2、 顺序存储二叉树遍历

前序遍历完成顺序存储的应用实例

中序遍历完成顺序存储的应用实例

后序遍历完成顺序存储的应用实例

10.3 、线索化二叉树

10.3.1 、先看一个问题

10.3.2 、线索二叉树基本介绍

10.3.3 、线索二叉树应用案例

前序线索化二叉树

中序线索化二叉树

10.3.4 、遍历线索化二叉树

前序遍历线索化的二叉树

中序遍历线索化的二叉树

热门文章

最新文章

相关课程

相关电子书

相关实验场景

9.2、哈希表的基本介绍

10.1、二叉树

10.1.2、树示意图

10.1.3、二叉树的概念

10.1.4、二叉树遍历的说明

10.1.6、二叉树-查找指定节点

10.1.7、二叉树-删除节点

10.2.1、顺序存储二叉树的概念

10.2.2、顺序存储二叉树遍历