七、基本数据结构之树

一、基本数据结构之数组
二、基本数据结构之链表
三、基本数据结构之队列
四、基本数据结构之栈
五、基本数据结构之哈希表
六、基本数据结构之集合
七、基本数据结构之树
八、基本数据结构之堆
九、基本数据结构之图

1. 树的基本概念

• 节点：树结构中的每一个元素都是节点
• 根节点：树最顶端的节点，也是最开始的节点
• 叶子节点：没有子节点的节点
• 高度：从叶子节点到根节点的方向，从0开始计数，称为高度
• 深度：从根节点到叶子节点的方向，从0开始计数，称为深度
• 层：从根节点到叶子结点的方向，从1开始计数，称为层数

2. 二叉树的分类

• 普通二叉树：每个节点最多有两个子节点
• 满二叉树：除了叶子节点外的每个节点有且仅有两个子节点，且所有叶子节点都在同一个层上（满二叉树一定是完全二叉树）
• 完全二叉树：从树的根节点，从上到下，从左到右依次填满结点形成的二叉树（完全二叉树不一定是满二叉树）

3. 二叉树的遍历

• 前序遍历：根节点 --> 左子树 --> 右子树
• 中序遍历：左子树 --> 根节点 --> 右子树
• 后序遍历：左子树 --> 右子树 --> 根节点

4. 二叉树的Java实现

public class TreeNode {
	int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}