Java来聊一下树Tree数据结构

把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
特点：
1、每个节点只有有限个子节点或没有子节点。
2、除了根节点每个节点只有一个父节点，根节点没有父节点。
3、叶节点是最底下的节点，它没有子节点，其他节点都有子节点。
4、除了根节点外，每个子节点可以分为多个不想交的子树。 5、父节点和子节点之间用指针链接。 可能有些人知道树这么一回事，就是不知道怎么去描述。

所以Java中定义实体类树，可以这样定义：

package tree;

/**
 * @author kegekeqi
 * @version 1.0
 * @date 2021-12-12 9:50
 */
public class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x) {
		val = x;
	}

	@Override
	public String toString() {
		return "TreeNode{" +
				"val=" + val +
				", left=" + left +
				", right=" + right +
				'}';
	}
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25

那么为什么需要树呢？
仔细想一下TreeSet、TreeMap，为什么要用他们。HashSet速度快，TreeSet则方便排序。HashMap速度快，TreeMap方便排序。
同时，在树中查找数据项的速度和在有序数组中查找一样快，并且插入数据项和删除数据项的速度也和链表一样。可以说结合了数组和链表的特点。

特殊的树
二叉树
就是每个节点最多只能有2个节点，可以有1个节点，可以有2个节点。

二叉树重要概念：三种遍历方式
前序遍历：10、6、4、8、14、12、16
中序遍历：4、6、8、10、12、14、16 后序遍历：4、8、6、12、16、14、10

还有宽度优先遍历：从上到下 10、6、14、4、8、12、16

二叉搜索树：左子节点总是小于或等于根结点，而右子节点总是大于大于或等于根结点。

二叉树另外两个特性堆和红黑树。
没错，是堆栈的堆，最大堆和最小堆主要快速解决最大值和最小值的问题。TreeMap底层红黑树。红黑树是吧树中节点定义红黑两种颜色，并通过规则确保从根节点到叶节点的最长路径的长度不超过最短路径的两倍。

文章知识点与官方知识档案匹配，可进一步学习相关知识

本文使用 文章同步助手 同步