树的诞生
1、数组存储方式的分析
数组未排序
优点：在数组尾添加元素，速度快
缺点：查找速度慢
数组排序
- 优点：可以使用二分查找，查找速度快
- 缺点：为了保证数组有序，在添加新数据时，找到插入位置后，后面的数据需整体移动，速度慢。
2、链式存储方式的分析
- 优点：在一定程度上对数组存储方式有优化，增加和删除元素速度快
- 缺点：不管链表是否有序，查找速度都慢(检索某个值，需要从头节点开始遍历)
3、树存储方式的分析
能提高数据存储，读取的效率。比如利用二叉排序树，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。
树中的术语
结点：指树中的一个元素，一般用 n 表示
结点的度：指结点拥有的子结点的个数，二叉树的度不大于2
树的度：指树中各结点的度的最大值
树的阶：指树中的一个结点最多能有多少个子节点，一般用字母 M 表示阶数
分支结点：度大于0的结点，除了叶子结点之外的结点
叶结点：度为 0 的结点，也称为终端结点
高度/深度：叶子节点的高度为1，根节点高度最高
层：规定根节点在1层，其他任意节点是其父节点的层数+1
森林：彼此不相交的树的集合
二叉树
简介
- 二叉树：每个结点最多只能有两个子结点(左结点和右结点)
- 满二叉树：二叉树的所有叶子结点都在最后一层，且结点总数为 2n -1 , n 为层数
- 完全二叉树：二叉树的所有叶子结点都在最后一层或者倒数第二层，而且最后一层的叶子结点在左边连续，倒数第二层的叶子结点在右边连续
- 左斜树：所有节点都只有左子树的二叉树
- 右斜树：所有节点都只有右子树的二叉树
前序遍历
先输出父节点，再遍历左子树和右子树
递归
public void preOrderRecur(Node root) {
if (root == null) {
return;
}
System.out.print(root.data + " -> ");
preOrderRecur(root.left);
preOrderRecur(root.right);
}
非递归
public void preOrder() {
if (root == null)
return;
Node current;
//把LinkedList当栈使用
LinkedList<Node> s = new LinkedList<Node>();
s.addFirst(root);
while (!s.isEmpty()) {
current = s.removeFirst();
System.out.print(current.data + " -> ");
if (current.right != null)
s.addFirst(current.right);
if (current.left != null)
s.addFirst(current.left);
}
}
中序遍历
先遍历左子树，再输出父节点，再遍历右子树
递归
public void inOrderRecur(Node root) {
if (root == null) {
return;
}
inOrderRecur(root.left);
System.out.print(root.data + " -> ");
inOrderRecur(root.right);
}
非递归
public void inOrder() {
Node current = root;
//把LinkedList作为栈使用
LinkedList<Node> s = new LinkedList<Node>();
while (current != null || !s.isEmpty()) {
while (current != null) {
s.addFirst(current);
current = current.left;
}
if (!s.isEmpty()) {
current = s.removeFirst();
System.out.print(current.data + " -> ");
current = current.right;
}
}
}
后序遍历
先遍历左子树，再遍历右子树，最后输出父节点
递归
public void postOrderRecur(Node root) {
if (root == null) {
return;
}
postOrderRecur(root.left);
postOrderRecur(root.right);
System.out.print(root.data + " -> ");
}
非递归
public void postOrder() {
Node current = root;
LinkedList<Node> s1 = new LinkedList<Node>();
LinkedList<Node> s2 = new LinkedList<Node>();
while (current != null || !s1.isEmpty()) {
while (current != null) {
s1.addFirst(current);
s2.addFirst(current);
current = current.right;
}
if (!s1.isEmpty()) {
current = s1.removeFirst();
current = current.left;
}
}
while (!s2.isEmpty()) {
System.out.print(s2.removeFirst().data + " -> ");
}
}
层次遍历
public void levelOrder() {
if (root == null) {
return;
}
//把LinkedList作为队列使用
LinkedList<Node> q = new LinkedList<Node>();
q.addFirst(root);
Node current;
while (!q.isEmpty()) {
current = q.removeLast();
System.out.print(current.data + " -> ");
if (current.left != null)
q.addFirst(current.left);
if (current.right != null)
q.addFirst(current.right);
}
}
查找
public boolean contains(int e) {
//用current记录根节点
Node current = root;
while (current != null) {
//相等，说明找到了，返回true
if (e == current.data) {
return true;
//要查找的数比根节点大，指向根节点的右儿子
} else if (e > current.data) {
current = current.right;
//要查找的数比根节点下，指向根节点的左儿子
} else {
current = current.left;
}
}
//找不到，返回false
return false;
}
删除
代码实现
顺序存储二叉树
。。。
线索化二叉树
。。。
二叉搜索树-BST
二叉搜索树(BST: Binary Search Tree)：任何一个非叶子结点，要求左子结点的值比当前结点的值小，右子结点的值比当前结点的值大。
创建和遍历
。。。
删除
。。。
复杂度
时间复杂度：O(log2n)～O(n)
如果二叉搜索树是平衡的，则 n 个节点的二叉排序树的高度为 log2n+1 ，其查找效率为O(log2n)，近似于折半查找。
如果二叉搜索树完全不平衡，则其深度可达到 n，查找效率为 O(n)，退化为顺序查找。
空间复杂度：O(n)
平衡二叉树-AVL
引出
给你一个序列 {1,2,3,4,5,6}，要求创建一颗二叉搜索树(BST)
可以看到左子树全部为空，极端情况下，二叉树会退化成链表
- 插入速度没有影响
- 查询速度明显降低(需要依次比较)，搜索效率降低为 O(n)
由此，二叉搜索树的查找效率取决于树的高度，因此保持树的高度最小，即可保证树的查找效率。如何保证？这就要引入平衡二叉树了！
简介
平衡二叉树，由前苏联的数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉树，根据科学家的英文名也称为 AVL 树。 可以保证查询效率较高。
特点：
- 必须是二叉搜索树
- 每个结点的左子树和右子树的高度差的绝对值不超过1
平衡因子：将二叉树上节点的左子树高度减去右子树高度的值称为该节点的平衡因子BF(Balance Factor)。
左旋转
右旋转
双旋转
。。。
红黑树
红黑树是 AVL 树的变体
结点不是红色就是黑色，根结点必是黑色
叶子结点是 null 结点（空结点）且为黑色
每个红色结点的两个子结点都是黑色。（同一路径，不存在连续的红色节点）
每个节点到叶子节点的所有路径，都包含相同数目的黑色节点（相同的黑色高度）
B-树家族
请参考小简的另一篇文章：B-Tree家族 | 简简 (jwt1399.top)
字典树
。。。
参考
❤️Sponsor
您的支持是我不断前进的动力，如果您恰巧财力雄厚，又感觉本文对您有所帮助的话，可以考虑打赏一下本文，用以维持本博客的运营费用，拒绝白嫖，从你我做起！🥰🥰🥰
| 支付宝支付 | 微信支付 |
 |
 |
