【白话树】之二叉树

快速导航

一、二叉树的基本概念
- 1、二叉树定义
- 2、常见术语
- 3、基本操作
- - 1）创建：
  - 2）插入与删除：
- 4、常见类型
- - 1）满二叉树（完美二叉树）
  - 2）完全二叉树
  - 3）完满二叉树
  - 4）平衡二叉树
  - 5）链表 - 特殊的二叉树
二、二叉树遍历
- 1、层序遍历
- 2、前序、中序、后序遍历

一、二叉树的基本概念

1、二叉树定义

二叉树：是一种非线性数据结构，是“分而治之”思想的一种实现。

和链表一样，二叉树最基本的单位也是节点。

只是二叉树的节点，不仅包含值本身，也包含了左子节点和右子节点的引用。

二叉树（binary tree）是n（n≥0）个节点构成的集合，它或为空树（n=0），或满足以下两个条件：

1）有且仅有一个称为根的节点；

2）除根节点以外，其余节点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且T1和T2本身都是二叉树。

二叉树是一种特殊的树，它最多有两个子树，分别为左子树和右子树，二者是有序的，不可以互换。

也就是说，二叉树中不存在度大于2的节点。

下面是二叉树的五种形态：
在这里插入图片描述

Java结构代码：

/* 二叉树节点类 */
class TreeNode {int val;         // 节点值TreeNode left;   // 左子节点引用TreeNode right;  // 右子节点引用TreeNode(int x) { val = x; }
}

2、常见术语

根节点：二叉树顶层的节点，唯一没有父节点的节点
叶子节点：没有子节点的节点
边：两个节点之间的连线
节点所在的层：根节点层数为1，相当于根节点的层数 + 节点到根的边数
节点的度：子节点的数量
二叉树的高度：根节点到所有叶子节点的最大的边数
节点的深度：根节点到节点的边数
节点的高度：节点到所有叶子节点的最大的边数

3、基本操作

1）创建：

Java实现：

// 初始化节点
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
// 构建节点之间的引用（指针）
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;

2）插入与删除：

在这里插入图片描述
Java实现：

TreeNode P = new TreeNode(0);
// 在 n1 -> n2 中间插入节点 P
n1.left = P;
P.left = n2;
// 删除节点 P
n1.left = n2;

4、常见类型

1）满二叉树（完美二叉树）

所有层的节点都被填满的二叉树。
在这里插入图片描述

2）完全二叉树

只有最底层的节点没有被填满，而且同一层级是从左到右依次填充的。
在这里插入图片描述

3）完满二叉树

除了叶节点之外，其余所有节点都有两个子节点。
在这里插入图片描述

4）平衡二叉树

任意节点的左子树和右子树的高度之差的绝对值不超过 1 。
在这里插入图片描述

5）链表 - 特殊的二叉树

当二叉树中的每一层只有一个节点的时候，所有的节点组成一个链表。

二、二叉树遍历

1、层序遍历

相关概念： 广度优先遍历、广度优先搜索/BFS

遍历方式： 自顶向下，从左到右，逐层遍历

图示：
在这里插入图片描述
Java代码实现：

/* 层序遍历 */
List<Integer> levelOrder(TreeNode root) {// 初始化队列，加入根节点Queue<TreeNode> queue = new LinkedList<>();queue.add(root);// 初始化一个列表，用于保存遍历序列List<Integer> list = new ArrayList<>();while (!queue.isEmpty()) {TreeNode node = queue.poll(); // 队列出队list.add(node.val);           // 保存节点值if (node.left != null)queue.offer(node.left);   // 左子节点入队if (node.right != null)queue.offer(node.right);  // 右子节点入队}return list;
}

2、前序、中序、后序遍历

相关概念： 深度优先遍历、深度优先搜索/DFS

快速记忆： 先走到尽头，再回溯继续。

前序（根节点 -> 左子树 -> 右子树）
中序（左子树 -> 根节点 -> 右子树）
后序（左子树 -> 右子树 -> 根节点）

图示：
在这里插入图片描述
深度优先遍历就像是绕着整棵二叉树的外围“走”一圈

深度优先搜索通常基于递归实现，Java代码如下：

/* 前序遍历 */
void preOrder(TreeNode root) {if (root == null)return;// 访问优先级：根节点 -> 左子树 -> 右子树list.add(root.val);preOrder(root.left);preOrder(root.right);
}/* 中序遍历 */
void inOrder(TreeNode root) {if (root == null)return;// 访问优先级：左子树 -> 根节点 -> 右子树inOrder(root.left);list.add(root.val);inOrder(root.right);
}/* 后序遍历 */
void postOrder(TreeNode root) {if (root == null)return;// 访问优先级：左子树 -> 右子树 -> 根节点postOrder(root.left);postOrder(root.right);list.add(root.val);
}

参考资料：

《趣学数据结构》 – 陈小玉
https://www.hello-algo.com/chapter_tree/binary_tree/#4