资源描述：
《数据结构树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第六章树和二叉树第六章树和二叉树第六章树和二叉树6.1树的有关概念6.2二叉树6.3二叉树的遍历6.4遍历的应用6.5*线索二叉树（简单介绍）6.6树和森林6.7哈夫曼树及应用第六章树和二叉树6.1树的有关概念1.树的概念2.树的应用3.树的表示树的有关术语5树的基本操作6.1树的有关概念1．树的定义定义：树是n个结点的有限集合。在任一棵非空树中： （1）有且仅有一个称为根的结点；。 （2）其余结点可分为m个互不相交的有限集合，而且这些集合中的每一集合本身又是一棵树，称为根的子树。树是递归结构，在树的定义中又用到了树的概念JIACBDHGFE树结构（除了一个称为根的结点外）每个元素都有且仅
2、有一个直接前趋，有且仅有零个或多个直接后继。6.1树的有关概念从逻辑结构看： 1）树中只有根结点没有前趋； 2）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继； 4）除根外的其他结点，都存在唯一条从根到该结点的路径；5）树是一种分枝结构JIACBDHGFE6.1树的有关概念2．树的应用 1）树可表示具有分枝结构关系的对象例1．家族族谱例2．单位行政机构的组织关系、系统功能模块图6.1树的有关概念2）树是常用的数据组织形式 有些应用中数据元素之间并不存在间分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。例3计算机的文件系统 不论是DOS文件系统还是wi
3、ndow文件系统，所有的文件是用树的形式来组织的。MyComputerC:D:E:etcWINDOWSProgramFilesPictureMusic…………………………………………6.1树的有关概念3、树的基本术语1）结点的度：结点所拥有的子树的个数。2）树的度：树中各结点度的最大值。CGBDEFKLHMIJADA=3DB=2DC=1DG=0DTree=36.1树的有关概念3）叶子结点：度为0的结点，也称为终端结点。4）分支结点：度不为0的结点，也称为非终端结点。CGBDEFKLHMIJA叶子结点：{K,L,F,G,M,I,J}分支结点：{A,B,C,D,E,H}6.1树的有关概念5）孩
4、子、双亲：树中结点的子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点；6）兄弟：具有同一个双亲的孩子结点互称为兄弟。CGBDEFKLHMIJA孩子结点：{B,C,D}双亲结点：{A}兄弟结点：{E，F}6.1树的有关概念7）路径：如果树的结点序列n1,n2,…,nk有如下关系：结点ni是ni+1的双亲，则把n1,n2,…,nk称为一条由n1至nk的路径；路径上经过的边的个数称为路径长度。CGBDEFKLHMIJA结点序列：{nA,nB,nE,nK}路经长度=36.1树的有关概念8）祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖先，而y称为x的子孙
5、。CGBDEFKLHMIJA6.1树的有关概念9）结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。10）树的深度：树中所有结点的最大层数，也称高度。1层2层4层3层高度＝4CGBDEFKLHMIJC6.1树的有关概念11）有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的（即不能互换），称这棵树为有序树；反之，称为无序树。ACBGFEDACBGFED数据结构中讨论的一般都是有序树6.1树的有关概念12）森林：m(m≥0)棵互不相交的树的集合。CBDEFKLHJA树中每一个结点的子树的集合即为森林。6.1树的有关概念树结构和线性结构的比较线
6、性结构树结构第一个数据元素根结点（只有一个）无前驱无双亲最后一个数据元素叶子结点(可以有多个)无后继无孩子其它数据元素其它结点一个前驱,一个后继一个双亲,多个孩子一对一一对多6.1树的有关概念4、树的基本操作树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操作：1）InitTree(&T);//构造空树T2）DestroyTree(&T);//销毁树T3）CreateTree(&T,definition);//按definition构造树T4）ClearTree(&T);//将树T清为空树5）TreeEmpty(T);//判断树T是否为空树6）TreeDepth(T);//求树
7、的深度7）Root(T);//返回树T的根值6.1树的有关概念8）Value(T,&cur_e);//求树T中结点cur_e的值9）Assign(T,cur_e,value);//把value赋值给树T的cur_e结点10）Parent(T,cur_e);//求树T中非根结点cur_e的双亲11）LeftChild(T,cur_e);//求树T中非叶子结点cur_e的左孩子12）RightSibling(T,cur_e)
