第4单元 非线性数据结构 树、二叉树 计算机软件基础 The software bas ic of computer 主讲:赵英良 西安交通大学 计算机教学实验中心
下一页 计算机软件基础 The software basic of computer 主讲：赵英良 西安交通大学 计算机教学实验中心 第4单元 非线性数据结构 树、二叉树
上一单元内容提要 栈 栈、栈顶指针 顺序存储、共享栈、链栈、入栈、出栈操作 、队列 队列、顺序存储、队头指针、队尾指针、约定 循环队列、链式队列(带头结点)、入队、出队 串 串、长度、空串(空格串)、子串、主串、 位置、子串位置、串相等、串的操作、 停止放映 串的存储结构、紧缩存储、非紧缩存储 四、数组:行、列优先顺序存储,矩阵的压缩存储 第2页
下一页 上一页 停止放映 第 2 页 上一单元内容提要 一、栈 栈、栈顶指针 顺序存储、共享栈、链栈、入栈、出栈操作 二、队列 队列、顺序存储、队头指针、队尾指针、约定 循环队列、链式队列（带头结点）、入队、出队 三、串 串、长度、空串（空格串）、子串、主串、 位置、子串位置、串相等、串的操作、 串的存储结构、紧缩存储、非紧缩存储 四、数组：行、列优先顺序存储，矩阵的压缩存储
、树型结构及其基本概念 树形结构是以分支关系来 定义的层次结构。在客观 西安交大 世界中树形结构广泛存在, 并应用于: 管理学院 电信学院医学院 人类社会的族谱、家谱 行政区域划分管理; 各种社会组织机构;信通系电子系计算机系计教中心 在计算机领域中,用树 表示源程序的语法结构; 在0S中,文件系统、目 录等组织结构也是用树计0计 计12 来表示的。 停止放映 张三李四王五 第3页
下一页 上一页 停止放映 第 3 页 一、树型结构及其基本概念 ⚫ 树形结构是以分支关系来 定义的层次结构。在客观 世界中树形结构广泛存在， 并应用于： –人类社会的族谱、家谱、 行政区域划分管理； –各种社会组织机构； –在计算机领域中，用树 表示源程序的语法结构； –在OS中，文件系统、目 录等组织结构也是用树 来表示的。 西安交大 管理学院……电信学院 医学院 信通系 电子系 计算机系 计教中心 …… 计01 计02 计12 张三 李四 王五
1.树的定义(逻辑结构) ●树是一种数据结构: Tree=(D, R) 其中: D是具有相同特性的n个数据元素的集合; R是D上逻辑关系的集合,且满足: 在D中存在唯一的称为根的数据元素,没 有前趋; D中其余数据元素都有且只有一个前趋; D中所有元素,或有若干个互不相同的后 继(子树),或无后继(叶结点); 停止放映 则称Tree为树。 第4页
下一页 上一页 停止放映 第 4 页 1.树的定义（逻辑结构） ⚫ 树是一种数据结构： Tree=（D，R） 其中： D 是具有相同特性的n个数据元素的集合； R 是D上逻辑关系的集合，且满足： –在D中存在唯一的称为根的数据元素，没 有前趋； –D中其余数据元素都有且只有一个前趋； –D中所有元素，或有若干个互不相同的后 继（子树），或无后继（叶结点）； 则称Tree为树
树的定义(递归结构) 树是一个或多个结点组成的有限集合 T,有一个特定结点称为根,其余结 点分为m(m≥0)个互不相交的集合 T1,T2,…,Tm。每个集合又是一棵 树,被称为这个根的子树 ●树是一种递归结构,可以包含一个结 点,该结点包含不相交的树的指针 (即子树)。 停止放映 第5页
下一页 上一页 停止放映 第 5 页 树的定义（递归结构） ⚫ 树是一个或多个结点组成的有限集合 T，有一个特定结点称为根，其余结 点分为m（m0）个互不相交的集合 T1，T2，…,Tm。每个集合又是一棵 树，被称为这个根的子树。 ⚫ 树是一种递归结构，可以包含一个结 点，该结点包含不相交的树的指针 （即子树）
2.树的表示形式 (1)一般邢式 (2)嵌套形式 (3)凹入形式 (4)广义表形式 停止放映 第6页
下一页 上一页 停止放映 第 6 页 2.树的表示形式 (1) 一般形式 (2) 嵌套形式 (3) 凹入形式 (4) 广义表形式
树的表示(一般形式) 停止放映 (b) (a)只有根结点的树 (b)一般的树 第7页
下一页 上一页 停止放映 第 7 页 树的表示(一般形式) A B C D E F K L G H I J M A (a) (b) (a)只有根结点的树 (b)一般的树
树的表示(嵌套形式) B H G 停止放映 第8页
下一页 上一页 停止放映 第 8 页 树的表示(嵌套形式) A C G B F E K L M H D J I
树的表示(凹入形式) A E K F C D 停止放映 第9页
下一页 上一页 停止放映 第 9 页 树的表示(凹入形式) A B E K L C D F G H I J M
树的表示(广义表形式) 第一层 第二层 (A(B(E(K, L, F), C(G),D(H(M),I,J))) 第四层 停止放映 第三层 第10页
下一页 上一页 停止放映 第 10 页 树的表示(广义表形式) ( A ( B ( E (K,L),F),C(G),D( H (M),I,J ))) 第一层 第二层 第三层 第四层