当前位置：首页 > news >正文

二叉树详解：带你掌握二叉树

news 文章来源：https://blog.csdn.net/weixin_73392477/article/details/130987111 2025/1/19 20:36:49

- 前言
- 1. 树型结构
- - 1. 1 树的概念
  - 1.2 树的特点
  - 1.3 树的相关术语
- 2. 二叉树（binary tree）
- - 2.1 二叉树的概念
  - 2.2 二叉树中的特殊树
  - - 2.2.1 满二叉树
    - 2.2.2 完全二叉树
  - 2.3 二叉树的性质
- 3. 二叉树的遍历
- - 3.1 前序遍历
  - 3.2 中序遍历
  - 3.3 后序遍历
  - 3.4 层序遍历
- 总结

前言

因为二叉树是一种特殊的树，所以想要学习好二叉树，必须了解树型结构，知道树的基本概念。所以正式开始学习之前，在前面为大家引入了树的概念。

1. 树型结构

1. 1 树的概念

树是一种非线性的数据结构，它是有n个节点构成的集合，把它称为树，是因为这种结构看起来就像一个倒挂的树，根在上面，叶在下面。

1.2 树的特点

有一个特殊的节点，没有前驱节点，我们将此称为根节点。
树是递归定义的。
树的任何节点都可以有任意后继，但是它们不会交叉。
树是一个非线性数据结构。

1.3 树的相关术语

根节点：一个特殊节点，没有前驱节点；上图：第一个1 。
节点的度：一个节点拥有的子树的多少，就是该节点的度；上图：9的度为：2 。
树的度：一棵树最大节点的度就是树的度；上图：最大的节点的度为3 ，则树的度为3 。
叶节点：又称叶子节点，终端节点，度为零的节点；上图：3、4等都是叶节点。
父节点：又称双亲节点，父亲节点，一个节点有子节点，则就是这是字节点的父节点；上图：9是3的父节点。
子节点：又称孩子节点，一个节点下面与连接的节点就是子节点；上图：3是9的子节点。
节点的层次：根节点为第一层，根节点的子节点为第二层，以此类推。
树的高度或深度：树中最大的节点的层次。

2. 二叉树（binary tree）

2.1 二叉树的概念

二叉树是一种树形数据结构，是一种特殊的树，二叉树中每个节点最多只能有两个子节点，并且二叉树的次序是不可颠倒的，是一颗有序树。

2.2 二叉树中的特殊树

二叉树是一种特殊的树，而特殊树中还会有特殊。

2.2.1 满二叉树

一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵
二叉树的层数为K，且结点总数是，则它就是满二叉树。
在这里插入图片描述

2.2.2 完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n
个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。
在这里插入图片描述

2.3 二叉树的性质

二叉树是由节点和边构成的树形结构，每个节点最多有两个子节点，分别称为左子节点和右子节点，没有子节点的节点称为叶子节点。
二叉树有一个根节点，其它节点都是根节点的子节点。根节点没有父节点。
对于一个有n个节点的二叉树，设其高度为h，则h的取值范围为1到n，且h为log2(n+1)向上取整。
在二叉树的第i层上，最多有2^(i-1)个节点。
若深度为h的二叉树满足：每个节点都有两个子节点，且所有叶子节点都在第h层或h-1层，则称该树为满二叉树。满二叉树的节点数为2^h-1。
若深度为h的二叉树最后一层只有叶子节点，其它层都是满的，则称该树为完全二叉树。完全二叉树的节点数在1到2^(h-1)之间。
若二叉树的左右子树可以交换位置且仍为同一棵树，则该二叉树为镜像二叉树。1. 二叉树是由节点和边构成的树形结构，每个节点最多有两个子节点，分别称为左子节点和右子节点，没有子节点的节点称为叶子节点。
《一些练习的题》
1.某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（）
A 不存在这样的二叉树
B 200
C 198
D 199
2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（）
A n
B n+1
C n-1
D n/2
3.一个具有767个节点的完全二叉树，其叶子节点个数为（）
A 383
B 384
C 385
D 386
4.一棵完全二叉树的节点数为531个，那么这棵树的高度为（）
A 11
B 10
C 8
D 12
答案：
1.B
2.A
3.B
4.B

3. 二叉树的遍历

二叉树的遍历是一个重要的点，是一个必须要掌握的点，遍历分为前中后序遍历，层序遍历四种。我们将使用这张图详细介绍一下。
遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。
遍历是二叉树上最重要的操作之一，是二叉树上进行其它运算之基础。

3.1 前序遍历

前序遍历的遍历顺序：访问根结点—>根的左子树—>根的右子树。
遍历结果：123456

如上图：遍历根节点1，然后遍历左子树2，一直遍历到左子树为null。然后返回途中遍历右子树，3的右子树为null。然后返回到2，2的右子树为null，返回到根节点1。1的左树已经遍历一遍，所以继续遍历1的右子树4，然后先遍历左子树5，5的左右都为空，则返回遍历4的右子树6。6的左右都为空，原路返回，到根节点遍历结束。

3.2 中序遍历

根的左子树—>根节点—>根的右子树。
遍历结果：321546

3.3 后序遍历

根的左子树—>根的右子树—>根节点。
遍历结果：325641

3.4 层序遍历

除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在
层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
遍历结果：124356

一些练习选择题

某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为()
A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA
二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为()
A: E B: F C: G D: H
设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为()
A: adbce B: decab C: debac D: abcde
某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出(同一层从左到右)的序列为()
A: FEDCBA B: CBAFED C: DEFCBA D: ABCDEF
【参考答案】 1. A 2. A 3. D 4. A

总结

这篇博客主要为大家带来树及二叉树的基本概念，性质，遍历方式等，下篇博客将为大家带来代码的实现以及应用。
期待大家关注!
最后，祝大家61快乐，天天开心！

目录

前言