第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,kER;(3)对应于D-(root)的划分，R-{,..}有唯一的一个划分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，有∈R； (3)对应于D-{root}的划分，R-{,.}有 唯一的一个划分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)个不相交的树构成森林
树的性质·性质l:n个结点，每个结点度d,则：n=d,+1i=l·性质2:度为k的树第i层的结点个数最多k(i-1)kh -1性质3：深度为h的k叉树，最多结点数为k-1性质4:具有n个结点的k叉树深度最小为logk(n(k -1)+1)6中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 6 中国科学技术大学 树的性质 • 性质1:n个结点，每个结点度di ,则： • 性质2:度为k的树第i层的结点个数最多 k (i-1) • 性质3:深度为h的k叉树，最多结点数为 • 性质4:具有n个结点的k叉树深度最小为 • 1 1 = + = n i n di 1 1 − − k k h logk (n(k −1) +1)
5.2二叉树(binary Tree)>二叉树的定义和基本术语一是n(n>0)个元素的有限集，或为空集(n=0），或含有唯一的根元素，其余元素分成两个互不相交的子集，每个子集本身也是一颗二叉树。分别称为根的左子树右子树。一空树：集合为空的二叉树一结点的度：非空子树的个数一左孩子，右孩子一叶子结点：左右子树均空的结点；度为零一二叉树的深度：二叉树中叶子结点的最大层次数中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 7 中国科学技术大学 ➢ 二叉树的定义和基本术语 – 是n(n0)个元素的有限集，或为空集(n=0) ，或含有唯 一的根元素，其余元素分成两个互不相交的子集，每 个子集本身也是一颗二叉树。分别称为根的左子树、 右子树。 – 空树:集合为空的二叉树 – 结点的度：非空子树的个数 – 左孩子，右孩子 – 叶子结点：左右子树均空的结点；度为零 – 二叉树的深度：二叉树中叶子结点的最大层次数 5.2二叉树（binary Tree）
满二叉树（fullbinarytree）：所有分支结点度为2，叶子结点在同一层次一完全二叉树（completebinarytree）：深度h，h-1为满二叉树，h层的结点都集中在左侧9101112138X1415101112(a）满二叉树(b）完全二叉树8中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 8 中国科学技术大学 – 满二叉树（full binary tree）：所有分支结点度为2， 叶子结点在同一层次 – 完全二叉树（complete binary tree）：深度h，h-1为 满二叉树，h层的结点都集中在左侧
二叉树ADT描述ADT BinaryTree:数据对象D：D是同类型数据元素的集合。数据关系R：若D=①，则称BinaryTree为空二叉树：否则R是满足下列条件的二元关系：(1)在D中存在唯一的称为根的元素root，它在R下无直接前驱；(2)若D-{root)=①，则R=① ;否则存在D-{(root)={Dl ,Dr) 且DInDr=O ;(3)若DI+①，则DI中存在唯一的元素xl，ER，且存在DI上的关系RlcR；若Dr+①，则Dr中存在唯一的元素xr，ER，且存在Dr上的关系RrcR ；R=[,,Rl ,Rr} ;(4)(DI，RI)是一棵符合本定义的二叉树，称为根的左子树;(Dr，Rr)是一棵符合本定义的二叉树，称为根的右子树。9中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 9 中国科学技术大学 二叉树ADT描述 ADT BinaryTree{ 数据对象D：D是同类型数据元素的集合。 数据关系R：若D=，则称BinaryTree为空二叉树； 否则R是满足下列条件的二元关系： (1)在D中存在唯一的称为根的元素root，它在R下无直接前驱； (2)若D-{root}=，则R=；否则存在D-{root}={Dl，Dr}， 且Dl∩Dr=； (3)若Dl≠，则Dl中存在唯一的元素xl，∈R，且存在 Dl上的关系RlR；若Dr≠，则Dr中存在唯一的元素xr， ∈R，且存在Dr上的关系RrR；R={， ，Rl，Rr}； (4)(Dl，Rl)是一棵符合本定义的二叉树，称为根的左子树； (Dr，Rr)是一棵符合本定义的二叉树，称为根的右子树
基本操作P：·RightChild(T,e)·InitBiTree(&T).LeftSibling(T,e)·DestroyBiTree(&T)·RightSibling(T,e)·CreateBiTree(&T,definition)·BiTreeEmpty(T).InsertChild(&T,p,LR,C)·BiTreeDepth(T).DeleteChild(&T,p,LR)·Traverse(T)·Parent(T,e)·LeftChild(T,e) //EndADT BinaryTree10中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 10 中国科学技术大学 •InitBiTree(&T) •DestroyBiTree(&T) •CreateBiTree(&T,definition) •BiTreeEmpty(T) •BiTreeDepth(T) •Parent(T,e) •LeftChild(T,e) •RightChild(T,e) •LeftSibling(T,e) •RightSibling(T,e) •InsertChild(&T,p,LR,C) •DeleteChild(&T,p,LR) •Traverse(T) 基本操作P： ｝//End ADT BinaryTree