资源描述：
《软件技术基础课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、非线性结构1非线性结构非线性结构：至少存在一个数据元素有两个或两个以上的直接前驱（或直接后继）元素的数据结构。非线性结构主要有树(TREE)结构图(GRAPH)结构2树3树型结构树形结构例：用于描述层次结构的关系，如：人类的族谱、各种社会关系、各类分类编码；操作系统的文件系统、编译程序的语法树；Internet中的DNS（域名系统）分等级的分类方案均可用层次结构来表示，即可由此导出树形结构。4树的定义树(Tree)是n(n≥0)个结点的有限集合T，对于任意一棵非空树，它满足：当n＝0时，称为空树
2、；当n>0时，有且仅有一个特定的称为根(root)的结点。当n＞1时，其余结点可分为m(m＞0)个互不相交的有限集T1，T2，….，Tm，其中每个集合本身又是一棵树，称为根的子树。树的定义是一个递归定义。5树的定义ABCDEFGHIJK由11个结点集合T组成的树，T={A,B,C,D,E,F,G,H,I,J,K}，其中结点A是根结点，除结点A外，其余结点分成3个互不相交的集合T1={B,E,F,G}，T2={C}，T3={D,H,I,J,K}，形成了以结点A为树根的3棵子树T1、T2、T3。而这
3、三棵子树本身又是一棵树。例如子树T3的根结点是D，其余又分成3个互不相交的集合T31={H}，T32={I}，T33={J,K}，形成了以结点D为树根的3棵子树T31，T32，T33。而T31、T32为只有一个根结点的树。6树的基本术语ABCDEFGHIJK第1层第2层第3层第4层7树的基本术语结点(node)结点的度(degree)分支(branch)结点叶(leaf)结点子(child)结点父(parent)结点兄弟(sibling)结点祖先(ancestor)结点子孙(descendant
4、)结点结点所处层次(level)树的高度(depth)树的度(degree)见书p488基本术语树中每个结点的分支数称为结点的度。树的度是树中结点的最大度数。度为零的结点为叶结点(Leaf)，称度不为的零结点为分支结点。树中结点的子树的根结点称为该结点的子结点。相反，称该结点为子结点的父结点。9基本术语一个结点的直接后继结点是兄弟结点，他们拥有相同的父结点。祖先结点是从根结点达到某结点所经过分支上的所有结点称为该结点的祖先。子孙结点以某结点为根的子树中的任一结点都称为该结点的子孙。10基本术语树
5、中结点的层次(Level)从根结点开始，根为一层结点，其子结点为二层结点，依次类推。叶子结点为最下层结点。这种分层的好处是树中结点的最大层数称为该树的高度（深度）。森林(Forest)是m(m≥0)棵互不相交的树的集合(可以看成是把一棵树的根结点去掉，所得到的子树构成森林)。如果树中每个结点的子结点规定从左到右是有次序的（不许随意改动），那么，称该树为有序树。否则称为无序树。11树的性质一树中结点总数等于树中所有结点的度之和加1。所谓结点的度是指结点拥有的子树个数。根据树的定义知：在一棵树中，除
6、根结点之外，每个结点有且仅有一个父结点，即每个结点与指向它的一个分支结点一一对应。因而，除树的根结点外的结点数等于树中所有结点的分支数（度数）。由此可知：树中的结点总数应为所有结点的度之和加1。12树的性质二度为k的树的第i层最多有ki-1个结点（i≥1)。(用数学归纳法)：所谓树的度是指树内各结点的度的最大值。当i=1时，在树中的第一层只有一个结点（根结点），结论正确。设：对于第i-1层（i＞1)命题也成立，即度为k的树的第i-1层最多有k(i-1)-1=ki-2个结点。由树的度的定义知：度为
7、k的树中每个结点最多有k个子结点，因此：第i层上结点总数最多为第i-1层上结点数的k倍，即第i层上最多有k*ki-2=ki-1个结点，与命题相符。故：度为k的树的第i层最多有ki-1个结点(i＞1)。13树的性质三深度为h的k叉树最多有个结点只有当深度为h的k叉树（即该树的度为k）上每一层都达到该层最多结点总数时，该树的结点总数将达到最大，因而有：14树的性质四具有n个结点的k叉树的最小深度为不小于的最小整数。具有n个结点的k叉树的深度为h，若该树的前h-1层都是满的，即每一层的结点数都为ki-
8、1个（1≤i≤h-1），第h层（最后一层）的结点数可能满，也可能不满，则该树具有最小的深度。由性质三知：即：kh-1＜n(k-1)+1≤kh15树的性质四取以k为底的对数后得：h-1＜logk(n(k-1)+1)≤h16树的表示树型表示凹入表表示abdeijfcghacghjbdefi这是最流行的表示方法17树的表示嵌套集合表示ijdfghabce嵌套括号表示a(b(d,e(i,j),f),c(g,h))18树的基本操作初始化求指定结点所在树的根结点求指定结点的父结点求指定结点的某一孩子结点求指
