这里面有10个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树；10个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。
掌握了这些基础的数据结构和算法，再学更加复杂的数据结构和算法，就会非常容易、非常快。
目录
树(Tree)
树型结构是一种非线性结构，它的数据元素之间呈现分支、分层的特点。
1.树的定义
树(Tree)是由n(n≥0)个结点构成的有限集合T，当n=0时T称为空树；否则，在任一非空树T中：
(1)有且仅有一个特定的结点，它没有前驱结点，称其为根(Root)结点；
(2)剩下的结点可分为m(m≥0)个互不相交的子集T1，T2，…，Tm，其中每个子集本身又是一棵树，并称其为根的子树(Subtree)。
注意：树的定义具有递归性，即“树中还有树”。树的递归定义揭示出了树的固有特性
2.什么是树结构
什么是“树”？再好的定义，都没有图解来的直观。所以我在图中画了几棵“树”。你来看看，这些“树”都有什么特征？
你有没有发现，“树”这种数据结构真的很像我们现实生活中的“树”
3.为什么使用树结构
在有序数组中，可以快速找到特定的值，但是想在有序数组中插入一个新的数据项，就必须首先找出新数据项插入的位置，然后将比新数据项大的数据项向后移动一位，来给新的数据项腾出空间，删除同理，这样移动很费时。显而易见，如果要做很多的插入和删除操作和删除操作，就不该选用有序数组。另一方面，链表中可以快速添加和删除某个数据项，但是在链表中查找数据项可不容易，必须从头开始访问链表的每一个数据项，直到找到该数据项为止，这个过程很慢。 树这种数据结构，既能像链表那样快速的插入和删除，又能想有序数组那样快速查找
4.树的常用术语
结点——包含一个数据元素和若干指向其子树的分支
度——结点拥有的子树个数
树的度——该树中结点的最大度数
叶子——度为零的结点
分支结点（非终端结点）——度不为零的结点
孩子和双亲——结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲
兄弟——同一个双亲的孩子
祖先和子孙——从根到该结点所经分支上的所有结点。相应地，以某一结点为根的子树中的任一结点称为该结点的子孙。
结点的层次——结点的层次从根开始定义，根结点的层次为1，其孩子结点的层次为2，……
堂兄弟——双亲在同一层的结点
树的深度——树中结点的最大层次
有序树和无序树——如果将树中每个结点的各子树看成是从左到右有次序的(即位置不能互换)，则称该树为有序树；否则称为无序树。
森林——m(m≥0)棵互不相交的树的有限集合
二叉树(Binary Tree）
树结构多种多样，不过我们最常用还是二叉树，我们平时最常用的树就是二叉树。二叉树的每个节点最多有两个子节点，分别是左子节点和右子节点。二叉树中，有两种比较特殊的树，分别是满二叉树和完全二叉树。满二叉树又是完全二叉树的一种特殊情况。
1．二叉树的定义和特点
二叉树的定义：
二叉树(Binary Tree)是n(n≥0)个结点的有限集合BT，它或者是空集，或者由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树组成 。
————————————
二叉树的特点：
每个结点至多有二棵子树(即不存在度大于2的结点)；二叉树的子树有左、右之分，且其次序不能任意颠倒。
2．几种特殊形式的二叉树
1、满二叉树：
定义：深度为k且有2k-1个结点的二叉树，称为满二叉树。
特点：每一层上的结点数都是最大结点数
2、完全二叉树：
定义：
深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树
特点:
特点一 : 叶子结点只可能在层次最大的两层上出现;
特点二 : 对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l 或l+1
代码创建二叉树：
首先，创建一个节点Node类
package demo5;
/*
* 节（结）点类
*/
public class Node {
//节点的权
int value;
//左儿子（左节点）
Node leftNode;
//右儿子（右节点）
Node rightNode;
//构造函数，初始化的时候就给二叉树赋上权值
public Node(int value) {
this.value=value;
}
//设置左儿子（左节点）
public void setLeftNode(Node leftNode) {
this.leftNode = leftNode;
}
//设置右儿子（右节点）
public void setRightNode(Node rightNode) {
this.rightNode = rightNode;
}
接着创建一个二叉树BinaryTree 类
package demo5;
/*
* 二叉树Class
*/
public class BinaryTree {
//根节点root
Node root;
//设置根节点
public void setRoot(Node root) {
this.root = root;
}
//获取根节点
public Node getRoot() {
return root;
}
}
最后创建TestBinaryTree 类（该类主要是main方法用来测试）来创建一个二叉树
package demo5;
public class TestBinaryTree {
public static void main(String[] args) {
//创建一颗树
BinaryTree binTree = new BinaryTree();
//创建一个根节点
Node root = new Node(1);
//把根节点赋给树
binTree.setRoot(root);
//创建一个左节点
Node rootL = new Node(2);
//把新创建的节点设置为根节点的子节点
root.setLeftNode(rootL);
//创建一个右节点
Node rootR = new Node(3);
//把新创建的节点设置为根节点的子节点
root.setRightNode(rootR);
//为第二层的左节点创建两个子节点
rootL.setLeftNode(new Node(4));
rootL.setRightNode(new Node(5));
//为第二层的右节点创建两个子节点
rootR.setLeftNode(new Node(6));
rootR.setRightNode(new Node(7));
}
}
不难看出创建好的二叉树如下（画的不好，还望各位见谅）：
3．二叉树的两种存储方式
二叉树既可以用链式存储，也可以用数组顺序存储。数组顺序存储的方式比较适合完全二叉树，其他类型的二叉树用数组存储会比较浪费存储空间，所以链式存储更合适。
我们先来看比较简单、直观的链式存储法。
接着是基于数组的顺序存储法（该例子是一棵完全二叉树）
上面例子是一棵完全二叉树，所以仅仅“浪费”了一个下标为0的存储位置。如果是非完全二叉树，则会浪费比较多的数组存储空间，如下。
4．二叉树的遍历
前面我讲了二叉树的基本定义和存储方法，现在我们来看二叉树中非常重要的操作，二叉树的遍历。这也是非常常见的面试题。
经典遍历的方法有三种，前序遍历、中序遍历和后序遍历
前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。
我想，睿智的你已经想到了二叉树的前、中、后序遍历就是一个递归的过程。比如，前序遍历，其实就是先打印根节点，然后再递归地打印左子树，最后递归地打印右子树。
在之前创建好的二叉树代码之上，我们来使用这三种方法遍历一下~
依旧是在Node节点类上添加方法：可以看出遍历方法都是用的递归思想
package suanfa.shu;
/**
* @author duyanyan
* @date 2021/4/20 16:44
* 节（结）点类
*/
public class Node {
//节点的权
int value;
//左儿子 左节点
Node lefyNode;
//右节点
Node rightNode;
//构造函数，初始化的时候就给二叉树附上权值
public Node(int value) {
this.value = value;
}
///设置左儿子（左节点
public void setLefyNode(Node lefyNode) {
this.lefyNode = lefyNode;
}
//设置右儿子（右节点）
public void setRightNode(Node rightNode) {
this.rightNode = rightNode;
}
//==============开始遍历
//前序遍历（节点，左，右）
public void frontShow(){
//先遍历当前节点的内容
System.out.println(value);
//左节点
if(lefyNode != null){
lefyNode.frontShow();
}
//右节点
if (rightNode !=null){
rightNode.frontShow();
}
}
//中序遍历（左，节点，右）
public void midShow(){
//左节点
if (lefyNode != null){
lefyNode.midShow();
}
//遍历当前节点
System.out.println(value);
//右节点
if (rightNode !=null){
rightNode.midShow();
}
}
//后序遍历（左，右，节点）
public void afterShow(){
//左节点
if (lefyNode != null){
lefyNode.afterShow();
}
//y右节点
if (rightNode !=null){
rightNode.afterShow();
}
//遍历当前节点
System.out.println(value);
}
}
然后依旧是在二叉树BinaryTree 类上添加方法，并且添加的方法调用Node类中的遍历方法
package suanfa.shu;
/**
* @author duyanyan
* @date 2021/4/20 16:44
* 二叉树class
*/
public class BinaryTree {
//根re节点root
Node root;
//获取根节点
public Node getRoot() {
return root;
}
//设置根节点
public void setRoot(Node root) {
this.root = root;
}
public void frontShow() {
if(root!=null) {
//调用节点类Node中的前序遍历frontShow（）方法
root.frontShow();
}
}
public void midShow() {
if(root!=null) {
//调用节点类Node中的中序遍历midShow()方法
root.midShow();
}
}
public void afterShow() {
if(root!=null) {
//调用节点类Node中的后序遍历afterShow()方法
root.afterShow();
}
}
}
依旧是在TestBinaryTree类中测试
package suanfa.shu;
/**
* @author duyanyan
* @date 2021/4/20 16:44
* （该类主要是main方法用来测试）来创建一个二叉树
*/
public class TestBinaryTree {
public static void main(String[] args) {
//创建一颗树
BinaryTree binaryTree = new BinaryTree();
//创建一个根节点
Node root = new Node(1);
//把根节点赋给树
binaryTree.setRoot(root);
//创建一个左节点
Node rootL = new Node(2);
//把新创建的节点设置为根节点的子节点
root.setLefyNode(rootL);
//创建一个右节点
Node rootR = new Node(3);
//把新创建的节点设置为根节点的子节点
root.setRightNode(rootR);
//为第二层的左节点创建两个子节点
rootL.setLefyNode(new Node(4));
rootL.setRightNode(new Node(5));
//为第二层的右节点创建两个子节点
rootR.setLefyNode(new Node(6));
rootR.setRightNode(new Node(7));
//前序遍历树
binaryTree.frontShow();
System.out.println("前序遍历===============");
//中序遍历
binaryTree.midShow();
System.out.println("中序遍历===============");
//后序遍历
binaryTree.afterShow();
System.out.println("后序遍历===============");
//前序查找
/* Node result = binaryTree.frontShow(5);
System.out.println(result);*/
}
}
二叉树遍历算法分析：
二叉树遍历算法中的基本操作是访问根结点，不论按哪种次序遍历，都要访问所有的结点，对含n个结点的二叉树，其时间复杂度均为O（n）。所需辅助空间为遍历过程中所需的栈空间，最多等于二叉树的深度k乘以每个结点所需空间数，最坏情况下树的深度为结点的个数n，因此，其空间复杂度也为O(n)。
贴一下我断点对递归的分析，希望对你有一定的帮助~
5．二叉树中节点的查找与删除
刚才讲到二叉树的三种金典遍历放法，那么节点的查找同样是可以效仿的，分别叫做前序查找、中序查找以及后序查找，下面代码只以前序查找为例，三者查找方法思路类似~
至于删除节点，有三种情况：
1、如果删除的是根节点，那么二叉树就完全被删了
2、如果删除的是双亲节点，那么该双亲节点以及他下面的所有子节点所构成的子树将被删除
3、如果删除的是叶子节点，那么就直接删除该叶子节点
这里，总结一下，我们学了一种非线性表数据结构，树。关于树，有几个比较常用的概念你需要掌握，那就是：根节点、叶子节点、父节点、子节点、兄弟节点，还有节点的高度、深度、层数，以及树的高度等。我们平时最常用的树就是二叉树。二叉树的每个节点最多有两个子节点，分别是左子节点和右子节点。二叉树中，有两种比较特殊的树，分别是满二叉树和完全二叉树。满二叉树又是完全二叉树的一种特殊情况。二叉树既可以用链式存储，也可以用数组顺序存储。数组顺序存储的方式比较适合完全二叉树，其他类型的二叉树用数组存储会比较浪费存储空间。除此之外，二叉树里非常重要的操作就是前、中、后序遍历操作，遍历的时间复杂度是O(n)，你需要理解并能用递归代码来实现。
————————————————
版权声明：本文为CSDN博主「宜春」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_44543508/article/details/100600178
6、红黑树
二叉树：
每个分支不能超过两个。
排序树/查找树：查询速度快
在二叉树的基础上，元素有大小顺序的，左子树上的数字小，右子树上的数字大。
平衡树：
左子树和右子树数量相等。
不平衡树：
左子树和右子树数量不相等。
红黑树：
特点：趋近于平衡树，查询速度快，查询叶子节点最大次数和最小次数不能超过2倍。
约束条件：
结点可以是红色，黑色
根节点是黑色的，
叶子结点，黑色
每个红色结点的子结点都是黑色的
任何一个结点到其每一个叶子结点的所有路径上黑色结点的数量相同
