数据结构与算法—赵玉兰 第4章 树与二叉树

数据结构与算法—赵玉兰

计算机学院 软件工程系

树的定义和相关术语 4.2 二叉树 4.3 树和森林 4.4 森林与二叉树的关系 4.5 Huffman树与编码 4.11

数据结构与算法—赵玉兰

计算机学院 软件工程系

树的定义和相关术语 4.2 二叉树 4.3 树和森林 4.4 森林与二叉树的关系 4.5 Huffman树与编码 4.12

数据结构与算法—赵玉兰

计算机学院 软件工程系

树形结构是一种非线性结构，应用十分广泛。 如：行政机构、目录、家谱等。 内蒙古大学

理工学院数 物 电 学 理 子 系 系 系

计算机学院 计 算 机 系 网 络 中 心

生命科学学院

外国语学院日 语 系

人文学院 汉 历 哲 语 史 学 系 系 系

计 生 环 动 生 资 英 算 物 境 物 物 源 语 中 系 系 中 工 所 系 心 心 程 中 心

行政机构3

数据结构与算法—赵玉兰

计算机学院 软件工程系

磁 盘 目 录

数据结构与算法—赵玉兰

计算机学院 软件工程系

红 楼 梦 家 谱

数据结构与算法—赵玉兰

计算机学院 软件工程系

树和森林的概念树的定义 树是由 n (n ≥ 0) 个结点组成的有限集合。如果 n = 0,称为空树；如果 n > 0,则 有一个特定的称之为根(root)的结点，它只有

直接后继，但没有直接前驱； 除根以外的其他结点被划分到 m (m ≥ 0) 个

互不相交的子集T1, T2, …, Tm中，每个子集又 都构成一棵树，称之为根的子树(sub tree)。

数据结构与算法—赵玉兰

计算机学院 软件工程系

树的特点

每棵子树的根结点有且仅有一个直接前 驱，但可以有0个或多个直接后继。 树是一种典型的“层次结构”,体现出 “一对多”的关系。 AB E K L F C G H M7

D I J

数据结构与算法—赵玉兰

计算机学院 软件工程系

例4.1: Tree=(D, R)D={Book, C1, C2, C3, S1.1, S1.2, S2.1, S2.2, S2.3, S2.1.1, S2.1.2}R={ <Book, C1>, <Book, C2>, <Book, C3>, <C1, S1.1>, <C1, S1.2>, <C2, S2.1>, <C2, S2.2>, <C2, S2.3>, <S2.1, S2.1.1>, <S2.1, S2.1.2> } Book C1 C2 C3 Chapter

S1.1

S1.2

S2.1

S2.2

S2.3

SectionSub-Section

S2.1.1 S2.1.2

数据结构与算法—赵玉兰

计算机学院 软件工程系

基本术语：主要来源于家谱和自然界中的树。

双亲、子女(parent, child): 若<a,b> R,则称a是b的双亲，b是a 的子女(孩子); 结点度(degree): A 结点所拥有的子女数； 叶子(leaf): B C D 度为0的结点； 分枝结点(branch node): E F G H I J 度大于0的结点； L M 树的度：树中最大的结点的度；K9

数据结构与算法—赵玉兰

计算机学院 软件工程系

结点所在的层次(level):根在第1层，其它任一结点 所在的层是其双亲的层数加1。 深度或高(depth):树中结点的最大层数。 兄弟(sibling):同一双亲的结点间互称兄弟。 堂兄弟(cousin):同层的非兄弟结点互称堂兄弟。 1 A2 3 E4

B F

C G H

D I J

K

L

M

数据结构与算法—赵玉兰

计算机学院 软件工程系

祖先(descendant) 、子孙(ancestor):一个结点

是它所有子树中结点的祖先，而子树中的这些

结点都是它 的子孙。

路径(path):是一个结点序列n1,n2,n3,…,nk,并且 前1个结点是后1个结点的双亲；它的长度是k-1。

有序树(ordered

tree):将树中每个结点的各子树 看出是从左到右是有次序的(不能互换);否则是无序 树。A B C无序树

A C B11

有序树

数据结构与算法—赵玉兰

计算机学院 软件工程系

结点A、B、C的度分别为： 3、2、1 结点A的孩子： B,C,D 结点B的孩子： B E,F 树的度： E 3K LF A C G H

叶子： K,L,F,G,M,I,J 结点I的双亲： D 结点L的双亲： E 结点B,C,D为兄弟 结点K,L为兄弟 结点A的层次： 1 结点M的层次： 4 树的深度： 412

D I J

M

结点F,G为堂兄弟 结点A是结点F,G的祖先

数据结构与算法—赵玉兰

计算机学院 软件工程系

森林(Forest):m(m≥0)棵互不相交的树的集合。森林A F H

根

A B C F G D H I J

B

C

D E

G

I

J

EK

K由根的各子树构成的森林

由三棵树构成的森林

数据结构与算法—赵玉兰

计算机学院 软件工程系

树的定义和相关术语 4.2 二叉树 4.3 树和森林 4.4 森林与二叉树的关系 4.5 Huffman树与编码 4.114

数据结构与算法—赵玉兰

计算机学院 软件工程系

二叉树 (Binary Tree)二叉树的定义一棵二叉树是一个结点的有限集合， 该集合或者为空，或者是由一个根结点加 上两棵分别称为左子树和右子树的、互不 相交的二叉树组成。

二叉树的五种不同形态：L R L R15

数据结构与算法—赵玉兰

计算机学院 软件工程系

自然界很神奇！16