树的定义树的基本术语

离散树知识点总结一、基本概念1. 什么是树树是一种特殊的图，它是一种没有回路的无向图。

树是由 n 个节点和 n-1 条边组成的连通图。

2. 树的特点树是一个具有以下特点的无向图：- 无环。

树中不存在回路，即不存在从一个节点出发经过若干条边再回到出发点的路径。

- 连通。

树是一个连通图，即从树的任意一个节点出发，都可以到达树的所有其他节点。

- n 个顶点和 n-1 条边。

树由 n 个顶点和 n-1 条边组成。

3. 树的术语- 节点（Node）：树中的每一个元素都称为节点。

- 父节点（Parent）：在树中，每个节点都有一个父节点，除了根节点没有父节点。

- 子节点（Children）：一个节点的子节点是指它的相邻节点。

- 根节点（Root）：树中从哪个节点开始，就是根节点。

- 叶子节点（Leaf）：没有子节点的节点称为叶子节点。

- 度（Degree）：一个节点的子节点的个数称为该节点的度。

- 高度（Height）：树中的最长路径的边数。

4. 树的表示树可以用多种方式表示，最常用的方式有：孩子表示法、双亲表示法、孩子兄弟表示法和层次表示法。

5. 树的应用树在计算机科学中有广泛的应用，例如用于构建数据结构，构建层次化的目录结构等。

常见的树结构有二叉树、二叉搜索树（BST）、平衡二叉树（AVL）、红黑树、B树、B+树等。

二、树的遍历1. 深度优先遍历（DFS）深度优先遍历是一种递归的遍历方式，它分为先序遍历、中序遍历和后序遍历三种方式。

- 先序遍历（Preorder）先序遍历的顺序是先遍历根节点，然后递归地遍历左子树和右子树。

- 中序遍历（Inorder）中序遍历的顺序是先递归地遍历左子树，然后遍历根节点，最后递归地遍历右子树。

- 后序遍历（Postorder）后序遍历的顺序是先递归地遍历左子树和右子树，然后遍历根节点。

2. 广度优先遍历（BFS）广度优先遍历是一种逐层遍历的方式，它从根节点开始，按照层次遍历树的节点。

（3）如果2i＋1>n，则结点i无右孩子；否则，其 右孩子是结点2i＋1。
2021/7/21
20
完全二叉树上结点之间的关系
[I/2]
i
I+1
i
I+1
2i
2i+1
2i 2i+1 2(I+1) 2i+3 2(I+1) 2i+3
(a)I和i+1结点在同一层
(b)I和i+1结点不在同一层
2021/7/21
2021/7/21
22
顺序存储结构的特点
• 从树根起，自上层至下层，每层自左至右的给所有结点编号缺点是有可能对存储 空间造成极大的浪费，在最坏的情况下，一个深度为H且只有H个结点的右单支树 确需要2h-1个结点存储空间。
• 若经常需要插入与删除树中结点时，则不宜采用顺序存储结构。
2021/7/21
2021/7/21
26
6.3 遍历二叉树和线索二叉树
1 遍历二叉树
➢ 在二叉树的一些应用中，常常要求在树中查找 具有某种特征的结点，或者对树中全部结点逐 一进行某种处理。遍历二叉树即按某条搜索路 径巡访树中的每一个结点，使得每一个结点均 被访问一次，而且仅被访问一次。
➢ “访问”可以是对结点作各种处理，如输出结 点的信息等。
❖ 按层次顺序对二叉树进行遍历。
2021/7/21
29
遍历二叉树的递归算法
➢ 先序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（1）访问根结点；
（2）先序遍历左子树；
（3）先序遍历右子树。
➢ 中序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则

TElemType data ; int Lchild,Rchild; } SBNode; typedef struct｛
SBNode nodes[MAXSIZE]; } SBTree;
举例
结点 左子
右子
1
26 34
1
2
6
2
3
4
3
0
4
4
0
0
4
4
0
0
特点:
6
0
0
找子方便,找父 结点不便.
三、二叉链表存储结构
第一层 第二层
( A ( B ( E (K,L),F),C(G),D( H (M),I,J )))
第四层 第三层
二、基本术语
结点：包括一个数据元素及若干个指向其它子树 的分支；例如，A，B，C，D等。
叶结点：无后件结点为叶结点；如K，L，M。 根结点：无前件的结点为根；例如，A结点。
子结点：某结点后件为该结点的子结点；例如，
方法描述： 从根结点a开始访问， 接着访问左子结点b， 最后访问右子结点c。
即：
根
A 访问根结点 B 先序遍历左子树 C 先序遍历右子树
a
左子 右子
bc
二、中序法（InOrder）
方法描述：
从左子结点b开始访问，
接着访问根结点a，
最后访问右子结点c。
即：
根
A 中序遍历左子树 B 访问根结点 C 中序遍历右子树
计算机学院
自动化学院
各种社会组织机构；
在计算机领域中，用树表示源
程序的语法结构；
2101 2102
2103
在OS中，文件系统、目录等组
织结构也是用树来表示的。

二叉树的定义
合 交二或的叉者左树左为右是子空子由树集树n根(n， 组结>=点或 成0)者 ，个由 并结一 且A点个左的根右有结子限点树集及都合右两是构子棵二成树互叉，不树此相。集 二叉树的每个结点B至多只有两E棵子树（结点的度
最多为2）。 二叉树的子树有左右之C分，其次序F 不能任意颠倒。
D
G
HK
12 2021/5/9
(A(B(E(F),G),C,D(H(I),J,K(L))) (c) 广义表表示法
( b) 凹入表示法
12
树的基本术语
基本术语
结点：数据元素+若干指向子树的分支 结点的度：分支的个数（或 子树的个数） 叶子结点（终端结点）：度为零的结点 分支结点（非终端结点）：度不等于零的结点 树的度：树中所有结点的度的最大值 孩子结点：结点的子树的根结点为该结点的孩子结点 双亲结点：与孩子结点相对应的结点 兄弟结点：同一个双亲的孩子结点之间的互称 祖先结点：从根结点起到该结点所经分支上的所有结点 子孙结点：以某结点为根的子树中的任意结点
29 2021/5/9
0
0 00 0
29
二叉树的存储结构
顺序存储结构的缺点
由于一般二叉树必须仿照完全二叉树那样存储，可能 会浪费很多存储空间，单支树就是一个极端情况。
若经常需要插入与删除树中结点时，顺序存储方式需 要大量移动数据。
30 2021/5/9
30
二叉树的存储结构
链式存储结构
二叉链表 二叉链表结构：数据域、左指针域、右指针域
完全二叉树：树中所含的
a
n 个结点和满二叉树中编号
为 1 至 n 的结点一一对应。
b
c
d
e
f