华北电力大学：数据结构_第6章(树)

North China Electric Power University 数据结构 Data Structure 华北电力大喾计算机斛学与工程柰 Dept of Computer Science& Engineering of North China Electric Power University

数据结构 North China Electric Power University Data Structure 华北电力大学计算机科学与工程系 Dept. of Computer Science&Engineering of North China Electric Power University

North China Electric Power University I 第五章树 ★基本术语 ★树的基本操作和存储结构 ★二义树 ★二义树的通历及线索二又树 树的逼历 ★哈夫曼树及其发用

第五章 树 ★ 基本术语 ★ 树的基本操作和存储结构 ★ 二叉树 North China Electric Power University ★ 二叉树的遍历及线索二叉树 ★ 树的遍历 ★ 哈夫曼树及其应用

North China Electric Power University I ★基本术语 树型结构是一类重要的非线性数据结构,其中以二叉 树最为常用。树是以分支关系定义的层次结构,它为计算机 应用中出现的具有层次关系或分支关系的数据提供了一种自 然的表示方法。用树结构描述的信息模型在客观世界普遍存 在 桌面 我的文档 计算机科学与工程系 曰里我的电脑 曰本地磁盘(C) +0 Documents and Settings G Pro 办公室〉教研室><实验侴〉<研究室 a VipInfo + C WINDOWS 品DvD驱动器(D) 图φ本地磁盘(E:) 本地磁盘(F:) 品PAL3D15K4(G:) 团本地磁盘(H:) 工应 由φ本地磁盘(w:) 地磁盘(Y:) 用 田控制面板 研簖研 共享文档 yh的文档 网上邻居 回收站

★基本术语 North China Electric Power University 树型结构是一类重要的非线性数据结构，其中以二叉 树最为常用。树是以分支关系定义的层次结构，它为计算机 应用中出现的具有层次关系或分支关系的数据提供了一种自 然的表示方法。用树结构描述的信息模型在客观世界普遍存 在。 计算机科学与工程系 办公室 教研室 实验室 研究室 行 政 办 公 室 总 支 办 公 室 计 算 机 教 研 室 软 件 教 研 室 软 件 实 验 室 综 合 实 验 室 数 字 逻 辑 实 验 室 组 成 原 理 试 验 室 管 理 信 息 系 统 研 究 室 知 识 工 程 研 究 室 微 机 应 用 研 究 室

North China Electric Power University I 树的定义:树是n(m≥0)个结点的有限集T在一棵非空 树中: 1)有且仅有一个特定的称为根的结点 2)当n>1时其余结点可分为m(m>0)个互不相交的有 限集合T1,T2,Tm,其中每个集合本身又是一棵树,并 且称为根的子树 树的定义可以用如下形式化描述来表示 Tree=(D, 其中D是具有相同特性的数据元素的集合;若D只含有 个元素,则R为空集否则R是D上的某个二元关系H 的集合,即R={H,H为如下描述的二元关系:

North China Electric Power University 树的定义：树是n(n≥0)个结点的有限集T,在一棵非空 树中： 1)有且仅有一个特定的称为根的结点； 2)当n>1时,其余结点可分为m(m>0)个互不相交的有 限集合T1 ,T2 ,…,Tm,其中每个集合本身又是一棵树，并 且称为根的子树。 树的定义可以用如下形式化描述来表示： Tree=(D,R) 其中:D是具有相同特性的数据元素的集合;若D只含有 一个元素,则R为空集,否则R是D上的某个二元关系H 的集合,即R={H},H为如下描述的二元关系:

1)有且仅有一个结点没有前驱,该结点被称为树的根; 2)除树根结点外,其余每个结点有且仅有一个前驱结点 3)包含树根结点在内的每个结点,可以有任意多个(包含 0个)后继 树的几种表示方法: 1)二元组表示 D=A, B, CD,E,E,G, H, LJ, K, L, M R={,,,,C,G>,, D,D>,,, <oM

树的几种表示方法： 1)有且仅有一个结点没有前驱，该结点被称为树的根； 2)除树根结点外，其余每个结点有且仅有一个前驱结点； 3)包含树根结点在内的每个结点，可以有任意多个(包含 0个)后继。 A B C D E F G H I J K L M 1)二元组表示 D={A,B,C,D,E,F,G,H,I,J,K,L,M} R={,,, ,,,, ,,,, }

