二叉树知识整理：结构、性质与遍历实现

1. 树型结构#

1.1 了解树#

形如图中的结构，称之为树型结构。实际上，数据结构的树 = 图论中的树 + 根节点 + 父子关系

对于数据结构中树的定义

树是由 n（n >= 0）个节点但组成的有限集合。

其中，树的一些基本概念有以下：

**节点的度：**一个节点含有子树的个数称为该节点的度；
**树的度：**一棵树中，所有节点度的最大值称为树的度；上图树的度为 3
**叶子节点或终端节点：**度为 0 的节点称为叶子节点；
**双亲节点或父节点：**若一个节点含有子节点，则这个节点称为其子节点的父节点；
**根节点：**一棵树中，没有双亲节点的节点；
**树的高度或深度：**树中节点的最大层次；上图树的高度为 4
**非终端节点或分支节点：**度不为 0 的节点；

2.二叉树#

2.1 二叉树的概念#

二叉树是一个有限节点集合，满足：

可以是空集（空二叉树）

如果不为空，则由三部分组成：根节点（Root）、左子树（Left Subtree）、右子树（Right Subtree)

并且：左子树和右子树本身也是二叉树

2.1.1 特殊的两种二叉树#

**满二叉树：**一棵二叉树，若每层的节点树都达到最大值，则这棵二叉树就是满二叉树。从数学关系上看，一颗二叉树的层数为 K，则节点总数为 2^k- 1，则它就是满二叉树。
**完全二叉树：**除了最后一层外，其余各层都被完全填满，并且最后一层的节点从左至右连续排列，中间不能空缺

图像概念如下：

2.2 二叉树的性质#

若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 2^i-1(i>0)个结点
若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是 2^k - 1(k>=0)
对任何一棵二叉树, 如果其叶结点个数为 n₀, 度为2的非叶结点个数为 n₂,则有n₀＝n₂＋1
具有n个结点的完全二叉树的深度k为 log₂(n+1) 上取整
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为 i 的节点有：
- 若 i > 0,双亲序号：(i - 1)/2; i = 0,i 为根节点编号，无双亲节点
- 若2i+1<n，左孩子序号：2i+1，否则无左孩子
- 若2i+2<n，右孩子序号：2i+2，否则无右孩子

例题：

已知：总共节点个数为 n 的完全二叉树，求叶子节点个数？

前提说明：公式n₀ = n₂ + 1、n₀ + n₁ + n₂ = n

我们做分类讨论

情况一： n 为偶数

完全二叉树中必有且仅有一个度为 1 的节点，即： n₁ = 1

代入性质，即n₀ + 1 + n₂ = n

结合n₀ = n₂ + 1：可得n₂ = (n - 2) / 2

综上， n₀ = n₂ + 1 = n / 2

情况二：n 为奇数

完全二叉树中不存在度为 1 的节点，即： n₁ = 0

代入性质，即n₀ + n₂ = n

结合n₀ = n₂ + 1：可得n₂ = (n - 1) / 2

综上，n₀ = n₂ + 1 = (n + 1) / 2

总结该过程就是以下公式：n₀ = ⌈n / 2⌉注意是向上取整

2.2.1 性质推导#

对于性质 3，我们给出以下推导

已知：一棵 N 个节点的树有 N-1 条边，下标 1、2 分别代表度为 1，2 的节点能产生的边数：
n₁:产生 n₁-1 条边
n₂:产生 2*n₂ 条边
n₁+ 2*n₂ = N - 1 方程式 1
n₀ + n₁+ n₂ = N 方程式 2
联立解得：n₂ + 1 = n₀

2.3 二叉树的存储#

二叉树的存储结构分为：顺序存储和链式存储；

2.3.1 二叉树的链式存储#

二叉树的链式存储是通过一个个的节点引用起来的，常见的表示方式有二叉链表、三叉链表、线索二叉树表示方法；

链式存储使用情况：

形状不规则的普通二叉树
动态变化的二叉树
需要实现复杂逻辑的树

1
//二叉链表
2
class Node {
3
int val; // 数据域
4
Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
5
Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
6
}
7
// 三叉链表
8
class Node {
9
int val; // 数据域
10
Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
11
Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
12
Node parent; // 当前节点的根节点
13
}
14
// 线索二叉树
15
class Node {
16
    int val;
17
    ThreadedNode left;
18
    ThreadedNode right;
19

20
    // 标志位：0代表孩子，1代表线索（指向前驱/后继）
21
    int lTag;
22
    int rTag;
23
}

线索二叉树：

