树的定义和基本术语

树的基本构造

1. 什么是树

树是一种非线性的数据结构，它由一组以边连接的节点组成。树的基本构造包括根节点、子节点和父节点。树的结构具有层次性，每个节点除了根节点外，都有一个父节点，可以有零个或多个子节点。

树是一种重要的数据结构，在计算机科学中广泛应用。例如，文件系统就是一种树的结构，目录可以看作是树的节点，文件可以看作是树的叶子节点。

2. 树的基本术语

在学习树的基本构造之前，我们首先需要了解一些树的基本术语。

• 根节点（Root）：树的顶端节点，没有父节点。

• 子节点（Child）：一个节点可以有零个或多个子节点。

• 父节点（Parent）：一个节点的直接上级节点。

• 叶子节点（Leaf）：没有子节点的节点。

• 兄弟节点（Sibling）：具有相同父节点的节点。

• 子树（Subtree）：节点及其所有后代节点构成的树。

• 深度（Depth）：节点到根节点的边数。

• 高度（Height）：树中节点的最大深度。

3. 树的表示方法

树的结构可以通过不同的方式进行表示，常见的表示方法有以下几种：

3.1. 嵌套列表表示法

嵌套列表表示法是一种简单直观的表示方法。每个节点用一个列表表示，列表的第一个元素表示节点的值，后续元素表示子节点。例如，以下是一个用嵌套列表表示的树：

[1, [2, [4], [5]], [3, [6], [7]]]

3.2. 链表表示法

链表表示法是一种常用的表示方法。每个节点用一个对象表示，对象中包含节点的值和指向子节点的指针。例如，以下是一个用链表表示的树：

class TreeNode:

def __init__(self, value): self.value = value

self.children = []

3.3. 数组表示法

数组表示法是一种紧凑的表示方法。将树的节点按照层次遍历的顺序存储在一个数组中，数组中每个元素保存节点的值。例如，以下是一个用数组表示的树：

树（⼀）树的基本知识树结构

1） 了解树的定义、表⽰形式和基本术语

2） 了解⼆叉树的概念和性质

3） 掌握⼆叉树的⼏种遍历⽅法

4） 理解⼆叉树的遍历⽅法的C语⾔代码实现

5） 了解树的存储结构

6）了解哈夫曼树和哈夫曼编码的基本概念树的定义

树（Tree），是n（n≥0）个结点的有限集。若n=0时称为空树；若n>0时为⾮空树。

在⼀个⾮空树中，有且仅有⼀个称为根的结点。除根以外的其他结点划分为m（m>0）个互不相交的有限集T1，T2，. . .，Tm，其中每⼀个集合本⾝⼜是⼀棵树，并且称为根的⼦树（SubTree）。

例如下图是只有⼀个结点的树，这个唯⼀的结点也是这棵树的根节点：

再⽐如下⾯这棵树：

这棵树有9个结点，其中A是根，其余结点组成2个互不相交的⼦集：T1={B, D, E, I}，T2={C, F, G, H}，T1和T2都是A的⼦树，其本⾝也是⼀棵树：

在树T1中，B是根节点，其余结点⼜分为两个互不相交的⼦树：T11={D, I}，T12={E}。在树T11中D是根，其包含由结点I组成的⼦树。从这个概念上我们可以看出树的定义是⼀个递归的定义，即在树的定义中⼜⽤到了树的定义，⽽递归也将是实现树的相关操作的⼀个重要⼿段。树的表⽰⽅法树形表⽰法

⽬录结构表⽰

韦恩图表⽰法

⼴义表表⽰法

凹⼊表⽰法

树的基本概念（※有关术语※重点※）

以下图为例⼦：

结点：数据元素以及指向⼦树的分⽀。图中的A,B,C等都是结点。根结点：⾮空树中⽆前驱结点的结点。图中的A结点。结点的度(Degree)：结点拥有的⼦树数量。图中度为3的有：A、D，度为2的有：B、E、H，度为1的有：C、H。：树内各结点的度的最⼤值。上图中树的度为3。叶⼦结点(终端结点)(Leaf)：树没有⼦结点，即度为0的结点。图中的F，G，I，J，K，L，M 都是叶⼦结点。分⽀结点(分⽀点或⾮终端结点)：不属于叶⼦结点的结点，即度不为0的结点。A,B,C,D等都是分⽀结点。内部结点(中间结点)：根结点以外的分⽀结点。B,C,D，E，H等都是内部结点。层次(Level)：从根结点开始，根结点为第⼀层（A），根的⼦结点为第⼆层（B,C,D），以此类推。从根结点到树中某结点所经路径上的分⽀数称为该结点的层次。根结点的层次在不同教材中有规定为1，也有规定为0，其余结点的层次等于其双亲结点的层次加1。所以某结点在第n层，则其孩⼦就在第n+1层。（笔者这⾥默认根结点为1）结点深度：对任意结点x，x结点的深度表⽰为根结点到x结点的路径长度。所以根结点深度为0，第⼆层结点深度为1，以此类推；如深度为3的结点有：K，L，M，深度为2的结点有：E、F、G、H、I、J结点⾼度：对任意节点x，叶⼦节点到x节点的路径长度就是节点x的⾼度树的深度：树从根结点开始往下数，叶⼦结点所在的最⼤层数称为 树的深度。⼀棵树中结点的最⼤层次就是树的深度，深度定义是从上往下的。如图中树的深度为：4（默认根结点为1）树的⾼度：数值上和深度⼀样，⾼度定义是从下往上的。如图中树的⾼度为：4孩⼦-双亲(child-parent)：结点的⼦树的根称为该结点的孩⼦，该结点称为孩⼦的双亲。图中，E是L的双亲，L是E的孩⼦。兄弟结点(Sibling)：有⼀些结点，它们有共同的双亲，则称这些结点为兄弟结点。图中的H,I,J就是兄弟结点。堂兄弟结点：双亲在同⼀层上的结点称为堂兄弟结点。图中的G,H就是堂兄弟结点。结点的祖先：从根到该结点所经分⽀上的所有的结点。A,D,H结点都是结点M的祖先。结点的⼦孙：以某结点为根的⼦树中的任⼀结点。树的深度：树中结点的最⼤层次。图中的树的深度为4。有序树：树中结点的各⼦树从左⾄右右次序。⽆序树：树中结点的各⼦树⽆次序。森林：是m(m≥0)棵互不相交的树的集合。把根结点删除树就变成了森林；⼀棵树可以看成是⼀个特殊的森林；给森林中的各⼦树加上⼀个双亲结点，森林就变成了树。树⼀定是森林，⽽森林不⼀定是树。