North China Electric Power University I 2)集合图表示 3)凹入表表示 C(G ④B D 4)广义表表示法:A(B(E,F(K,L),C(G),D(H,,J(M)

North China Electric Power University 4) 广义表表示法：A(B(E,F(K,L)),C(G),D(H,I,J(M))) A E B K L F C G H I M D J 2)集合图表示 3)凹入表表示

North China Electric Power University I 树型结构和线性结构的比较 树型结构 线性结构 根结点无前驱结点 第一个数据元素无前驱 多个叶子结点无后继 最后一个数据元素无后继 其它数据元素有一个 其它元素有且仅有一个直接 前驱和多个后继 前驱和一个直接后继

North China Electric Power University 树型结构和线性结构的比较 树型结构 线性结构 根结点无前驱结点 第一个数据元素无前驱 多个叶子结点无后继 最后一个数据元素无后继 其它数据元素有一个 前驱和多个后继 其它元素有且仅有一个直接 前驱和一个直接后继

North China Electric Power University I 树中的基本术语: 1结点、结点的度、树的度 2叶子结点、分支结点 3孩子、双亲、兄弟、 画①@ 堂兄弟、祖先、子孙 4结点的层次、树的深度 5有序树和无序树 6森林

North China Electric Power University 树中的基本术语： A B C D E F G H I J K L M 1.结点、结点的度、树的度 2.叶子结点、分支结点 3.孩子、双亲、兄弟、 堂兄弟、祖先、子孙 4.结点的层次、树的深度 5.有序树和无序树 6.森林 B C D E F G H I J K L M

North China Electric Power University I 树的性质: 性质:树中的结点数等于所有结点的度加。Q 证明:除树的根结点外每个 结点有且只有一个直 接前驱,除树的根结 点之外的结点数等于E 所有结点的分支数 性质2:度为k的树中第层至多有k1个结点。 性质3:深度为h的k叉树至多有(贴-1)(k<1)个结点。 性质4具有n个结点的k叉树的最小深度为og(n(k1)+1)

North China Electric Power University 树的性质： 性质1:树中的结点数等于所有结点的度加1。 A B C D E F G H I J K L M 证明：除树的根结点外每个 结点有且只有一个直 接前驱，除树的根结 点之外的结点数等于 所有结点的分支数。 性质2:度为k的树中第i层至多有k i-1个结点。 性质3:深度为h的k叉树至多有(kh -1)/(k-1)个结点。 性质4:具有n个结点的k叉树的最小深度为logk (n(k-1)+1)

North China Electric Power University I ★树的基本操作和存储牿构 树的基本运算 1Root(T):求树T的根结点,若T为空则返回结果为“空” 2 Parent(T,x):求结点x在树T上的双亲结点,若结点x是树T的根 结点或x不在树T中,则返回结果为“空”。 3 Initiate(T:置T为空树。 4 Child(Tx):求树T上结点x的第i个孩子,若x不在树T上或x 没有第个孩子,则返回结果为“空”。 5 Create(x,T1,T2,T建立一棵以x为根,以T1,T2,T为第1,2, 3.k棵子树的树。 6 Delete(①,x,i:删除树T上结点x的第子树,若结点x无第棵子 树,则为空操作。 7 Traverse(T:按某个次序依次访间树中的各个结点,并使每个结 点只被访问一次

North China Electric Power University ★树的基本操作和存储结构 树的基本运算 1.Root(T):求树T的根结点，若T为空则返回结果为“空”。 2.Parent(T,x):求结点x在树T上的双亲结点，若结点x是树T的根 结点或x不在树T中，则返回结果为“空”。 3.Initiate(T):置T为空树。 4.Child(T,x,i):求树T上结点x的第i个孩子，若x不在树T上或x 没有第i个孩子，则返回结果为“空”。 5.Create(x,T1 ,T2 ,…,Tk ):建立一棵以x为根，以T1 ,T2 ,…,Tk为第1,2, 3…,k棵子树的树。 6.Delete(T,x,i):删除树T上结点x的第i棵子树，若结点x无第i棵子 树，则为空操作。 7.Traverse(T):按某个次序依次访问树中的各个结点，并使每个结 点只被访问一次