数据结构与算法之二叉树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 <= < 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);
        }
    }
}