Java数据结构与算法-java数据结构与算法（四）-阿里云开发者社区

Java数据结构与算法-java数据结构与算法（三）https://developer.aliyun.com/article/1469491

哈希表

哈希表的基本介绍

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

技术前景：在还没有缓存产品的时候是如何解决的

图形化实现后的散列表

实现思路就是以数组来做为映射唯一标识，每一个数组内的索引对饮一条链表

举例部门编号就可以理解为数组的值

部门编号：姓名（链表保存的值）

google 上机题

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

要求:

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

思路分析并画出示意图

思路实现

/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.hashtable
 * @className: hashtebDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/1 3:01
 * @version: 1.0
 */
public class hashtebDemo {
    public static void main(String[] args) {
        //创建哈希表
        hashtable hashTab = 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("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);
                    hashTab.add(emp);
                    break;
                case "list":
                    hashTab.list();
                    break;
                case "find":
                    System.out.println("请输入要查找的id");
                    id = scanner.nextInt();
                    hashTab.findEmpById(id);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                default:
                    break;
            }
        }
    }
}
//创建 hashtab 管理多条链表，就是用数组来映射， 哈希表的实现方式有两种
//1. 数组+ 链表
//2。 二叉树
class hashtable {
    //用于映射链表的数组
    private EmpLinkedList[] empLinkedListArrays;
    // 用来 记录长度
    private int size;
//    构造器 初始化
    public hashtable(int size) {
        this.size = size;
        //    初始化 Emplinkedlistarrays
        empLinkedListArrays = new EmpLinkedList[size];
        //   此处 这个时候不要分开初始化每一个链表，我们一次性初始化好
        for (int i = 0; i < size; i++) {
            empLinkedListArrays[i] = new EmpLinkedList();
        }
    }
    //    添加成员
    public void add(Emp emp) {
        //  根据员工id 得到员工应该添加再那个链表
        int emplinkedlistNo = hashFun(emp.id);
        //   将emp 添加对应的链表
        empLinkedListArrays[emplinkedlistNo].add(emp);
    }
    //遍历所有的链表 遍历hashtab
    public void list() {
        for (int i = 0; i < size; i++) {
            empLinkedListArrays[i].list(i);
        }
    }
    //查找id
    public void findEmpById(int id) {
        //       使用散列函数，确定到那条链表
        int empLinkedListNo = hashFun(id);
        Emp empByid = empLinkedListArrays[empLinkedListNo].findEmpByid(id);
        if (empByid == null) {
            System.out.println("并没有找到雇员");
        } else {
            System.out.println("在" + (empLinkedListNo + 1) + "链表中找到雇员,id为=>" + empByid.id);
        }
    }
    //    用取模法来根据id 来算出链表对应映射的id数组
    public int hashFun(int id) {
        return id % size;
    }
}
class Emp {
    public int id;
    public String name;
    public Emp next;
    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }
}
class EmpLinkedList {
    //头指针，执行第一个EMP 因此我们这个链表 的head是直接指向第一个emp
    private Emp head;
    //    添加雇员到列表
//    1. 假定 当添加雇员的时候 id 自增长 即是id的分配总是从小到大，所以我们不需要处理id是否有序的判断，
//    直接添加到当前链表的最后即可
    public void add(Emp emp) {
        //如果头节点是空的那么就将头节点添加，因为是第一个雇员
        if (head == null) {
            head = emp;
            return;
        }
        //    如果头节点不是空的那代表不是第一个，我们需要一个指针指向head节点
        Emp curEmp = head;
        //   之后循环链表到末尾添加
        while (true) {
            //如果进入这个if 那么代表链表到了最后
            if (curEmp == null) {
                break;
            }
            //每次循环将curEmp 后移一直到触发if 执行 break
            curEmp = curEmp.next;
        }
        //   退出循环代表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%dname=%s\t", curEmp.id, curEmp.name);
            if (curEmp.next == null) {
                break;
            }
            curEmp = curEmp.next;
        }
        System.out.println();
    }
    //根据id 查找链表
    public Emp findEmpByid(int id) {
        if (head == null) {
            System.out.println("该链表为空");
            return null;
        }
        Emp curemp = head;
        while (true) {
            if (curemp.id == id) {
                break;
            }
            if (curemp.next == null) {
                System.out.println("此链表没有要查找的雇员");
                break;
            }
            //后移
            curemp = curemp.next;
        }
        return curemp;
    }
}

效果演示

新增与遍历

查找

树的结构学习

二叉树简介

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

二叉树的概念

树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。
二叉树的子节点分为左节点和右节点
如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1 , n 为层数，则我们称为满二叉树。
如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数二
层的叶子节点在右边连续，我们称为完全二叉树

数组

数组存储方式的分析

优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低

画出操作示意图：

链表

链式存储方式的分析

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

删除效率也很好)。

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

操作示意图：

二叉树

树存储方式的分析

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

可以保证数据的插入，删除，修改的速度

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

认识树结构

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

1) 节点  
2) 根节点  
3) 父节点  
4) 子节点  
5) 叶子节点 (没有子节点的节点)  6) 节点的权(节点值)  7) 路径(从 root 节点找到该节点的路线)  8) 层  
6) 子树  
7) 树的高度(最大层数)

森林 :多颗子树构成森林

二叉树遍历的说明

前序遍历: 先输出父节点，再遍历左子树和右子树
中序遍历: 先遍历左子树，再输出父节点，再遍历右子树
后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点
小结: 看输出父节点的顺序，就确定是前序，中序还是后序

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

