下载此文档

第五章 树.ppt


文档分类:IT计算机 | 页数:约149页 举报非法文档有奖
1/149
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/149 下载此文档
文档列表 文档介绍
第五章树树和森林的概念二叉树二叉树遍历线索化二叉树树与森林堆Huffman树*树和森林的概念有根树:一棵有根树T,简称为树,它是n(n≥0)个结点的有限集合。当n=0时,T称为空树;否则,T是非空树。记作r是一个特定的称为根(root)的结点,它只有直接后继,没有直接前驱根以外的其他结点划分为m(m0)个互不相交的有限集合T1,T2,…,Tm,每个集合又是一棵树,并且称为根的子树*每棵子树的根结点有且仅有一个直接前驱,但可以有0个或多个直接后继*DACBIJHGFEMLK树的基本术语子女:若结点的子树非空,结点子树的根即为该结点的子女。双亲(父亲):若结点有子女,该结点是子女的双亲(父亲)。兄弟:同一结点的子女互称为兄弟。度:结点的子女个数即为该结点的度;树中各个结点的度的最大值称为树的度。*分支结点:度不为0的结点即为分支结点,亦称为非终端结点。叶结点:度为0的结点即为叶结点,亦称为终端结点。祖先:根结点到该结点的路径上的各个结点都是该结点的祖先。子孙:某结点的所有下属结点,都是该结点的子孙。*结点的层次:规定根结点在第一层,其子女结点的层次等于它的层次加一。以下类推。结点的深度:结点的深度即为结点的层次;离根最远结点的层次即为树的深度。1层2层4层3层depth=4DACBIJHGFEMLKheight=4*结点的高度:规定叶结点的高度为1,其双亲结点的高度等于它的高度加一。树的高度:等于根结点的高度,即根结点所有子女高度的最大值加一。有序树:树中结点的各棵子树T1,T2,…是有次序的,即为有序树。无序树:树中结点的各棵子树之间的次序是不重要的,可以互相交换位置。森林:森林是m(m≥0)棵树的集合。*树的抽象数据类型template<classT>classTree{//对象:树是由n(≥0)个结点组成的有限集合。在//类界面中的position是树中结点的地址。在顺序//存储方式下是下标型,在链表存储方式下是指针//型。T是树结点中存放数据的类型,要求所有结//点的数据类型都是一致的。public:Tree(); ~Tree();*BuildRoot(constT&value);//建立树的根结点 positionFirstChild(positionp); //返回p第一个子女地址,无子女返回0 positionNextSibling(positionp); //返回p下一兄弟地址,若无下一兄弟返回0 positionParent(positionp); //返回p双亲结点地址,若p为根返回0TGetData(positionp);//返回结点p中存放的值boolInsertChild(positionp,T&value);//在结点p下插入值为value的新子女,若插//入失败,函数返回false,否则返回true*boolDeleteChild(positionp,inti); //删除结点p的第i个子女及其全部子孙结//点,若删除失败,则返回false,否则返回true voidDeleteSubTree(positiont);//删除以t为根结点的子树boolIsEmpty();//判树空否,若空则返回true,否则返回falsevoidTraversal(void(*visit)(positionp));//遍历以p为根的子树};*

第五章 树 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数149
  • 收藏数0 收藏
  • 顶次数0
  • 上传人陈潇睡不醒
  • 文件大小1.56 MB
  • 时间2019-12-11