第5章二叉树和树5.1树的基本概念5.2二叉树的概念5.3二叉树的遍历及应用5.4线索二叉树5.5树和森林5.6哈夫曼树和哈夫曼编码中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 1 中国科学技术大学 第5章 二叉树和树 5.1树的基本概念 5.2二叉树的概念 5.3二叉树的遍历及应用 5.4线索二叉树 5.5树和森林 5.6哈夫曼树和哈夫曼编码
5.1树的基本概念FHK中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 2 中国科学技术大学 5.1树的基本概念 • 树的定义（无序树） – n(n>=0)个数据元素（结点）的有限集D，若D为 空集，则为空树。否则： – 在D中存在唯一的称为根的数据元素 – 当n>1时，其余结点可分为m（m>0）个互不相交 的有限子集T1，T2，.，Tm，其中每个子集本 身又是一颗树，并成为根的子树
树的ADT描述ADT Tree?数据对象D：D是同类型数据元素的集合。数据关系R：若D=①，则称为空树；否则R是满足下列条件的二元关系：(1)D中存在唯一的称为根的元素root，它在R下无直接前驱。(2)若D-{root)=①，则R=①；否则存在D-{root)的一个划分D1，D2，...Dm(m>0)，对任意的jk(1≤j,k<m)，有DjnDk=O,且对任意的i(1<i<m)，存在唯一的数据元素xiEDi，有<root,xi>ER;(3)对应于D-(root)的划分，R-{<root，x1>,..<root，xm>}有唯一的一个划分R1，，Rm(m>0)，对任意的jk(1j,k<m)有RjnRk-の，且对任意的i(1<i<m)，Ri是Di上的二元关系。(Di，Ri)是一棵符合本定义的树，称为根root的子树。3ypb@ustc.edu.cn中国科学技术大学
ypb@ustc.edu.cn 3 中国科学技术大学 树的ADT描述 ADT Tree{ 数据对象D：D是同类型数据元素的集合。 数据关系R：若D=，则称为空树； 否则R是满足下列条件的二元关系： (1)D中存在唯一的称为根的元素root，它在R下无直接前驱。 (2)若D-{root}=，则R=；否则存在D-{root}的一个划分 D1，D2，.Dm(m>0)，对任意的j≠k(1≤j,k≤m)，有Dj∩Dk=， 且对任意的i(1≤i≤m)，存在唯一的数据元素xi∈Di，有<root， xi>∈R； (3)对应于D-{root}的划分，R-{<root，x1>,.<root，xm>}有 唯一的一个划分R1，.，Rm(m>0)，对任意的j≠k(1≤j,k≤m) 有Rj∩Rk=，且对任意的i(1≤i≤m)，Ri是Di上的二元关系。 (Di，Ri)是一棵符合本定义的树，称为根root的子树
基本操作：InitTree（&T)- DestroyTree（&T）- CreateTree(&T,definition)- TreeEmpty(T)TreeDepth(T)- Root(T)- Parent(T,x)- FirstChild （T，x) Nextsibling(T,x)InsertChild （&T,x,i,p)- DeleteChild (&T,xi)- Traverse(T,visitO)End ADT Tree中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 4 中国科学技术大学 基本操作： – InitTree（&T） – DestroyTree（&T） – CreateTree(&T,definition) – TreeEmpty(T) – TreeDepth(T) – Root(T) – Parent(T, x) – FirstChild（T，x） – Nextsibling(T,x) – InsertChild（&T,x,i,p） – DeleteChild（&T,x,i） – Traverse(T,visit()) }End ADT Tree
树的相关术语：结点：树的数据元素及指向子树的分支。结点的度：子树的个数。树的度：树中结点度的最大值。分支结点、叶子结点：度不为0、为0的结点。孩子：结点子树的根（后继）称为该结点孩子。双亲：结点前驱称该结点双亲兄弟、祖先、子孙：结点层次：根结点层次是1，其他结点层次是双亲层次+1。树深度：结点层次的最大值。无序树：交互子树不是不同的树。森林：m(m>=0)个不相交的树构成森林5中国科学技术大学vpb@ustc.edu.cn
ypb@ustc.edu.cn 5 中国科学技术大学 树的相关术语 • 结点：树的数据元素及指向子树的分支。 • 结点的度：子树的个数。 • 树的度：树中结点度的最大值。 • 分支结点、叶子结点：度不为0、为0的结点。 • 孩子：结点子树的根（后继）称为该结点孩子。 • 双亲：结点前驱称该结点双亲。 • 兄弟、祖先、子孙： • 结点层次：根结点层次是1，其他结点层次是双 亲层次+1。 • 树深度：结点层次的最大值。 • 无序树：交互子树不是不同的树。 • 森林：m(m>=0)个不相交的树构成森林