数据结构第5章ppt课件.ppt

《数据结构第5章ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1第五章树与二叉树宋会英12第五章树与二叉树5.1树的基本概念5.2二叉树5.3二叉树的存储表示5.5线索二叉树5.6树和森林5.9哈夫曼树与哈夫曼编码5.8堆5.4二叉树的遍历及其应用5.7树和森林的遍历及其应用235.1树的基本概念5.1.1树的定义和术语两种树：自由树与有根树。①自由树：一棵自由树Tf可定义为一个二元组Tf=(V,E)其中V={v1,...,vn}是由n(n＞0)个元素组成的有限非空集合，称为顶点集合。E={(vi,vj)

2、vi,vjV,1≤i,j≤n}是n-1个序对的集合，称为边集合，E中的元素(vi,vj）称为边或分支。34自由树②有根树：

3、一棵有根树T，简称为树，它是n(n≥0)个结点的有限集合。当n=0时，T称为空树；否则，T是非空树，记作45r是一个特定的称为根(root)的结点，它只有直接后继，但没有直接前驱；根以外的其他结点划分为m(m0)个互不相交的有限集合T1,T2,…,Tm，每个集合又是一棵树，并且称之为根的子树。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。5a.直观表示法：用圆圈表示结点，元素写在圆圈中，连线表示元素之间的关系。根在上，叶子在下（即树向下生长）。acebdfg树的常见表示方法6b.嵌套集合表示法：根据树的集合定义，写出集合划分。{a,{b,{e},

4、{f}},{c},{d,{g}}}c.文氏图表示法：集合表示的一种直观表示，用图表示集合。acbefdgacebdfg直观表示法7d.目录表示法（凹入表示法）：将一棵树描述为一本书，书-章-节-小节-acebdfg直观表示法1a2b3e3f2c2d3g目录表示法8结点:结点的度:树的度?叶子结点?分支结点?数据元素+若干指向子树的分支分支的个数即结点拥有的子树数一棵树中各结点度数的最大值度为零的结点度大于零的结点DHIJM树的基本术语9子女结点、双亲结点兄弟结点、堂兄弟祖先结点、子孙结点结点的层次:树的深度：(从根到结点的)路径：由从根到该结点所经分支和结点构成。AB

5、CDEFGHIJMKL规定根结点的层次为1，它的孩子为第2层……树中叶子结点所在的最大层次1011等于根结点的高度，即根结点所有子女高度的最大值加一。高度：树的高度？有序树：无序树？森林？规定叶结点的高度为1，其双亲结点的高度等于它的高度加一。树中结点的各棵子树T0,T1,…是有次序的，即为有序树。树中结点的各棵子树之间的次序是不重要的，可以互相交换位置。是m（m≥0）棵树的集合。11ABCDEFGHIJKLM结点A的度：结点M的度：叶子：结点A的孩子：结点I的双亲：结点B，C，D为兄弟树的度：结点A的层次：结点M的层次：树的深度：结点F，G为堂兄弟结点A是结点F，G

6、的祖先30B,C,DK，L，F，G，M，I，J314D412135.1.2树的抽象数据类型classTree{//对象:树是由n(≥0)个结点组成的有限集合。在//类界面中的position是树中结点的地址。在顺序//存储方式下是下标型,在链表存储方式下是指针//型。DataType是树结点中数据的类型,要求所有//结点的数据类型都是一致的。public:Tree();~Tree();1314BuildRoot(constDataType&value);//建立树的根结点positionFirstChild(positionp);//返回p第一个子女地址,无子女返回0

7、positionNextSibling(positionp);//返回p下一兄弟地址,若无下一兄弟返回0positionParent(positionp);//返回p双亲结点地址,若p为根返回0DataTypegetData(positionp);//返回结点p中存放的值boolInsertChild(positionp,DataType&value);//在结点p下插入值为value的新子女,若插//入失败,函数返回false,否则返回true1415boolDeleteChild(positionp,inti);//删除结点p的第i个子女及其全部子孙结//点,若删

8、除失败,则返回false,否则返回truevoidDeleteSubTree(positiont);//删除以t为根结点的子树boolIsEmpty();//判树空否,若空则返回true,否则返回falsevoidTraversal(void(*visit)(positionp));//遍历以p为根的子树};15讨论：1.树的逻辑结构(特点)：一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。2.树的存储结构讨论1：树是非线性结构，该怎样存储？————仍然有顺序存储、链式存储方式。16可规定为：从上至下、