在普通的二叉链表中，一个拥有 n 个结点的二叉树会有 n+1 个空指针域。线索二叉树的核心思想就是利用这些空指针来存放结点在某种遍历序列中的“前驱”和“后继”信息，从而加快遍历速度.

实质就是：线索二叉树 = 用空指针存遍历顺序

线索树中的 right 可以类似理解为链表中的 next 可以向上走，也可以像普通二叉树一样往下找右子树走

1
ltag = 0 → 左孩子
2
ltag = 1 → 前驱（线索）
3

4
rtag = 0 → 右孩子
5
rtag = 1 → 后继（线索）

如中序遍历不用递归（线索树）

1
public void inorderTraverse(ThreadNode root) {
2
    ThreadNode cur = root;
3

4
    // 找到最左节点
5
    while (cur.ltag == 0) {
6
        cur = cur.left;
7
    }
8

9
    while (cur != null) {
10
        System.out.print(cur.val + " ");
11

12
        // 如果是线索 → 直接走后继
13
        if (cur.rtag == 1) {
14
            cur = cur.right;
15
        } else {
16
            // 否则去右子树找最左
17
            cur = cur.right;
18
            while (cur != null && cur.ltag == 0) {
19
                cur = cur.left;
20
            }
21
        }
22
    }
23
}

而将二叉树转为线索树需要用线索化方法将其转换，如下

