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={<A,B>,<A,C>,<A,D B,E>,<B,F>,C,G>,<D,H>, D,D>,<D,J>,<F,K>,<FL> <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={<A,B>,<A,C>,<A,D>, <B,E>,<B,F>,<C,G>,<D,H>, <D,I>,<D,J>,<F,K>,<F,L>, <J,M>}