树的基本术语

一、树的定义

树（Tree）是一种非线性的数据结构，它由n（n>=1）个节点组成的有限集合。其中，有且只有一个节点被称为根节点，其余节点被分为若干互不相交的、且看作一个整体（子树）来处理的、有限集合。

二、树的基本术语

为了更好地理解树的概念，我们需要了解一些树的基本术语：

1. 节点（Node）

节点是树的基本构成单元，每个节点包含数据和指向其他节点的指针或引用。节点可以有零个或多个子节点。

2. 根节点（Root）

根节点是树的顶端节点，它是树中唯一一个没有父节点的节点。根节点用于标识树的起点。

3. 父节点（Parent）

一个节点的直接上层节点称为其父节点。一个节点可以有零个或一个父节点。

4. 子节点（Child）

一个节点的直接下层节点称为其子节点。一个节点可以有零个或多个子节点。

5. 兄弟节点（Sibling）

拥有共同父节点的节点称为兄弟节点。兄弟节点之间的关系是平等的。 6. 叶节点（Leaf）

没有子节点的节点称为叶节点，也可以叫做终端节点。

7. 子树（Subtree）

子树是由一个节点及其所有子孙节点组成的树。每个子节点可以看作是该子树的根节点。

8. 深度（Depth）

节点的深度是指从根节点到该节点的唯一路径上的边的数量。根节点的深度为0。

9. 高度（Height）

节点的高度是指从该节点到最深叶节点的路径上的边的数量。叶节点的高度为0。整棵树的高度是指根节点的高度。

10. 祖先节点（Ancestor）

一个节点的祖先节点是从根节点到该节点的路径上的所有节点。

11. 后代节点（Descendant）

一个节点的后代节点是从该节点到叶节点的所有节点。

三、树的分类

树可以分为多种不同的类型，常见的树包括二叉树、二叉搜索树、平衡二叉树等。

1. 二叉树（Binary Tree）

二叉树是一种特殊的树结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树可以是空树，也可以是非空树。 2. 二叉搜索树（Binary Search Tree）

数据结构

Date

Time

1 第6章 树和二叉树

内容概要：本章主要介绍树，二叉树，最优二叉树的相关概念和操作，存储结构和相应

的操作，并在综合应用设计中，给出了对应算法的C语言实现。

教学目标

1．理解各种树和森林与二叉树的相应操作。

2．熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其他操作。

3．熟练掌握二叉树和树的各种存储结构及其建立的算法。

4．掌握哈夫曼编码的方法。

5．通过综合应用设计，掌握各种算法的C语言实现过程。

基本知识点： 树和二叉树的定义、二叉树的存储表示、二叉树的遍历以及其它操作的

实现、树和森林的存储表示、树和森林的遍历以及其它操作的实现、最优树和赫夫曼编码

重点：二叉树的性质、二叉树的遍历及其应用，构造哈夫曼树。

难点：编写实现二叉树和树的各种操作的递归算法。

本章知识体系结构：

课时安排：

6个课时 树的定义

树 树的性质 树的逻辑表示法 树形表示法

树的存储结构 双亲存储结构 文氏表示法

凹入表示法

括号表示法 孩子存储结构

孩子双亲存储结构

二叉树 二叉树的定义

二叉树的性质

二叉树的逻辑表示法（采用树的逻辑表示法）

二叉树的存储结构 二叉树的顺序存储结构

先序遍历

中序遍历

后序遍历 二叉树的遍历 二叉树的链式存储结构（二叉链）

由先序序列和中序序列构造二叉树

由中序序列和后序序列构造二叉树 二叉树的构造

二叉树的线索化

哈夫曼树 二叉树和树之间的差别

二叉树与树、森林之间的转换 二叉树和树

数据结构

Date

Time

2

课程 数据结构 教学教具 多媒体课件

学时 2 班级 06网络 教学日期/课时 /2课时

教学单元 第6章 树和二叉树

教学方法 讲授（PPT）

教学目标 掌握树、二叉树的基本概念和术语，二叉树的性质

教学重点 二叉树的定义、二叉树的性质、链式存储结构

教学难点 二叉树的性质、链式存储二叉树的基本操作

组

织

教

学 一、树的定义