数据结构C语言.pptx

:非线性结构,一个直接前驱,但可能有多个直接后继(1:n):过去许多书籍中都定义树为n≥1,曾经有“空树不是树”的说法,但现在树的定义已修改。注2:树的定义具有递归性,即树的定义中还有树。树(Tree)是n个(n≥0)结点组成的有限集合T。在任何一棵非空树中:(1)有且仅有一个结点称为根(root);(2)当n>1时,其余的结点可分为m(m>0)个互不相交的有限集合T1,T2,…,Tm。其中,每个集合本身又是一棵树,被称作这个根的子树(SubTree)。5A只有根结点的树ABCDEFGHIJKLM有子树的树根子树6树的抽象数据类型定义(见教材P118-119)ADTTree{数据对象D:数据关系R:基本操作P:}ADTTree若D为空集,则称为空树;//允许n=0若D中仅含一个数据元素,则R为空集;否则R={H},H是如下二元关系:①在D中存在唯一根元素root,在H下无前驱②若D-{root}≠Φ,则存在对D-{root}的一个划分,对任意j≠k,有Dj∩Dk=Φ,且<>∈H...③对应于D-{root}的划分,H-……有唯一一个划分,对任意j≠k,有Hj∩Hk=Φ。(Di,{Hi})D是具有相同特性的数据元素的集合。//至少有15个7基本操作:查找类插入类删除类8Root(T)//求树的根结点查找类:Value(T,cur_e)//求当前结点的元素值Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历9InitTree(&T)//初始化置空树插入类:CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树10ClearTree(&T)//将树清空删除类:DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树