North China Electric Power University I 树的存储结构 1孩子表示法 由于树中每个结点可能有多棵子树,可用多重链表,即 每个结点有多个指针域,其中每个指针指向一棵子树的根结 点,则结点形式有如下两种 data child1 child2 childd data degree child1 child2 I childd (2) 在第一种形式中,结点是同构的,存储空间浪费较大, 在第二种形式中,结点是不同构的,虽能节约存储空间,但 实现和运算很不方便
North China Electric Power University 树的存储结构 1.孩子表示法 由于树中每个结点可能有多棵子树，可用多重链表，即 每个结点有多个指针域，其中每个指针指向一棵子树的根结 点，则结点形式有如下两种： data child1 child2 … childd data degree child1 child2 … childd 在第一种形式中，结点是同构的，存储空间浪费较大， 在第二种形式中，结点是不同构的，虽能节约存储空间，但 实现和运算很不方便。 (1) (2)
North China Electric Power University I 可以把每个结点的孩子结点排列起来,看成一个线性表, 且以单链表作存储结构,n个结点有n个孩子链表,n个头指针 又组成一个线性表,为了便于查找,可用向量表示。 Type link- f node; noderecord child: Elem Type; next:link: end; tree=Arrayll. maxn of link; 2 123456 23456 4|[51 222
North China Electric Power University 可以把每个结点的孩子结点排列起来，看成一个线性表， 且以单链表作存储结构，n个结点有n个孩子链表，n个头指针 又组成一个线性表，为了便于查找，可用向量表示。 Type link=↑node; node=record child:ElemType; next:link; end; tree=Array[1..maxn] of link; 1 2 3 4 5 6 2 3 4 5 6 ^ ^ 1 2 3 4 5 6 ^ ^ ^ ^ 2 3 4 5 6 ^ ^ 1 2 3 4 5 6 0 1 1 2 2 2 ^ ^ ^ ^
North China Electric Power University I 2孩子兄弟表示法 又称二叉链表表示法,即以二叉链表作树的存储结构,链 表中结点的两个链域分别指向该结点的第一个孩子结点和下 个兄弟结点,分别命名为frst-chid和 nextsibling。 data first-child nextsibling Q 2| |5 6 在孩子兄弟表示法中,要找结点x的第个孩子,则只要先从 first-child域找到第一个孩子结点上,然后沿着该孩子结点的 o nextsibling域连续走i步,便可找到的第个孩子
North China Electric Power University 2.孩子兄弟表示法 又称二叉链表表示法，即以二叉链表作树的存储结构，链 表中结点的两个链域分别指向该结点的第一个孩子结点和下一 个兄弟结点，分别命名为first-child和nextsibling。 data first-child nextsibling 1 2 3 4 5 6 1 2 3 4 5 6 ^ ^ ^ ^ ^ ^ ^ 在孩子兄弟表示法中，要找结点x的第i个孩子,则只要先从 first-child域找到第一个孩子结点上，然后沿着该孩子结点的 nextsibling域连续走i-1步，便可找到x的第i个孩子
North China Electric Power University I 3双亲表示法 用一个数组顺序地存放树的各个结点,结点存放的顺序是 任意的。每一结点有两个域组成:数据域和指针域,分别存储 树上结点中的数据元素和用于指示本结点之双亲所在的存储结 点。 指针域的类型定义有两种:高级语言中的指针类型和整型 或子界类型,与之对应的链表分别称为动态链表和静态链表。 静态双亲链表的定义: const size={结点数}; 结点序号 data parent 110 pe node=record 31 data: ElemType; 21 parent: 0. size 2345 43 end 53 stalist=arrayllsize] of node; 663
North China Electric Power University 3.双亲表示法 用一个数组顺序地存放树的各个结点，结点存放的顺序是 任意的。每一结点有两个域组成：数据域和指针域，分别存储 树上结点中的数据元素和用于指示本结点之双亲所在的存储结 点。 指针域的类型定义有两种：高级语言中的指针类型和整型 或子界类型，与之对应的链表分别称为动态链表和静态链表。 静态双亲链表的定义： const size={结点数}; Type node=record data:ElemType; parent:0..size; end; stalist=array[1..size] of node; 1 2 3 4 5 6 ^ 1 2 3 4 5 6 1 3 2 4 5 6 data parent 0 1 1 3 3 3 结点序号
North China Electric Power University I ★二叉树 二叉树是一种重要的数据结构类型,它有许多良 好的性质和简单的物理表示,它的特点是最多有两个 孩子,并且二叉树的子树有左右之分,且其子树的顺 序不能任意颠倒。 二叉树的定义 二叉树是有m(n≥0)个结点的有限集合,此集合 或者是空的,或者是由一个根结点加上两棵分别称为 左右子树的、互不相交的二叉树组成。 注意:二叉树和树是两个不同的概念,树的子树不必区分其次 序,而二叉树的子树有左右之分,另外,二叉树也不能简单地 看成是一有序树,因为只有一棵子树时,无法区分其次序
North China Electric Power University ★二叉树 二叉树是一种重要的数据结构类型，它有许多良 好的性质和简单的物理表示，它的特点是最多有两个 孩子，并且二叉树的子树有左右之分，且其子树的顺 序不能任意颠倒。 二叉树的定义 二叉树是有n(n≥0)个结点的有限集合，此集合 或者是空的，或者是由一个根结点加上两棵分别称为 左右子树的、互不相交的二叉树组成。 注意：二叉树和树是两个不同的概念，树的子树不必区分其次 序，而二叉树的子树有左右之分，另外，二叉树也不能简单地 看成是一有序树，因为只有一棵子树时，无法区分其次序