线性结构和非线性结构课件.ppt

线性结构和非线性结构课件.ppt线性结构和非线性结构线性结构的特点是逻辑结构简单,易于进行查找、插入和删除等操作,其主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述。非线性结构是指,在该结构中至少存在一个数据元素,有两个或两个以上的直接前驱(或直接后继)元素。树型结构和图型就是其中十分重要的非线性结构,可以用来描述客观世界中广泛存在的层次结构和网状结构的关系。*树二叉树二叉树遍历线索二叉树树和森林哈弗曼树第5章树和二叉树**树的定义树是由n(n0)个结点组成的有限集合T。如果n=0,称为空树;如果n>0,则T满足以下两个条件:有且只有一个特定的称之为根(root)的结点,它只有直接后继,但没有直接前驱;除根以外的其它结点划分为m(m0)个互不相交的有限集合T1,T2,…,Tm,其中每个集合又是一棵树,并且称之为根的子树(subTree)。每棵子树的根结点有且仅有一个直接前驱,但可以有0个或多个直接后继。*树的表示树型表示bacghdefij*凹入表表示abdeijfcgh*嵌套集合表示嵌套括号(广义表)表示ijdfghabcea(b(d,e(i,j),f),c(g,h))*结点(node)结点的度(degree)结点的子树个数分支(branch)结点度不为0的结点叶(leaf)结点度为0的结点子女(child)结点某结点子树的根结点双亲(parent)结点某个结点是其子树之根的双亲12344*兄弟(sibling)结点具有同一双亲的所有结点祖先(ancestor)结点若树中结点k到ks存在一条路径,则称k是ks的祖先子孙(descendant)结点若树中结点k到ks存在一条路径,则称ks是k的子孙结点所处层次(level)根结点的层数为1,其余结点的层数为双亲结点的层数加1树的高度(depth)树中结点的最大层数有序树子树的次序不能互换无序树子树的次序可以互换森林互不相交的树的集合*(BinaryTree),该集合或者为空,或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。*