7.2树的基本操作与存储 ◆树的基本操作 ◆树的存储结构 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 11 7.2 树的基本操作与存储 树的基本操作 树的存储结构
7.2.1树的基本操作 ◆树的基本操作通常有以下几种 () ) Initiate(t)初始化一棵空树t (2)Root(X)求结点x所在树的根结点 (3) Parent(t,X)求树t中结点x的双亲结点。 (4Chid(t,x,i)求树t中结点x的第个孩子结点。 5 RightSibling(t,)求树t中结点x的第一个右边兄弟 结点 (6) Insert(t,x,i,s)把以s为根结点的树插入到树t中 作为结点x的第棵子树 (⑦ Delete(t,ⅹ,i)在树t中删除结点x的第i棵子树 (8) Tranverse(t)是树的遍历操作,即按某种方式访问 树t中的每个结点,且使每个结点只被访问一次 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 12 7.2.1 树的基本操作 树的基本操作通常有以下几种： ⑴Initiate（t）初始化一棵空树t。 ⑵Root（x）求结点x所在树的根结点。 ⑶Parent（t，x）求树t中结点x的双亲结点。 ⑷Child（t，x，i）求树t中结点x的第i个孩子结点。 ⑸RightSibling（t，x）求树t中结点x的第一个右边兄弟 结点。 ⑹Insert（t，x，i，s）把以s为根结点的树插入到树t中 作为结点x的第i棵子树。 ⑺Delete（t，x，i）在树t中删除结点x的第i棵子树。 ⑻Tranverse（t）是树的遍历操作，即按某种方式访问 树t中的每个结点，且使每个结点只被访问一次
7.2.2树的存储结构 1.双亲表示法 由树的定义可以知道,树中的每个结点都有唯一的 双亲结点,根据这一特性,可用二组连续的存储空间( 维数组)存储树中的各个结点,数组中的一个元素表示树 中的一个结点,数组元素为结构体类型,其中包括结点本 身的信息以及结点的双亲结点在数组中的序号,树的这种 存储方法称为双亲表示法。其存储表示可描述为 define maxnode<树中结点的最大个数> typedef struct t elemtype data int parent cOdetype Nodetype t[MAXNODE 2021年1月21日 数据结构讲义 13
2021年1月21日 数据结构讲义 13 7.2.2 树的存储结构 1．双亲表示法 由树的定义可以知道，树中的每个结点都有唯一的一个 双亲结点，根据这一特性，可用一组连续的存储空间（一 维数组）存储树中的各个结点，数组中的一个元素表示树 中的一个结点，数组元素为结构体类型，其中包括结点本 身的信息以及结点的双亲结点在数组中的序号，树的这种 存储方法称为双亲表示法。其存储表示可描述为： #define MAXNODE <树中结点的最大个数> typedef struct { elemtype data; int parent; }NodeType; NodeType t[MAXNODE];
下图所示为树的双亲表示。图中用 parent域的值为-1表示 4该结点无双亲结点,即该结点是一个根结点 序号data A D E 100111 E 2345678 G H 244 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 14 下图所示为树的双亲表示。图中用parent域的值为-1表示 该结点无双亲结点，即该结点是一个根结点
树的双亲表示法对于实现 Parent(t,x)操作和 Root(x)操作很方便。但若求某结点的孩子结点, 即实现Chid(t,x,i)操作时,则需査询整个数组。 此外,这种存储方式不能够反映各兄弟结点之间的关 系,所以实现 RightSibling(t,x)操作也比较困难 在实际中,如果需要实现这些操作,可在结点结构中 」增设存放第一个孩子的域和存放第一个右兄弟的域, 就能较方便地实现上述操作了。 2021年1月21日 数据结构讲义 15
2021年1月21日 数据结构讲义 15 • 树的双亲表示法对于实现Parent（t，x）操作和 Root（x）操作很方便。但若求某结点的孩子结点， 即实现Child（t，x，i）操作时，则需查询整个数组。 此外，这种存储方式不能够反映各兄弟结点之间的关 系，所以实现RightSibling（t，x）操作也比较困难。 在实际中，如果需要实现这些操作，可在结点结构中 增设存放第一个孩子的域和存放第一个右兄弟的域， 就能较方便地实现上述操作了