数据结构与算法之二叉树Binary Tree

树Tree的基本概念

节点、根节点、父节点、子节点、兄弟节点
一棵树可以没有任何节点，称为空树
一棵树可以只有一个节点，也就是只有根节点
子树、左子树、右子树

节点的度（degree）：子树的个数
🌰：1的度是5个：2、3、4、5、6
🌰：2的度是2个：21、22
🌰：61的度是0个
树的度（degree）：所有节点度中的最大值
🌰：图中最大的是节点1，有5个度
叶子的节点（leaf）：度为0的节点
🌰：图中21、221、222、223、31、5、51、52、61都是叶子节点
非叶子的节点：度不为0的节点

树的层数（level）：根节点在第1层，根节点的子节点在第2层，以此类推（有些教程从第0层计算）
节点的深度（depth）：从根节点到当前节点的唯一路劲上的节点总数
🌰：节点2的深度：从根节点1到2经过了2个节点，深度为2
🌰：节点31的深度：从根节点1到31经过了3个节点，深度为3
节点的高度（height）：从当前节点到最远叶子节点的路劲上的节点总数
🌰：节点2的高度：图中看出从节点2到最远的叶子节点为221、222、223中的一个，取其中一个计算，经历了2-22-221总共3个节点，所有高度为3
树的深度：所有节点深度中的最大值
树的高度：所有节点高度中的最大值
树的深度 等于树的高度

有序树、无序树、森林

有序树：树中的任意节点的子节点之间有顺序关系
有序树：树中的任意节点的子节点之间没有顺序关系（也称为“自由树”）
森林：由 m (m >= 0) 棵互不相交的树组成的集合

二叉树Binary Tree

二叉树的特点：

每个节点的度最大值为2（最多拥有2棵子树）
左子树跟右子树是有顺序的
即使某个节点只有一棵子树，也要区分左右子树
二叉树是有序树

二叉树的性质：

非空二叉树的第i层，最多有 2^i-1 个节点（i >= 1）
高度为h的二叉树上最多有 2^h-1 个节点（h>= 1）
对于任何一棵非空二叉树，如果叶子节点个数为n0，度为2的节点个数为n2，则有：n0 = n2 + 1
假设度为1的节点个数为n1，那么二叉树的节点总数n = n0 + n1 + n2
二叉树的变数T = n1 + 2 * n2 = n - 1 = n0 + n1 + n2 - 1

真二叉树Proper Binary Tree

所有节点的度要么是0，要么是2

满二叉树Full Binary Tree

所有节点的度要么是0，要么是2，且所有的叶子节点都在最后一层
在同样高度的二叉树中，满二叉树的叶子节点数量最多，总节点数量最多
满二叉树一定是真二叉树，真二叉树不一定是满二叉树
假设满二叉树的高度为h（h>= 1），那么：
🌰：第i层的节点数量：2^i-1
🌰：叶子节点数量：2^h-1
🌰：总节点的数量n：n = 2^h-1 = 2⁰ + 2¹ + 2² + ... 2^h-1

完全二叉树Complete Binary Tree

叶子节点只会出现在最后2层，且最后1层的叶子节点都靠左对齐
完全二叉树从根节点至倒数第2层是一棵满二叉树
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
度为1的节点只有左子树
度为1的节点要么是1个，要么是0个
同样节点数量的二叉树，完全二叉树的高度最小
假设完全二叉树的高度为h（h>= 1），那么：
🌰：至少有2^h-1个节点 2⁰ + 2¹ + 2² + ... 2^h-2 + 1
🌰：最多有2^h-1个节点 2⁰ + 2¹ + 2² + ... 2^h-1，满二叉树
🌰：总节点数量：2^h-1<=n<=2^h，取对数：h - 1 <= $log_2n$ < h

二叉搜索树Binary Search Tree

1、二叉搜索树是二叉树的一种，是应用非常广泛的一种二叉树，简称BST

又称为：二叉查找树、二叉排序树
任意一个节点的值都大于其左子树所有节点的值
任意一个节点的值都小于其右子树所有节点的值
它的左右子树也是一颗二叉搜索树

2、二叉搜索树可以大大提高搜索数据的效率
3、二叉搜索树存储的元素必须具备可比较性

比如 int、double 等
如果自定义类型，需要制定比较方式
不允许为null

二叉树的遍历

遍历是数据结构中常见操作：
1️⃣：把所有元素都访问一遍
线性数据结构的遍历比较简单：
1️⃣：正序遍历
2️⃣：逆序遍历
根据节点访问顺序的不同，二叉树的常见遍历方式有4种：
1️⃣：前序遍历
2️⃣：中序遍历
3️⃣：后序遍历
4️⃣：层序遍历

二叉树的遍历 —— 前序遍历

访问顺序：
🌰：根节点 — 前序遍历左子树 — 前序遍历右子树
🌰：7——4、2、1、3、5——9、8、11、10、12

可以利用递归来实

public void preporderTraversal() {
    preporderTraversal(rootNode);
}
private void preporderTraversal(Node<E> node) {
    if (node == null) { return; }
    System.out.println(node.element);
    preporderTraversal(node.leftNode);
    preporderTraversal(node.rightNode);
}

二叉树的遍历 —— 中序遍历

访问顺序：
🌰：中序遍历左子树 — 根节点 — 中序遍历右子树
🌰：1、2、3、4、5——7——8、9、10、11、12
如果访问顺序是这样的：
🌰：中序遍历右子树 — 根节点 — 中序遍历左子树
🌰：12、11、10、9、8——7——5、4、3、2、1
二叉搜索树的中序遍历结果是升序或者降序的

public void inorderTraversal() {
    inorderTraversal(rootNode);
}
private void inorderTraversal(Node<E> node) {
    if (node == null) { return; }
    inorderTraversal(node.leftNode);
    System.out.println(node.element);
    inorderTraversal(node.rightNode);
}

二叉树的遍历 —— 后序遍历

访问顺序：
🌰：后序遍历左子树 — 后序遍历右子树 — 根节点
🌰：1、3、2、5、4——8、10、12、11、9——7

public void postorderTraversal() {
    postorderTraversal(rootNode);
}
private void postorderTraversal(Node<E> node) {
    if (node == null) { return; }
    postorderTraversal(node.leftNode);
    postorderTraversal(node.rightNode);
    System.out.println(node.element);
}

二叉树的遍历 —— 层序遍历

访问顺序：
🌰：从上到下，从左到右依次访问每一个节点
🌰：7——4、9——2、5、8、1——1、3、10、12
实现思路：使用队列
1️⃣：将根节点入队
2️⃣：循环执行下面操作，直到队列为空：
🌰：将队头节点A出队，进行访问
🌰：将A的左子节点入队
🌰：将A的右子节点入队

public void levelOrderTraversal() {
    if (rootNode == null) { return; }
        
    Queue<Node<E>> queue = new LinkedList<>();
    queue.offer(rootNode);
        
    while (!queue.isEmpty()) {
        Node<E> node = queue.poll();
        System.out.println(node.element);
        //是否有左右子节点
        if (node.leftNode != null) {
            queue.offer(node.leftNode);
        }
        if (node.rightNode != null) {
            queue.offer(node.rightNode);
        }
    }
}