第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树的基本概念 B H 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=O,则称为空树； 否则R是满足下列条件的二元关系： (I)D中存在唯一的称为根的元素root,它在R下无直接前驱。 (2)若D-{root}=0,则R=☑；否则存在D-{root}的一个划分 D1,D2,.Dm(m>0),对任意的jk(1,k≤m),有DinDk=0, 且对任意的i(I≤ism),存在唯一的数据元素xi∈Di,有<root, xi>∈R; (3)对应于D-{root}的划分，R-{<root,xl>,<root,xm>}有 唯一的一个划分R1,.,Rm(m>0),对任意的j(1j,k≤m) 有RjORk=☑，且对任意的i(I≤ism),Ri是Di上的二元关系。 (Di,Ri是一棵符合本定义的树，称为根root的子树。 ypb@ustc.edu.cn 3 中国科学技术大学
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的子树
S 基本操作： -nitTree（&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 ypb@ustc.edu.cn 4 中国科学技术大学
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)个不相交的树构成森林。 ypb@ustc.edu.cn 5 中国科学技术大学
ypb@ustc.edu.cn 5 中国科学技术大学 树的相关术语 • 结点：树的数据元素及指向子树的分支。 • 结点的度：子树的个数。 • 树的度：树中结点度的最大值。 • 分支结点、叶子结点：度不为0、为0的结点。 • 孩子：结点子树的根（后继）称为该结点孩子。 • 双亲：结点前驱称该结点双亲。 • 兄弟、祖先、子孙： • 结点层次：根结点层次是1，其他结点层次是双 亲层次+1。 • 树深度：结点层次的最大值。 • 无序树：交互子树不是不同的树。 • 森林：m(m>=0)个不相交的树构成森林