网站大量收购独家精品文档,联系QQ:2885784924

第6章 树和二叉树(一).ppt

  1. 1、本文档共87页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第5章 树形结构 树和二叉树 5.1 树 1树的定义 树是n(n≥0)个结点的有限集合,在任一棵非空树中: (1)有且仅有一个称为根的结点; (2)其余结点可分为个互不相交的集合,而且这些集合中的每一集合都本身又是一棵树,称为根的子树。 2. 树的逻辑结构 1)树中只有根结点没有前趋 2)除根外其余结点都有且仅一个前趋; 3)树中的每个结点可以有零个或多个后继 树是一种分枝结构 ,除了一个称为根的结点外,每个元素都有且仅有一个直接前趋,有且仅有零个或多个直接后继。 5.1.2 树的表示形式 5.1.3 常用术语 1) 结点(node):包含一个数据元素及若干指向子树的分支。 2) 结点的度(degree):结点拥有的子树个数。 3)树的度:树中最大的结点度。 4)叶子(leaf)结点:也叫终端结点,是度为0的结点; 5)分支节点:度不为0的结点,也叫非终端结点。一棵树除叶子节点外,其它都是非终端结点。 5.1.3 常用术语 6)孩子(child)结点:结点的子树的根称为该结点的孩子结点。 7)双亲(parents)结点:孩子结点的上层结点,称为这些结点的双亲结点。 8)兄弟(sibling)结点:同一双亲的孩子结点。 9)子孙结点:一个结点的所有子树中的结点,称为该结点的子孙结点。 10)祖先节点:从树根到达一个结点的路径上通过的所有结点,称为该结点的祖先结点。 5.1.3 常用术语 11)结点层(level):从根结点开始算起,根为第一层;根的孩子为第2层结点;…… 12)树的深度(depth):树中最大的结点层。 13)森林(forest):互不相交的树集合。 14)有序树:如果一棵树中结点的各个子树从左到右是有次序的,若交换位置则构成不同的树,则称这棵树是有序树,如家族树。 15)无序树:不考虑子树顺序的树。 5.1.4 树的存储结构 5.1.4 树的存储结构 树的存储结构有很多,既可以采用顺序存储结构,也可以采用链式存储结构。但无论采用哪种存储方式,都要求存储结构不仅能存储各结点本身的数据信息,还要能惟一地反映树中各结点之间的逻辑关系。 5.1.4 树的存储结构 1. 双亲表示法 树中每个结点的孩子可能有任意多个,但其双亲只有一个。双亲表示法是通过结点与双亲之间的关系将树中结点组织在一起。该存储结构以一组连续空间存储树的结点,同时在每个结点上附设一个指示器,指示其双亲结点的位置。 2. 孩子表示法 孩子表示法是树的一种链式存储结构,其设计思想有两种,其一是建立一个多重链表,存放树中每个结点及其多棵子树,即每个结点由一个数据字段和多个指针字段组成,数据字段中存放该结点的数据元素,每个指针字段中的指针指向一棵子树的根结点。 3. 孩子兄弟表示法 孩子兄弟表示法又称二叉树表示法,或二叉链表表示法。即以二叉链表作为树的存储结构,链表中结点的两个字段分别指向该结点的第一个孩子结点和下一个兄弟结点,分别命名为firstchild字段和nextsibling字段。 利用孩子兄弟表示法存储树,能方便地实现树的各种操作。特别是易于实现查找某结点的孩子结点的运算。 1.双亲表示法 用一组连续的存储空间存储树中的各结点,树中除根外的每个结点都有惟一的一个双亲结点,所以每个结点存储元素本身的信息和结点的双亲结点的位置。 双亲表示的存储结构类型定义如下: #define MAX 100 typedef struct PTNode { TelemType data; int parent; /* 双亲位置字段*/ }PTNode; typedef struct { PTNode nodes[MAX]; int n; /* 结点数*/ }PTree; 2、孩子链表法 孩子表示法是通过保存每个结点的孩子结点的位置,表示树中结点之间的结构关系。每个结点的孩子结点用单链表存储,再用含n个元素的结构数组指向每个孩子链表。 孩子链表存储结构类型定义如下: typedef struct CTNode /* 孩子结点*/ { int child; struct CTNode *next; }*ChildPtr; typedef struct { TelemType data; ChildPtr firstchild; /* 孩子链表头指针*/ }CTBox; typedef struct { CTBox nodes[MAX]; int n, *r; /* 结点数和根的位置*/ }CTree; 3.

您可能关注的文档

文档评论(0)

好文精选 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档