计算机软件基础 (2)new

《计算机软件基础 (2)new》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、计算机软件基础Thesoftwarebasicofcomputer主讲：赵英良西安交通大学计算机教学实验中心第4单元非线性数据结构树、二叉树上一单元内容提要一、栈栈、栈顶指针顺序存储、共享栈、链栈、入栈、出栈操作二、队列队列、顺序存储、队头指针、队尾指针、约定循环队列、链式队列（带头结点）、入队、出队三、串串、长度、空串（空格串）、子串、主串、位置、子串位置、串相等、串的操作、串的存储结构、紧缩存储、非紧缩存储四、数组：行、列优先顺序存储，矩阵的压缩存储2一、树型结构及其基本概念树形结构是以分支关系来定义的层次结构。在客观世界中树形结构广泛存在，并应

2、用于：人类社会的族谱、家谱、行政区域划分管理；各种社会组织机构；在计算机领域中，用树表示源程序的语法结构；在OS中，文件系统、目录等组织结构也是用树来表示的。西安交大电信学院管理学院医学院……信通系电子系计算机系计教中心……计01计02计12张三李四王五31.树的定义（逻辑结构）树是一种数据结构：Tree=（D，R）其中：D是具有相同特性的n个数据元素的集合；R是D上逻辑关系的集合，且满足：在D中存在唯一的称为根的数据元素，没有前趋；D中其余数据元素都有且只有一个前趋；D中所有元素，或有若干个互不相同的后继（子树），或无后继（叶结点）；则称Tree为

3、树。4树的定义（递归结构）树是一个或多个结点组成的有限集合T，有一个特定结点称为根，其余结点分为m（m0）个互不相交的集合T1，T2，…,Tm。每个集合又是一棵树，被称为这个根的子树。树是一种递归结构，可以包含一个结点，该结点包含不相交的树的指针（即子树）。52.树的表示形式(1)一般形式(2)嵌套形式(3)凹入形式(4)广义表形式6树的表示(一般形式)ABCDEFKLGHIJMA(a)(b)(a)只有根结点的树(b)一般的树7树的表示(嵌套形式)ACGBFEKLMHDJI8树的表示(凹入形式)ABEKLCDFGHIJM9树的表示(广义表形式)(A

4、(B(E(K,L),F),C(G),D(H(M),I,J)))第一层第二层第三层第四层103.基本术语（一）结点包括一个数据元素及若干个指向其它子树的分支；例如，A，B，C，D等。叶结点无后继结点为叶；如K，L，M。支结点度不为0的结点为支结点；如B，C，D等。根结点无前趋的结点为根；例如，A结点。结点度结点拥有的子树数数目；例如，A的度为3。树的度树中结点的最大度数；上述树的度为3。11基本术语（二）子结点某结点子树的根为该结点的子结点；例如，结点A的子结点为B，C，D。父结点相对于某结点子树的根，称该结点为子树根的父结点；例如子结点C，B，D的父

5、结点为A。兄弟结点同一父亲的孩子之间互为兄弟结点（Sibling）；H，I，J互为兄弟。路径结点的序列n1，n2，…,nk(K1)是一条路径.长度长度等于路径中结点数-1.12基本术语（三）阶层（层次）结点的特性值，根结点的阶层为1，子结点为2，依次类推。如阶层1有结点A，阶层2有结点B，C，D。高度（深度）一棵树的最大阶层值为树的高度或深度。例如，结点A到M的高度为4。森林0棵或多棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。有序如果将树中结点的各子树看成从左至右是有顺序的（即不能互换），则称该树为有序树。否则，称为无序树。13

6、4.树的操作PARENT（n，T）得到树中n的父亲结点；ROOT（T）求树的根，返回树根的位置。CHILD（T，x，i）求树T中结点x的第i个孩子结点。CREATE（x，T1，T2，…,Tk)生成一个结点x,下带子树T1,T2,…,Tk。DELETE(x,i)删除结点x的第i个子树。TRAVERSE（T）遍历树T。按次序依此访问树中各个结点，且使每个结点只能被访问一次。145.树的实现(存储结构)数组实现方法（双亲表示法）链表实现方式（孩子表示法）二叉链表实现方式（孩子兄弟表示法）15树的实现(存储结构)(1)数组实现方法（双亲表示法）用数组存储树的

7、结点信息，在每个结点中附设一个指示器指示其双亲结点在数组中的位置。结构描述：#defineMAXSIZE100typedefstructPTNode{TElemTypedata；intparent；}PTNode；typedefstruc{PTNodenodes[MAXSIZE]；intn；}Ptree；结点数据元素包含：数据、父结点位置16双亲表示法举例123456789结点序号123456789123456789011223555方法特点：找根容易，找子结点难，要遍历整个数组。17树的存储结构（二）(2)链表实现方式（孩子表示法）把每个结点的孩子

8、结点排列起来，组成一个线性表，且以单链表作为存储结构，则n个结点有n个孩子链表。结构描述为：typedefs