资源描述：
《数据结构动画版_演示6.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、实例树的定义二叉树定义与性质下一章第五章树树与二叉树的存储结构及其相互转换树和二叉树的遍历二叉树的应用五子棋游戏……..……..…...…...…...…...树的实例1234567891011123次十二小球问题树的实例1212345678第一次：平1～8标准910111121平9～11标准轻12轻第二次：第三次：12重12重重12标准9109不平11标准11平11轻轻12标准910109不平11标准11平11重10412345678第一次：重9～12标准23平目标在234重平2，3标准第二次：第三次：2不平4标准重目标在1或81918轻目标在567轻56578175691011
2、3平1标准不平8标准平5，6标准不平7标准6/(root)libuseretcbinmathdsswyintaoxieStack.cppQueue.cppTree.cpp人类的族谱各种社会关系各类分类编码编译程序的语法树Internet中的DNS（域名系统）UNIX文件系统结构树的实例树是一类重要的非线性数据结构，是以分支关系定义的层次结构定义：树(tree)是n(n>0)个结点的有限集T，其中：有且仅有一个特定的结点，称为树的根(root)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)特点
3、：树中至少有一个结点——根树中各子树是互不相交的集合至少存在一个数据元素有两个或两个以上的直接前驱（或直接后继）元素的数据结构树的定义~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)A只有根结点的树ABCDEFGHIJKLM有子树的树根子树ADTTree{数据对象D:D是具有相同特性的数据元素的集合数据关系R:若D为空集，则称为空树否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n>1时
4、，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树基本操作：查找类操作插入类操作删除类操作}ADTTree树的抽象数据类型定义基本操作：TreeEmpty(T)初始条件：树T已存在操作结果：空树，返回TRUE;否则FALSETreeDepth(T)初始条件：树T已存在操作结果：返回T的深度查找类：Root(T)初始条件：树T已存在操作结果：返回T的根Value(T,cur_e)初始条件：树T已存在,cur_e是T中结点操作结果：返回cur_e的值Parent(T,cur_e)初始条件：树T已存在,cur
5、_e是T中结点操作结果：若cur_e是T中非根结点,返回其双亲;否则,返回空树的抽象数据类型定义LeftChild(T,cur_e)初始条件：树T已存在,cur_e是T中结点操作结果：若cur_e是T中非叶子结点,返回其最左孩子;否则,返回空RightChild(T,cur_e)初始条件：树T已存在,cur_e是T中结点操作结果：若cur_e是T中非叶子结点,返回其最右孩子;否则,返回空TraverseTree(T,visit())初始条件：树T已存在操作结果：按某种次序对T的每个元素调用函数visit()查找类：基本操作：树的抽象数据类型定义插入类：InsertChild(&T,
6、&p,i,c)初始条件：树T存在,p指向T中结点,1≤i≤p指结点度+1,非空树c与T不相交操作结果：将以c为根的树插入为T中p指结点的第i棵子树CreateTree(&T,definition)初始条件：definition给出树的定义操作结果：按definition构造树TAssign(T,cur_e,value)初始条件：树T已存在,cur_e是T中结点操作结果：结点cur_e赋值为valueInitTree(&T)操作结果：构造空树T基本操作：树的抽象数据类型定义DeleteChild(&T,&p,i)初始条件：树T存在,p指向T中结点,1≤i≤p指结点度操作结果：删除T中
7、p指结点的第i棵子树ClearTree(&T)初始条件：树T已存在操作结果：将树T清为空树DestroyTree(&T)初始条件：树T已存在操作结果：销毁树T删除类：基本操作：树的抽象数据类型定义结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)——结点拥有的子树数叶子(leaf)——度为0的结点，终端结点分支结点——度不为0的结点，非终端结点孩子(child)——结点子树的根称为该结点的孩子双亲(parents)——孩子结点