二叉树遍历代码实例

public static void main(String[] args){
     //  测试，先创建一颗二叉树
        BinaryTree binaryTree = new BinaryTree();
        heroNode root = new heroNode(1, "宋江");
        heroNode node1 = new heroNode(2, "吴用");
        heroNode node2 = new heroNode(3, "卢俊义");
        heroNode node3 = new heroNode(4, "林冲");
        heroNode node4 = new heroNode(5, "关胜");
        //设置头节点
        binaryTree.setHead(root);
        // 此处我们手动的填补二叉树，之后还会有递归的方式填充二叉树
        root.setLeftNode(node1);
        root.setRightNode(node2);
        node2.setRightNode(node3);
        node2.setLeftNode(node4);
        //测试
        ////    前序遍历
        //binaryTree.PreOrder();
        ////中序遍历
        //System.out.println();
        //binaryTree.InfixOrder();
        ////后序遍历
        //System.out.println();
        //binaryTree.PostOrder();
 }    
class BinaryTree {
    //确定根节点
    private heroNode head;
    public void setHead(heroNode head) {
        this.head = head;
    }
    //   前序遍历
    public void PreOrder() {
        if (this.head != null) {
            this.head.PreOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
    //中序遍历
    public void InfixOrder() {
        if (this.head != null) {
            this.head.infixOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
    //后续遍历
    public void PostOrder() {
        if (this.head != null) {
            this.head.postOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
}
class heroNode {
    private int id;
    private String name;
    private heroNode leftNode;
    private heroNode rightNode;
    public heroNode getLeftNode() {
        return leftNode;
    }
    public void setLeftNode(heroNode leftNode) {
        this.leftNode = leftNode;
    }
    public heroNode getRightNode() {
        return rightNode;
    }
    public void setRightNode(heroNode rightNode) {
        this.rightNode = rightNode;
    }
    public heroNode(int id, String name) {
        this.id = id;
        this.name = name;
    }
    public int getId() {
        return id;
    }
    public void setId(int id) {
        this.id = id;
    }
    public String getName() {
        return name;
    }
    @Override
    public String toString() {
        return "heroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
    public void setName(String name) {
        this.name = name;
    }
    //    前序遍历
    public void PreOrder() {
        System.out.println(this);
        if (this.getLeftNode() != null) {
            this.leftNode.PreOrder();
        }
        if (this.getRightNode() != null) {
            this.rightNode.PreOrder();
        }
    }
    //    中序遍历
    public void infixOrder() {
        if (this.leftNode != null) {
            this.leftNode.infixOrder();
        }
        System.out.println(this);
        if (this.rightNode != null) {
            this.rightNode.infixOrder();
        }
    }
    //   后序遍历
    public void postOrder() {
        if (this.leftNode != null) {
            this.leftNode.postOrder();
        }
        if (this.rightNode != null) {
            this.rightNode.postOrder();
        }
        System.out.println(this);
    }
}

二叉树查找思路

请编写前序查找，中序查找和后序查找的方法。
并分别使用三种查找方式，查找 heroNO = 5 的节点
并分析各种查找方式，分别比较了多少次

思路图解

二叉树查找代码示例

为了方便更好的阅读代码，就把节点和树类的查找代码专门的写出来，后面会有全代码的部分

class BinatyTree{
    
    //前序查找
    public heroNode preOrderSearch(int no) {
        if (this.head != null) {
            return this.head.PreOrderSearch(no);
        } else {
            return null;
        }
    }
    //中序查找
    public heroNode infixOrderSearch(int no) {
        if (this.head != null) {
            return this.head.infixOrderSearch(no);
        } else {
            return null;
        }
    }
    //后序查找
    public heroNode postOrderSearch(int no) {
        if (this.head != null) {
            return this.head.postOrderSearch(no);
        } else {
            return null;
        }
    }
}
class heroNode{
    
    //前序查找
    public heroNode preOrderSearch(int no) {
        if (this.head != null) {
            return this.head.PreOrderSearch(no);
        } else {
            return null;
        }
    }
    //中序查找
    public heroNode infixOrderSearch(int no) {
        if (this.head != null) {
            return this.head.infixOrderSearch(no);
        } else {
            return null;
        }
    }
    //后序查找
    public heroNode postOrderSearch(int no) {
        if (this.head != null) {
            return this.head.postOrderSearch(no);
        } else {
            return null;
        }
    }
}

二叉树-删除节点

如果删除的节点是叶子节点，则删除该节点
如果删除的节点是非叶子节点，则删除该子树.
测试，删除掉 5 号叶子节点和 3 号子树.

思路分析

有关二叉树的，遍历，查找，删除的全代码

package com.hyc.DataStructure.tree;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.tree
 * @className: BinaryTreeDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/3 16:47
 * @version: 1.0
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        //  测试，先创建一颗二叉树
        BinaryTree binaryTree = new BinaryTree();
        heroNode root = new heroNode(1, "宋江");
        heroNode node1 = new heroNode(2, "吴用");
        heroNode node2 = new heroNode(3, "卢俊义");
        heroNode node3 = new heroNode(4, "林冲");
        heroNode node4 = new heroNode(5, "关胜");
        //设置头节点
        binaryTree.setHead(root);
        // 此处我们手动的填补二叉树，之后还会有递归的方式填充二叉树
        root.setLeftNode(node1);
        root.setRightNode(node2);
        node2.setRightNode(node3);
        node2.setLeftNode(node4);
        //测试
        ////    前序遍历
        //binaryTree.PreOrder();
        ////中序遍历
        //System.out.println();
        //binaryTree.InfixOrder();
        ////后序遍历
        //System.out.println();
        //binaryTree.PostOrder();
        //System.out.println("前中后查找");
        //System.out.println("开始前序查找");
        //heroNode resNode = binaryTree.preOrderSearch(5);
        //if (resNode != null) {
        //    System.out.printf("找到节点为 no =>%d,名字 name => %s ", resNode.getId(), resNode.getName());
        //} else {
        //    System.out.println("查找失败");
        //}
        //System.out.println("开始中序查找");
        //heroNode resNode = binaryTree.infixOrderSearch(5);
        //if (resNode != null) {
        //    System.out.printf("找到节点为 no =>%d,名字 name => %s ", resNode.getId(), resNode.getName());
        //} else {
        //    System.out.println("查找失败");
        //}
        //System.out.println("开始后序查找");
        //heroNode resNode = binaryTree.postOrderSearch(5);
        //if (resNode != null) {
        //    System.out.printf("找到节点为 no =>%d,名字 name => %s ", resNode.getId(), resNode.getName());
        //} else {
        //    System.out.println("查找失败");
        //}
        //    删除测试
        System.out.println("删除前");
        binaryTree.PreOrder();
        System.out.println("删除后");
        binaryTree.deleteNode(5);
        binaryTree.PreOrder();
    }
}
class BinaryTree {
    //确定根节点
    private heroNode head;
    public void setHead(heroNode head) {
        this.head = head;
    }
    //   前序遍历
    public void PreOrder() {
        if (this.head != null) {
            this.head.PreOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
    //中序遍历
    public void InfixOrder() {
        if (this.head != null) {
            this.head.infixOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
    //后续遍历
    public void PostOrder() {
        if (this.head != null) {
            this.head.postOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
    //前序查找
    public heroNode preOrderSearch(int no) {
        if (this.head != null) {
            return this.head.PreOrderSearch(no);
        } else {
            return null;
        }
    }
    //中序查找
    public heroNode infixOrderSearch(int no) {
        if (this.head != null) {
            return this.head.infixOrderSearch(no);
        } else {
            return null;
        }
    }
    //后序查找
    public heroNode postOrderSearch(int no) {
        if (this.head != null) {
            return this.head.postOrderSearch(no);
        } else {
            return null;
        }
    }
    //    删除节点
    public void deleteNode(int no) {
        if (head != null) {
            if (head.getId() == no) {
                head = null;
                return;
            } else {
                head.deleteNode(no);
            }
        } else {
            System.out.println("空树,无法删除");
        }
    }
}
class heroNode {
    private int id;
    private String name;
    private heroNode leftNode;
    private heroNode rightNode;
    public heroNode getLeftNode() {
        return leftNode;
    }
    public void setLeftNode(heroNode leftNode) {
        this.leftNode = leftNode;
    }
    public heroNode getRightNode() {
        return rightNode;
    }
    public void setRightNode(heroNode rightNode) {
        this.rightNode = rightNode;
    }
    public heroNode(int id, String name) {
        this.id = id;
        this.name = name;
    }
    public int getId() {
        return id;
    }
    public void setId(int id) {
        this.id = id;
    }
    public String getName() {
        return name;
    }
    @Override
    public String toString() {
        return "heroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
    public void setName(String name) {
        this.name = name;
    }
    //    前序遍历
    public void PreOrder() {
        System.out.println(this);
        if (this.getLeftNode() != null) {
            this.leftNode.PreOrder();
        }
        if (this.getRightNode() != null) {
            this.rightNode.PreOrder();
        }
    }
    //    中序遍历
    public void infixOrder() {
        if (this.leftNode != null) {
            this.leftNode.infixOrder();
        }
        System.out.println(this);
        if (this.rightNode != null) {
            this.rightNode.infixOrder();
        }
    }
    //   后序遍历
    public void postOrder() {
        if (this.leftNode != null) {
            this.leftNode.postOrder();
        }
        if (this.rightNode != null) {
            this.rightNode.postOrder();
        }
        System.out.println(this);
    }
    //   前序查找
    public heroNode PreOrderSearch(int no) {
        System.out.println("前序查找");
        //比较当前节点的no 是不是我们要搜索的
        if (this.id == no) {
            return this;
        }
        //要返回的节点
        heroNode resNode = null;
        //  判断左边节点是不是空 如果不是空的话 那么就递归前序查找
        //    如果找到的话 就返回找到的节点
        if (this.leftNode != null) {
            resNode = this.leftNode.PreOrderSearch(no);
        }
        //如果不为null 那么代表左边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        //  判断右边节点是不是空 如果不是空的话 那么就递归前序查找
        //    如果找到的话 就返回找到的节点
        if (this.rightNode != null) {
            resNode = this.rightNode.PreOrderSearch(no);
        }
        return resNode;
    }
    //   中序查找
    public heroNode infixOrderSearch(int no) {
        //要返回的节点
        heroNode resNode = null;
        //  判断左边节点是不是空 如果不是空的话 那么就递归中序查找
        //    如果找到的话 就返回找到的节点
        if (this.leftNode != null) {
            resNode = this.leftNode.infixOrderSearch(no);
        }
        //如果不为null 那么代表左边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        //比较当前节点的no 是不是我们要搜索的
        System.out.println("中序查找");
        if (this.id == no) {
            return this;
        }
        //  判断右边节点是不是空 如果不是空的话 那么就递归中序查找
        //    如果找到的话 就返回找到的节点
        if (this.rightNode != null) {
            resNode = this.rightNode.infixOrderSearch(no);
        }
        return resNode;
    }
    //   后序查找
    public heroNode postOrderSearch(int no) {
        //要返回的节点
        heroNode resNode = null;
        //  判断左边节点是不是空 如果不是空的话 那么就递归后序查找
        //    如果找到的话 就返回找到的节点
        if (this.leftNode != null) {
            resNode = this.leftNode.postOrderSearch(no);
        }
        //如果不为null 那么代表左边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        //  判断右边节点是不是空 如果不是空的话 那么就递归后序查找
        //    如果找到的话 就返回找到的节点
        if (this.rightNode != null) {
            resNode = this.rightNode.postOrderSearch(no);
        }
        //如果不为null 那么代表右边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        System.out.println("后序查找");
        //左右子树，都没有找到，那么就比较当前节点的no 是不是我们要搜索的
        if (this.id == no) {
            return this;
        }
        return resNode;
    }
    //    删除 
    public void deleteNode(int no) {
        //    向左边遍历 如果左边子树有点话就将左边子树置空，如果不是就遍历右边
        if (this.leftNode != null && this.leftNode.id == no) {
            this.leftNode = null;
            return;
        }
        //    向右边遍历 如果右边子树有点话就将左边子树置空，如果左右都没有那么就绪要递归的删除
        if (this.rightNode != null && this.rightNode.id == no) {
            this.rightNode = null;
            return;
        }
        //    如果上面两步都不成功那么我们先向左边递归删除
        if (this.leftNode != null) {
            this.leftNode.deleteNode(no);
        }
        //    如果递归删除左子树也没有成功删除，那么就递归删除右边子树
        if (this.rightNode != null) {
            this.rightNode.deleteNode(no);
        }
    }
}

顺序存储二叉树

顺序存储二叉树的概念

从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组，

上图的二叉树的结点，要求以数组的方式来存放 arr : [1, 2, 3, 4, 5, 6, 6] 2) 要求在遍历数组 arr 时，仍然可以以前序遍历，中序遍历和后序遍历的方式完成结点的遍历

顺序存储二叉树的特点:

顺序二叉树通常只考虑完全二叉树
第 n 个元素的左子节点为 2 * n + 1（计算公式）
第 n 个元素的右子节点为 2 * n + 2 （计算公式）
第 n 个元素的父节点为 (n-1) / 2
n : 表示二叉树中的第几个元素

顺序存储二叉树遍历

需求

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

前序遍历的结果应当为 1,2,4,5,3,6,7

编码思路

这里判断的思路首先是有一个数组转变成树看待的思想，

数组： 1,2,3,4,5,6,7

树（如下图）

第 n 个元素的左子节点为 2 * n + 1（计算公式）
第 n 个元素的右子节点为 2 * n + 2 （计算公式）

我们可以用这个公式来证明一下，数组转树的正确性

比如我们要计算二的位置，2是1的左子节点，1是下标为0的元素 2*0+1 套用公式 = 1，之后的节点同理

代码实现

package com.hyc.DataStructure.tree;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.tree
 * @className: ArrayTreeDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/4 19:07
 * @version: 1.0
 */
public class ArrayTreeDemo {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        ArrayTree arrayTree = new ArrayTree(arr);
        //452 6731
        arrayTree.postOrder(0);
    }
}
class ArrayTree {
    private int[] arr;
    public ArrayTree(int[] arr) {
        this.arr = arr;
    }
    //    顺序存储树的前序遍历
    // 遍历公式 找到n的第n个左结点 n*2+1 找到n的第n个右节点 n*2+2
    // 输入参数 int index 为开始遍历到根节点 即为 数组下标0
    public void preOrder(int index) {
        //非空判断 避免空指针
        if (arr == null || arr.length == 0) {
            System.out.println("该树 为空 不能遍历");
        }
        //    前序遍历先输出自己
        System.out.println(arr[index]);
        //    之后递归遍历左结点
        //判断index 是否越界
        if ((2 * index + 1) < arr.length) {
            preOrder(index * 2 + 1);
        }
        //    之后递归遍历右边结点
        //判断index 是否越界
        if ((2 * index + 2) < arr.length) {
            preOrder(index * 2 + 2);
        }
    }
    public void infixOrder(int index) {
        //非空判断 避免空指针
        if (arr == null || arr.length == 0) {
            System.out.println("该树 为空 不能遍历");
        }
        //    递归遍历左结点
        //判断index 是否越界
        if ((2 * index + 1) < arr.length) {
            infixOrder(index * 2 + 1);
        }
        //    中序遍历输出自己
        System.out.println(arr[index]);
        //    递归遍历右边结点
        //判断index 是否越界
        if ((2 * index + 2) < arr.length) {
            infixOrder(index * 2 + 2);
        }
    }
    public void postOrder(int index) {
        //非空判断 避免空指针
        if (arr == null || arr.length == 0) {
            System.out.println("该树 为空 不能遍历");
        }
        //    递归遍历左结点
        //判断index 是否越界
        if ((2 * index + 1) < arr.length) {
            postOrder(index * 2 + 1);
        }
        //    递归遍历右边结点
        //判断index 是否越界
        if ((2 * index + 2) < arr.length) {
            postOrder(index * 2 + 2);
        }
        //    后序遍历输出自己
        System.out.println(arr[index]);
    }
}

这里我们先了解顺序存储二叉树，并且掌握他的节点计算思路和遍历思路，小冷之后的文章堆排序的时候会进行知识点的使用，提前预热

线索化二叉树

通过一个问题来引入线索化二叉树

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

问题分析:

当我们对上面的二叉树进行中序遍历时，数列为 {8, 3, 10, 1, 6, 14 }
但是 6, 8, 10, 14 这几个节点的左右指针，并没有完全的利用上.
如果我们希望充分的利用各个节点的左右指针，让各个节点可以指向自己的前后节点,怎么办?
解决方案-线索二叉树

线索二叉树基本介绍

n 个结点的二叉链表中含有 n+1 【公式 2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）
这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
一个结点的前一个结点，称为前驱结点
一个结点的后一个结点，称为后继结点

线索二叉树应用案例

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

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

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

代码实现

package com.hyc.DataStructure.tree.ThreadedBinaryTree;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.tree.ThreadedBinaryTree
 * @className: ThreadedBinaryTreeDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/5 16:38
 * @version: 1.0
 */
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        //测试一把中序线索二叉树的功能
        heroNode root = new heroNode(1, "tom");
        heroNode node2 = new heroNode(3, "jack");
        heroNode node3 = new heroNode(6, "smith");
        heroNode node4 = new heroNode(8, "mary");
        heroNode node5 = new heroNode(10, "king");
        heroNode node6 = new heroNode(14, "dim");
        //二叉树，后面我们要递归创建, 现在简单处理使用手动创建
        root.setLeftNode(node2);
        root.setRightNode(node3);
        node2.setLeftNode(node4);
        node2.setRightNode(node5);
        node3.setLeftNode(node6);
        //测试中序线索化
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setHead(root);
        threadedBinaryTree.postThreadedNodes(root);
        //测试: 以10号节点测试
        heroNode leftNode = node5.getLeftNode();
        heroNode rightNode = node5.getRightNode();
        System.out.println("10号结点的前驱结点是 =" + leftNode); //3
        System.out.println("10号结点的后继结点是=" + rightNode); //1
        //当线索化二叉树后，能在使用原来的遍历方法
        //threadedBinaryTree.infixOrder();
        System.out.println("使用线索化的方式遍历 线索化二叉树");
        threadedBinaryTree.preThreaddeList(); // 8, 3, 10, 1, 14, 6
    }
}
class ThreadedBinaryTree {
    //确定根节点
    private heroNode head;
    //递归的时候用来存放上一个节点的变量用于线索化树的遍历和线索化节点
    private heroNode pre;
    public void setHead(heroNode head) {
        this.head = head;
    }
    //线索化遍历
    public void ThreaddeList() {
        //    这里我们需要一个变量，存储当前的节点
        heroNode tempNode = head;
        while (tempNode != null) {
            /* 开始循环遍历
             * 循环找到 lefttype 为 1 的节点来，所以第一个找到的就是节点值为 8 的节点
             * 后面会随着遍历而变化，当找到了 lefttype ==1的时候 说明树已经线索化了
             * 之后只需要处理线索化之后的有效节点即可
             * */
            while (tempNode.getLefttype() == 0) {
                tempNode = tempNode.getLeftNode();
            }
            //    因为是中序遍历， 顺序为 ： 左 中 右 这里我们是从左边的lefttype==1也就是说是左边开头的第一个节点所以直接输出就可以了
            System.out.println(tempNode);
            /* 如果当前节点的右指针指向的是后继节点那么就一直输出
             * */
            while (tempNode.getRighttype() == 1) {
                tempNode = tempNode.getRightNode();
                System.out.println(tempNode);
            }
            // 替换这个遍历的节点
            tempNode = tempNode.getRightNode();
        }
    }
    public void preThreaddeList() {
        //    这里我们需要一个变量，存储当前的节点
        heroNode tempNode = head;
        while (tempNode != null) {
            /* 开始循环遍历
             * 循环找到 lefttype 为 1 的节点来，所以第一个找到的就是节点值为 8 的节点
             * 后面会随着遍历而变化，当找到了 lefttype ==1的时候 说明树已经线索化了
             * 之后只需要处理线索化之后的有效节点即可
             * */
            while (tempNode.getLefttype() == 0) {
                System.out.println(tempNode);
                tempNode = tempNode.getLeftNode();
            }
            //    因为是中序遍历， 顺序为 ： 左 中 右 这里我们是从左边的lefttype==1也就是说是左边开头的第一个节点所以直接输出就可以了
            System.out.println(tempNode);
            // 替换这个遍历的节点
            tempNode = tempNode.getRightNode();
        }
    }
    
    //线索化节点
    public void ThreadedNodes(heroNode node) {
        //       非空判断
        if (node == null) {
            return;
        }
        //    线索化左子树
        ThreadedNodes(node.getLeftNode());
        //    线索化节点
        //不太好理解这里以 8 举例子
        // 8 的left ==null 那么 8 的lefttype = 1 代表他是一个前驱节点
        if (node.getLeftNode() == null) {
            //如果当前节点的左指针是空值那么就将她的left指针指向pre前置节点
            //以8为例子那么当第一次进入方法 pre 是空的 所以 8 是没有前置节点的，自己便是前置节点，所以左指针状态为1
            node.setLeftNode(pre);
            //    指向之后 将type改变为1
            node.setLefttype(1);
        }
        //处理后继节点
        //这里判断的前置节点非空并且前置节点没有后继结点
        if (pre != null && pre.getRightNode() == null) {
            //这里以8 的后一个节点为例子 3当指针指向3 的时候前置节点 pre  = 8这里指向的意思是 8 的rightnode为3
            pre.setRightNode(node);
            //此时后置节点不是子树，并且前置节点的right指针指向了node的时候 改变right 状态 为 1表示为后继节点
            pre.setRighttype(1);
        }
        //每次处理了一个节点之后，我们都需要将他存储到pre也就是前置节点中
        //否则会造成死递归
        pre = node;
        //    线索化右子树
        ThreadedNodes(node.getRightNode());
    }
    //线索化节点
    public void preThreadedNodes(heroNode node) {
        //       非空判断
        if (node == null) {
            return;
        }
        //    线索化节点
        //不太好理解这里以 8 举例子
        // 8 的left ==null 那么 8 的lefttype = 1 代表他是一个前驱节点
        if (node.getLeftNode() == null) {
            //如果当前节点的左指针是空值那么就将她的left指针指向pre前置节点
            //以8为例子那么当第一次进入方法 pre 是空的 所以 8 是没有前置节点的，自己便是前置节点，所以左指针状态为1
            node.setLeftNode(pre);
            //    指向之后 将type改变为1
            node.setLefttype(1);
        }
        //处理后继节点
        //这里判断的前置节点非空并且前置节点没有后继结点
        if (pre != null && pre.getRightNode() == null) {
            //这里以8 的后一个节点为例子 3当指针指向3 的时候前置节点 pre  = 8这里指向的意思是 8 的rightnode为3
            pre.setRightNode(node);
            //此时后置节点不是子树，并且前置节点的right指针指向了node的时候 改变right 状态 为 1表示为后继节点
            pre.setRighttype(1);
        }
        //每次处理了一个节点之后，我们都需要将他存储到pre也就是前置节点中
        //否则会造成死递归
        pre = node;
        if (node.getLefttype() == 0) {
            //    线索化左子树
            preThreadedNodes(node.getLeftNode());
        }
        if (node.getRighttype() == 0) {
            //    线索化右子树
            preThreadedNodes(node.getRightNode());
        }
    }
    //线索化节点
    public void postThreadedNodes(heroNode node) {
        //       非空判断
        if (node == null) {
            return;
        }
        //    线索化左子树
        ThreadedNodes(node.getLeftNode());
        //    线索化右子树
        ThreadedNodes(node.getRightNode());
        //    线索化节点
        //不太好理解这里以 8 举例子
        // 8 的left ==null 那么 8 的lefttype = 1 代表他是一个前驱节点
        if (node.getLeftNode() == null) {
            //如果当前节点的左指针是空值那么就将她的left指针指向pre前置节点
            //以8为例子那么当第一次进入方法 pre 是空的 所以 8 是没有前置节点的，自己便是前置节点，所以左指针状态为1
            node.setLeftNode(pre);
            //    指向之后 将type改变为1
            node.setLefttype(1);
        }
        //处理后继节点
        //这里判断的前置节点非空并且前置节点没有后继结点
        if (pre != null && pre.getRightNode() == null) {
            //这里以8 的后一个节点为例子 3当指针指向3 的时候前置节点 pre  = 8这里指向的意思是 8 的rightnode为3
            pre.setRightNode(node);
            //此时后置节点不是子树，并且前置节点的right指针指向了node的时候 改变right 状态 为 1表示为后继节点
            pre.setRighttype(1);
        }
        //每次处理了一个节点之后，我们都需要将他存储到pre也就是前置节点中
        //否则会造成死递归
        pre = node;
    }
    //   前序遍历
    public void preOrder() {
        if (this.head != null) {
            this.head.PreOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
    //中序遍历
    public void InfixOrder() {
        if (this.head != null) {
            this.head.infixOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
    //后续遍历
    public void PostOrder() {
        if (this.head != null) {
            this.head.postOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }
    //前序查找
    public heroNode preOrderSearch(int no) {
        if (this.head != null) {
            return this.head.PreOrderSearch(no);
        } else {
            return null;
        }
    }
    //中序查找
    public heroNode infixOrderSearch(int no) {
        if (this.head != null) {
            return this.head.infixOrderSearch(no);
        } else {
            return null;
        }
    }
    //后序查找
    public heroNode postOrderSearch(int no) {
        if (this.head != null) {
            return this.head.postOrderSearch(no);
        } else {
            return null;
        }
    }
    //    删除节点
    public void deleteNode(int no) {
        if (head != null) {
            if (head.getId() == no) {
                head = null;
                return;
            } else {
                head.deleteNode(no);
            }
        } else {
            System.out.println("空树,无法删除");
        }
    }
}
class heroNode {
    private int id;
    private String name;
    private heroNode leftNode;
    private heroNode rightNode;
    //如果type 为 0 那么代表还有子树，如果type为1代表是前驱节点/后置节点
    private int lefttype;
    private int righttype;
    public int getLefttype() {
        return lefttype;
    }
    public void setLefttype(int lefttype) {
        this.lefttype = lefttype;
    }
    public int getRighttype() {
        return righttype;
    }
    public void setRighttype(int righttype) {
        this.righttype = righttype;
    }
    public heroNode getLeftNode() {
        return leftNode;
    }
    public void setLeftNode(heroNode leftNode) {
        this.leftNode = leftNode;
    }
    public heroNode getRightNode() {
        return rightNode;
    }
    public void setRightNode(heroNode rightNode) {
        this.rightNode = rightNode;
    }
    public heroNode(int id, String name) {
        this.id = id;
        this.name = name;
    }
    public int getId() {
        return id;
    }
    public void setId(int id) {
        this.id = id;
    }
    public String getName() {
        return name;
    }
    @Override
    public String toString() {
        return "heroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
    public void setName(String name) {
        this.name = name;
    }
    //    前序遍历
    public void PreOrder() {
        System.out.println(this);
        if (this.getLeftNode() != null) {
            this.leftNode.PreOrder();
        }
        if (this.getRightNode() != null) {
            this.rightNode.PreOrder();
        }
    }
    //    中序遍历
    public void infixOrder() {
        if (this.leftNode != null) {
            this.leftNode.infixOrder();
        }
        System.out.println(this);
        if (this.rightNode != null) {
            this.rightNode.infixOrder();
        }
    }
    //   后序遍历
    public void postOrder() {
        if (this.leftNode != null) {
            this.leftNode.postOrder();
        }
        if (this.rightNode != null) {
            this.rightNode.postOrder();
        }
        System.out.println(this);
    }
    //   前序查找
    public heroNode PreOrderSearch(int no) {
        System.out.println("前序查找");
        //比较当前节点的no 是不是我们要搜索的
        if (this.id == no) {
            return this;
        }
        //要返回的节点
        heroNode resNode = null;
        //  判断左边节点是不是空 如果不是空的话 那么就递归前序查找
        //    如果找到的话 就返回找到的节点
        if (this.leftNode != null) {
            resNode = this.leftNode.PreOrderSearch(no);
        }
        //如果不为null 那么代表左边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        //  判断右边节点是不是空 如果不是空的话 那么就递归前序查找
        //    如果找到的话 就返回找到的节点
        if (this.rightNode != null) {
            resNode = this.rightNode.PreOrderSearch(no);
        }
        return resNode;
    }
    //   中序查找
    public heroNode infixOrderSearch(int no) {
        //要返回的节点
        heroNode resNode = null;
        //  判断左边节点是不是空 如果不是空的话 那么就递归中序查找
        //    如果找到的话 就返回找到的节点
        if (this.leftNode != null) {
            resNode = this.leftNode.infixOrderSearch(no);
        }
        //如果不为null 那么代表左边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        //比较当前节点的no 是不是我们要搜索的
        System.out.println("中序查找");
        if (this.id == no) {
            return this;
        }
        //  判断右边节点是不是空 如果不是空的话 那么就递归中序查找
        //    如果找到的话 就返回找到的节点
        if (this.rightNode != null) {
            resNode = this.rightNode.infixOrderSearch(no);
        }
        return resNode;
    }
    //   后序查找
    public heroNode postOrderSearch(int no) {
        //要返回的节点
        heroNode resNode = null;
        //  判断左边节点是不是空 如果不是空的话 那么就递归后序查找
        //    如果找到的话 就返回找到的节点
        if (this.leftNode != null) {
            resNode = this.leftNode.postOrderSearch(no);
        }
        //如果不为null 那么代表左边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        //  判断右边节点是不是空 如果不是空的话 那么就递归后序查找
        //    如果找到的话 就返回找到的节点
        if (this.rightNode != null) {
            resNode = this.rightNode.postOrderSearch(no);
        }
        //如果不为null 那么代表右边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        System.out.println("后序查找");
        //左右子树，都没有找到，那么就比较当前节点的no 是不是我们要搜索的
        if (this.id == no) {
            return this;
        }
        return resNode;
    }
    //    删除
    public void deleteNode(int no) {
        //    向左边遍历 如果左边子树有点话就将左边子树置空，如果不是就遍历右边
        if (this.leftNode != null && this.leftNode.id == no) {
            this.leftNode = null;
            return;
        }
        //    向右边遍历 如果右边子树有点话就将左边子树置空，如果左右都没有那么就绪要递归的删除
        if (this.rightNode != null && this.rightNode.id == no) {
            this.rightNode = null;
            return;
        }
        //    如果上面两步都不成功那么我们先向左边递归删除
        if (this.leftNode != null) {
            this.leftNode.deleteNode(no);
        }
        //    如果递归删除左子树也没有成功删除，那么就递归删除右边子树
        if (this.rightNode != null) {
            this.rightNode.deleteNode(no);
        }
    }
}

遍历线索化二叉树

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

public void preThreaddeList() {
        //    这里我们需要一个变量，存储当前的节点
        heroNode tempNode = head;
        while (tempNode != null) {
            /* 开始循环遍历
             * 循环找到 lefttype 为 1 的节点来，所以第一个找到的就是节点值为 8 的节点
             * 后面会随着遍历而变化，当找到了 lefttype ==1的时候 说明树已经线索化了
             * 之后只需要处理线索化之后的有效节点即可
             * */
            while (tempNode.getLefttype() == 0) {
                System.out.println(tempNode);
                tempNode = tempNode.getLeftNode();
            }
            //    因为是中序遍历， 顺序为 ： 左 中 右 这里我们是从左边的lefttype==1也就是说是左边开头的第一个节点所以直接输出就可以了
            System.out.println(tempNode);
            // 替换这个遍历的节点
            tempNode = tempNode.getRightNode();
        }
    }

红黑树

是一种特殊的平衡二叉树

满足如下几个条件：

1、结点是红色或黑色的
2、根结点始终是黑色的
3、叶子结点也都是黑色的（当红色结点无左右孩子时，补足空结点是黑色的）
4、红色结点的子结点都是黑色的
5、对任一结点，到叶子结点的所有路径，都包含相同数目的黑色结点

特征：从根结点到叶子结点的最长路径，不会超过最短路径的两倍

当插入新结点使红黑树失去平衡时，通过两种方式恢复平衡：

旋转和变色（红变黑黑变红）

可视化网站

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

插入结点到红黑树的逻辑

约定新插入的结点都设为红色的，可以简化树的平衡过程

假设要插入的结点是X 父结点是P 祖父结点是G 叔父结点是U

1）X是根结点
放入根结点中，将颜色变为黑色

2）X的父结点是黑色的

3）X的父结点是红色的

a) 如果叔父结点U也是红色的，可以推断出祖父结点G必是黑色的

当增加新结点时造成两个红色结点相邻此时使用变色处理
P和U由从红色变为黑色 G由黑色变为红色如果G是根结点再次恢复为黑色

b) 如果叔父结点U是黑色的，并且X在左侧

以P为中心，向右旋转，G和U下移，此时如果P有右孩子，右孩子R移动到G的左孩子处
将P变为黑色将G变为红色

此为举例插入16的场景

c) 如果叔父结点U是黑色的，并且X在右侧

先通过左旋恢复成第二种情况然后再右旋和变色

以插入19举例

线段树

认识线段树

序列【1,4,2,3】

给序列的第i个数,加上X A[i]=A[I]+X O(1)
取序列的最大的数,遍历最大值 O(N)
遍历的时候时间复杂度高,怎么处理呢?

线段树Segment Tree

"区间" 线段树是根据区间的性质来构造的

特点:

每次将区间的长度一分为二,区间存储的左右边界 [[start,end]/[left,right]]

如果假设数组的长度 = n 线段树的高度就是 log(n)

将区间中的最大值加入进来,线段树加入值之后就是如下状态

除此之外,可以存储的区间内的最小值,区间求和等等

线段树的节点个数为 n+n/2+n/4... = (1+1/2+1/4...)*n ≈ 2n

构造线段树的时间复杂度和空间复杂度均为 O(n)

线段树创建代码实现

package com.hyc.DataStructure.SegmentTree;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.SegmentTree
 * @className: SegmentTree
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/26 10:15
 * @version: 1.0
 */
public class SegmentTree {
    @Override
    public String toString() {
        return "SegmentTree{" +
                "start=" + start +
                ", end=" + end +
                ", val=" + val +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
    public static void main(String[] args) {
        int[] arr = {1, 4, 2, 3};
        SegmentTree root = SegmentTree.build(arr);
        System.out.println(root);
    }
    //节点区间范围
    public int start, end;
    //    存储节点值
    public int val;
    //    左右子树
    public SegmentTree left;
    public SegmentTree right;
    public SegmentTree(int start, int end, int val) {
        this.start = start;
        this.end = end;
        this.val = val;
    }
    public static SegmentTree build(int[] A) {
        return buildByRecu(0, A.length - 1, A);
    }
    public static SegmentTree buildByRecu(int start, int end, int[] A) {
        if (start > end) {
            return null;
        }
        SegmentTree root = new SegmentTree(start, end, A[start]);
        //    如果是叶子节点 直接返回
        if (start == end) {
            return root;
        }
        //    如果不是那么就以二分的形式来递归创建树
        int mid = (start + end) / 2;
        root.left = buildByRecu(start, mid, A);
        root.right = buildByRecu(mid + 1, end, A);
        //求出区间内最大值为父节点的val
        root.val = Math.max(root.left.val, root.right.val);
        return root;
    }
}

单点更新

public static void modify(SegmentTree root, int index, int value) {
        //    先找到叶子节点,然后逐渐上层
        if (root.start == root.end && root.start == index) {
            root.val = value;
            return;
        }
        int mid = (root.start + root.end) / 2;
        //    判断index 在左子树的区间,还是 右子树的区间,二分思路
        if (index <= mid) {
            modify(root.left, index, value);
            root.val = Math.max(root.left.val, root.right.val);
            return;
        }
        modify(root.right, index, value);
        root.val = Math.max(root.left.val, root.right.val);
    }

搜索线段树

搜索线段树返回索引值

public static int searchByIndex(SegmentTree root, int index) {
        //    先找到叶子节点,然后逐渐上层
        if (root.start == root.end && root.start == index) {
            return root.val;
        }
        int mid = (root.start + root.end) / 2;
        //    判断index 在左子树的区间,还是 右子树的区间,二分思路
        if (index <= mid) {
            searchByIndex(root.left, index);
            return root.val;
        }
        searchByIndex(root.right, index);
        return root.val;
    }

Java数据结构与算法-java数据结构与算法（五）https://developer.aliyun.com/article/1469493

Java数据结构与算法-java数据结构与算法（四）

哈希表

哈希表的基本介绍

google 上机题

思路分析并画出示意图

思路实现

效果演示

新增与遍历

查找

树的结构学习

二叉树简介

数组

链表

二叉树

认识树结构

二叉树遍历的说明

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

二叉树遍历代码实例

二叉树查找思路

二叉树查找代码示例

二叉树-删除节点

有关二叉树的，遍历，查找，删除的全代码

顺序存储二叉树

顺序存储二叉树的概念

顺序存储二叉树的特点:

顺序存储二叉树遍历

代码实现

线索化二叉树

线索二叉树基本介绍

线索二叉树应用案例

代码实现

遍历线索化二叉树

红黑树

线段树

认识线段树

线段树创建代码实现

单点更新

搜索线段树

热门文章

最新文章

相关课程

相关电子书