1
public class ThreadedBinaryTreeDemo {
2

3
    // 节点定义
4
    static class ThreadNode {
5
        char val;
6
        ThreadNode left;
7
        ThreadNode right;
8

9
        int ltag; // 0 = 左孩子，1 = 前驱
10
        int rtag; // 0 = 右孩子，1 = 后继
11

12
        public ThreadNode(char val) {
13
            this.val = val;
14
        }
15
    }
16

17
    // 全局前驱指针
18
    static ThreadNode pre = null;
19
    // 递归过程中需要共享“上一个访问的节点”
20

21
    // 中序线索化
22
    public static void inorderThread(ThreadNode node) {
23
        if (node == null) return;
24

25
        // 1. 处理左子树（保证顺序：左→根→右）
26
        inorderThread(node.left);
27

28
        // 2. 处理当前节点
29

30
        // (1) 建立前驱线索
31
        if (node.left == null) {
32
            node.left = pre;
33
            node.ltag = 1;
34
        }
35

36
        // (2) 建立后继线索
37
        if (pre != null && pre.right == null) {
38
            pre.right = node;
39
            pre.rtag = 1;
40
        }
41

42
        // (3) 更新 pre（当前节点成为下一个节点的前驱）
43
        pre = node;
44

45
        // 3. 处理右子树
46
        inorderThread(node.right);
47
    }

2.3.2 二叉树的顺序存储#

顺序存储适合情况：

完全二叉树
满二叉树

顺序存储的核心是：使用数组来模拟二叉树的结构

就如前面性质所提到的：

左孩子：2 * i + 1

右孩子：2 * i + 2

顺序存储（数组下标） = 二叉树的层序遍历顺序

注：当且仅当是完全二叉树时

当不是完全二叉树时，其存储情况如此图

2.4 二叉树的基本操作#

2.4.1 二叉树的三种遍历#

1.前序遍历#

1
    // 前序遍历
2
    public void preorderTree(TreeNode root) {
3
        if(root == null) return;
4
        System.out.print(root.val+" ");
5
        preorderTree(root.left);
6
        preorderTree(root.right);
7
    }

非递归方法如下：

思路

通过栈来存储当前节点的上一位

**解题过程 **

将 root 赋给 cur，进入循环

循环中 cur 拿到节点就进行压栈并打印，随后向左移动

向左时一路压栈一路打印，直至 cur == null 时，再弹出前一个节点，将其右索引赋值给 cur 并将其进行循环（将 cur 视为另一子树的根节点即可理解）

1
    // 前序遍历非递归
2
    public void preorderNor(TreeNode root) {
3
        if(root == null) return;
4
        Stack<TreeNode> stack = new Stack<>();
5
        TreeNode cur = root;
6

7
        // 循环判断cur的右侧是否有元素
8
        while(cur != null || !stack.isEmpty()) {
9
            // 循环往下遍历左侧元素
10
            while(cur != null) {
11
                stack.push(cur);
12
                System.out.print(cur.val + " ");
13
                cur = cur.left;
14
            }
15
            // cur为空，需要提出栈中一个元素
16
            TreeNode top = stack.pop();
17
            cur = top.right;
18
        }
19
    }

**注意：**中序遍历（非递归）与此一样，只是打印位置不同

**复杂度 **

时间复杂度：O(N)
空间复杂度：O(N)（最坏）/ O(log N)（平均）/ O(1)（右单支树）

2.中序遍历#

1
// 中序遍历
2
    public void inorderTree(TreeNode root) {
3
        if(root == null) return;
4
        inorderTree(root.left);
5
        System.out.print(root.val+" ");
6
        inorderTree(root.right);
7
    }

中序遍历非递归方法与前序遍历非递归类似，仅仅调换打印位置

1
    // 中序遍历非递归
2
    public void inorderNor(TreeNode root) {
3
        if(root == null) return;
4
        Stack<TreeNode> stack = new Stack<>();
5
        TreeNode cur = root;
6

7
        // 循环判断cur的右侧是否有元素
8
        while(cur != null || !stack.isEmpty()) {
9
            // 循环往下遍历左侧元素
10
            while(cur != null) {
11
                stack.push(cur);
12
                cur = cur.left;
13
            }
14
            // cur为空，需要提出栈中一个元素
15
            TreeNode top = stack.pop();
16
            System.out.print(top.val + " ");
17
            cur = top.right;
18
        }
19
    }

3.后序遍历#

1
    // 后序遍历
2
    public void postorderTree(TreeNode root) {
3
        if(root == null) return;
4
        postorderTree(root.left);
5
        postorderTree(root.right);
6
        System.out.print(root.val+" ");
7
    }

下面为非递归方法：

注意：

如上图，当 cur 走到 7 时，假设还存在右值“10”，直至走完 “10”，随后弹出 7，又会再次走到判断 7 是否存在右值，因此进入死循环。

为此，我们在循环外定义一个节点prev，以此来标记我们打印过的节点以避免死循环。加上if(top.right != null && top.right != prev)这条判断语句即可

思路

通过栈来存储当前节点的上一位

**解题过程 **

思路延续前面的前序以及中序遍历的思想，仅在处理打印顺序时候需调整

1
    // 后序遍历非递归
2
    public void postorderNor(TreeNode root) {
3
        if(root == null) return;
4

5
        Stack<TreeNode> stack = new Stack<>();
6
        TreeNode cur = root;
7
        TreeNode prev = null;
8
        while(cur != null || !stack.isEmpty()) {
9
            while(cur != null) {
10
                stack.push(cur);
11
                cur = cur.left;
12
            }
13
            TreeNode top = stack.peek();
14
            // 注意此处prev用来标记前一个元素是否有被打印
15
            if(top.right != null && top.right != prev) {
16
                cur = top.right;
17
            } else {
18
                System.out.print(top.val + " ");
19
                stack.pop();
20
                prev = top;
21
            }
22
        }
23
    }

**复杂度 **

时间复杂度：O(N)
空间复杂度： O(N)（最坏） / O(log N)（最好）

2.4.2 二叉树的其他操作#

1. 获取树中节点个数#

1
    // 左子树叶子个数 + 右子树叶子个数（子问题法）
2
    public int getLeafNodeCount(TreeNode root){
3
        if(root == null) return 0;
4
        if(root.left == null && root.right == null) return 1;
5
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
6
    }

2. 获取叶子节点个数#

1
    // 获取叶子个数（遍历法）
2
    public static int count = 0;
3
    public void getLeafNodeCount(TreeNode root) {
4
        if(root == null) return;
5
        if(root.left == null && root.right == null) {
6
            count++;
7
        }
8
        getLeafNodeCount(root.left);
9
        getLeafNodeCount(root.right);
10
    }

3. 获取二叉树的高度#

1
    public int getHeight(TreeNode root) {
2
        if(root == null) return 0;
3
        return Math.max(getHeight(root.right)
4
                , getHeight(root.left)) + 1;
5
    }

4. 层序遍历#

1
public void levelOrder(TreeNode root) {
2
    if (root == null) return;
3
    Queue<TreeNode> queue = new LinkedList<>();
4
    queue.offer(root);
5

6
    while (!queue.isEmpty()) {
7
        TreeNode cur = queue.poll();
8
        System.out.print(cur.val + " ");
9

10
        if (cur.left != null) queue.offer(cur.left);
11
        if (cur.right != null) queue.offer(cur.right);
12
    }
13
}

二叉树 Oj 练习#

此题是转换为循环链表

LCR 155. 将二叉搜索树转化为排序的双向链表 - 力扣（LeetCode）

144. 二叉树的前序遍历 - 力扣（LeetCode）

二叉搜索树与双向链表_牛客题霸_牛客网

102. 二叉树的层序遍历 - 力扣（LeetCode）

236. 二叉树的最近公共祖先 - 力扣（LeetCode）

以上题解可参考另一篇文章~

音乐

音乐