多个后继)
数据对象 D：
D是具有相同特性的数据元素的集合。
数据关系 R：
若D为空集，则称为空树 。 否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n>1时，其余结点可分为m (m>0)个互
不相交的有限集T1, T2, …, Tm，其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。
插入类：
InitTree(&T) // 初始化置空树
CreateTree(&T, definition) // 按定义构造树
Assign(T, cur_e, value) // 给当前结点赋值
InsertChild(&T, &p, i, c) // 将以c为根的树插入为结点p的第i棵子树
删除类：
E
F
G
H
学校的行政关系、书的层次结构、人类的家族血缘关
系等。 树形结构 —— 结点间具有分层次的连接关系
对比树型结构和线性结构 的结构特点
线性结构
第一个数据元素 (无前驱)
最后一个数据元素 (无后继)
其它数据元素 (一个前驱、
一个后继)
树型结构
根结点 (无前驱)
多个叶子结点 (无后继)
其它数据元素 (一个前驱、
2020/8/20
8
A
B
C
D
E
F GH I
J
树的定义
树的递归定义的各子树T1,T2,…,Tm的相对 次序是重要的，即树是有序的。
2020/8/20
9
树定义(图示)
A
2020/8/20
A
B
C
E
F
G
H
KL
M
T1
10
T2
D
I
J
T3
树形结构
全校学生档案管理的组织方式
A
D
B
C
E F GH
A
B
C
D
现实世界中，能用树的结构表示的例子：
A
B
C
D
E F GH I J
KL
M
树的常见表示方法
1.直观表示法
用圆圈表示结点，元素写在圆圈中， 连线表示元素之间的关系，根在上， 叶子在下（即树向下生长）
A
B
C
D
E F GH I J
KL
M
树的常见表示方法
2.集合表示法
根据树的集合定义，写出集合划分。
孩子，双亲，兄弟，堂兄：结点的子树的根称为该 结点的孩子；该结点称为孩子的双亲；同一个双亲 的孩子之间互称兄弟；其父结点是兄弟的结点互称 堂兄。
2020/8/20
5
概念 祖先：从根结点到该结点所经分支上的所有结点。
子孙：以某结点为根的子树中的任一结点都称为该 结点的子孙。
层次：结点在树结构中的层（一般定义根为1层）。 深度：树中结点的最大层次称为树的深度。
有序树：
子树之间存在确定的次序关系。
无序树：
子树之间不存在确定的次序关系。
森林：
是m（m≥0）棵互 不相交的树的集合
F
root
A
B
C
D
E F GH I J
KL
M
任何一棵非空树是一个二元组 Tree = （root，F）
其中：root 被称为根结点 F 被称为子树森林
注意：
１．根没有双亲，叶子没有孩子 ２．堂兄弟的双亲是兄弟关系吗 ？
基本操作： 查找类 插入类 删除类
查找类：
Root(T) // 求树的根结点 Value(T, cur_e) // 求当前结点的元素值 Parent(T, cur_e) // 求当前结点的双亲结点 LeftChild(T, cur_e) // 求当前结点的最左孩子 RightSibling(T, cur_e) // 求当前结点的右兄弟 TreeEmpty(T) // 判定树是否为空树 TreeDepth(T) // 求树的深度 TraverseTree( T, Visit() ) // 遍历
M
内部结点: 除根之外的分支结点
孩子结点: 结点的子树的根称为该结 点的孩子（后继）
双亲结点:
一个结点是它各子树的根 结点的双亲（前驱）D
HI J
兄弟结点: 具有相同双亲的结点
M
祖先: 从根结点到该结点路径上所有 结点都称为该结点的祖先。
子孙: 该结点所有子树上的结点都 称为该结点的子孙
D
HI J
ClearTree(&T) // 将树清空 DestroyTree(&T) // 销毁树的结构
DeleteChild(&T, &p, i) // 删除结点p的第i棵子树
基本术语
结点: 树中的一个数据元素
结点的度: 分支的个数
树的度: 树中所有结点的度的最大值
叶子结点: 度为零的结点
D
HI J
分支结点: 度大于零的结点
M
(从根到结点的)路径：
A
B
C
D
由从根到该结点 E 所经分支和结点构成
F GH I J
KL
M
结点的层次: 根结点定义为第１层，根的
儿子定义为第２层，以此类 推，记作Ｌ（ｖ）
树的深度： 树中叶子结点所在的最大层次
堂兄弟: 双亲在同一层上的结点
有向树：
(１) 有确定的根； (２) 树根和子树根之间为有向关系。
公开课第六章
树和二叉树
掌握其定义、表示方法、 基本性质、存储结构
学习目标
掌握树的定义、表示方法、基本 性质、存储结构和遍历算法；
掌握二叉树的定义、基本性质、 存储结构、和各种运算。
概念示例
结点
结点的度(Degree) 叶子（Leaf)或终端结点
树的示例
分支结点或非终端结点
树的度 层次(Level) 树的深度(Depth)
A
B
C
D
孩子（child) 双亲（Parent)
E
F
G
H
I
J
兄弟(Sibling)
K
L
M
祖先
子孙 2020/8/20
4
树的概念
结点：一个数据元素及若干指向其子树的分支；
结点的度：结点拥有的子树的数目。
树的度：树内各结点的度的最大值；
叶子（终端结点）：度为0的结点； 分支结点（非终端结点）：度不为0的结点；除根 结点外，也称内部结点；
有序树：结点的子树在树中的位置固定，不能互换， 称有序树。
无序树：子树在树中的位置可以互换。 树的度：结点度的最大值
森林：m(m≥0)棵互不相交的树的.1 树的类型定义 6.2 二叉树的类型定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林的表示方法 6.7 树和森林的遍历 6.8 哈夫曼树与哈夫曼编码
树的定义 树(Tree)是n(n>=0)个结 点 的 有 限 集 。 n=0 时 称 为空树。
（注：有人定义树不能为空）
有且仅有一个称为根的 结点（Root）；
n>1时，其余结点可分为 m(m>0) 个 互 不 相 交 的 有 限集T1,T2,…,Tm,其中每 个集合又是一棵树，称 为子树(SubTree)