页数:57页文件大小:339.1 KB来源: 程序设计基础与数据结构ppt课件
本课件系统讲解树型结构:先由实例给出树的定义与基本术语,介绍双亲表示法、孩子表示法与孩子兄弟表示法三种存储方式;随后重点展开二叉树的定义、五条基本性质、顺序与链式存储及基本操作实现;再系统讲解先根、中根、后根与层次四种遍历及线索二叉树,最后介绍树与二叉树的转换和赫夫曼树的构造与应用。
第六章 树,本章各小节:
6.1 树的基本概念:树 T 是一个有限的非空数据元素集合,该集合中的一个特定的数据元素被称为根,其余的数据元素被划分成为若干个互不相交的集合 T1、T2、…、Tm,其中的每个集合都是一棵树,它们也被称为根结点的子树。
图中示例为一棵包含 6 个结点 A、B、C、D、E、F 的树。
树中包含了 6 个结点,T = {A,B,C,D,E,F}。
树中的每个数据元素被表示成一个结点,结点与它的子树之间由分枝相连,一个结点不仅包括数据元素的值,还包括指向它的子树的分枝。
结点的层次从根开始计算:树中根结点的层次为 1,根的孩子结点的层次为 2,也就是说,结点的层次等于它的双亲结点的层次数加 1。
树中结点的最大层次称为树的深度或高度。
树的基本操作:
说明:原文序号出现两个「6」(求双亲与求孩子),此处已顺次重排为 1~10,操作内容未改动。
6.2 树的存贮表示,本节的几种表示法:
6.2 树的存贮表示(其他表示法):本节除双亲表示法、孩子表示法与孩子兄弟表示法之外,还可根据实际需要采用其他形式来表示树中的结点与分枝关系。
本页源文件仅保留标题文字,图例部分建议对照原课件图片查看。
6.2.1 双亲表示法:树中的每个结点都只有一个唯一的双亲结点,因此在结点中只设一个指向双亲的位置域即可。
#define NODE_NUM 100 typedef struct node_st { char data; int parent; } NODE; NODE tree[NODE_NUM]; | 下标 | data | parent |
|---|---|---|
| 0 | A | -1 |
| 1 | B | 0 |
| 2 | C | 0 |
| 3 | D | 0 |
| 4 | E | 1 |
| 5 | F | 1 |
说明:表格中的下标、data 与 parent 三列由原文「0A-11B02C03D04E15F1」按示例树的父子关系(A 为根,B、C、D 为 A 的孩子,E、F 为 B 的孩子)切分还原,建议对照原课件图片核对。
6.2.2 孩子表示法:树中的每个数据元素都用一个结点来表示,每个结点有多个指针域,指针域的个数依赖于树中该结点的孩子的个数。
结点形式为 data | child1 | child2 | … | childn;图中给出了示例树各结点(A~F)的孩子指针域及空指针的示意。
带 degree 的表示法:以树的度作为孩子指针数组的维数,结点中增设度域。
#define TREE_DEGREE ... typedef struct node_st { char data; struct node_st *child[TREE_DEGREE]; } NODE;此时的树就可定义为一个指向树的根结点的指针:NODE *tree;
结点形式为 data | degree | child1 | child2 | …。由于各个结点之间不同构,操作起来比较困难,所以也不常用。
孩子链表表示法:为每个结点建立一条孩子链表,树结点中只保存指向孩子链表表头的指针。
typedef struct childnode_st { int id; struct childnode_st *next; } CHILDNODE; typedef struct node_st { char data; CHILDNODE *firstchild; } NODE; NODE tree[NODE_NUM]; 图中给出了示例树各结点(下标 0~5,data 为 A~F)的孩子链表连接关系。
带双亲的孩子链表表示法:在孩子链表表示法的树结点中再增加一个双亲位置域。
typedef struct childnode_st { int id; struct childnode_st *next; } CHILDNODE; typedef struct node_st { char data; int parent; CHILDNODE *firstchild; } NODE; NODE tree[NODE_NUM]; 图中同时给出了 parent、下标、data 与 firstchild 四部分的对应关系。
6.2.3 孩子兄弟表示法:树的结点除了结点信息外,还包括两个指针域,分别指向该结点的第一个孩子结点和下一个兄弟结点。
因为树中的每个结点中有两个指针域,所以又称为二叉链表表示法。
孩子兄弟表示法的存储结构定义:
typedef struct node_st { char data; struct node_st *child, *brother; } NODE; NODE *tree; 图中给出了示例树按孩子兄弟表示法连接后的二叉链表形态。
6.3 二叉树,本节内容包括:
6.3.1 二叉树的定义:二叉树是一个数据元素的有限集(可为空)。当二叉树不空时,它有一个特定的根结点,其余的结点被划分成为两棵互不相交的二叉树,即它的左子树和右子树。
二叉树的五种基本形态:
说明:原文该页仅有标题,五种形态以课件图片为准,此处按标题作文字整理。
二叉树的基本操作:
说明:原文序号中「求双亲」与「求左孩子」均标为 6,此处已顺次重排,操作内容未改动。
用二叉树表示算术表达式:表达式 a + b * c - d / e 对应的二叉树中,根结点为运算符「-」,其左子树为「+」与「*」构成的 a + b * c,右子树为「/」构成的 d / e。
分支结点存放运算符,叶子结点(a、b、c、d、e)存放操作数,运算次序由结点的层次决定。
6.3.2 二叉树的性质:
性质 4:假设具有 n 个结点的二叉树的高度为 h,则 n ≥ h ≥ ⌈log2(n+1)⌉。
图中给出高度为 3 的满二叉树(结点按层次编号 1~7)与完全二叉树的结点编号示例,用以说明两种形态在最后一层结点排列上的区别。
说明:原文该页主要为图示,编号序列字符粘连,具体编号以课件图片为准。
性质 5:假设具有 n 个结点的完全二叉树按层次从上到下、从左至右进行编号,则对编号为 i 的结点有:
该性质的 1 与 2、3 实际上完全等价,故只需知道 2 和 3 就可以得到 1;2、3 可用数学归纳法证明。
6.3.3 二叉树的存贮表示,两种存储结构:
6.3.3.1 二叉树的顺序存储结构:按完全二叉树的编号次序,用一组连续的存储单元(一维数组)依次存放二叉树中的结点。
图中给出高度为 3 的右单枝树及其存储示意:结点 A、B、C 只占用了与各自编号对应的数组单元,其余大量单元被空置,可见顺序存储对右单枝树这类形态会造成较大的空间浪费。
6.3.3.2 二叉树的链式存储结构——二叉链表表示:
typedef struct node_st { char data; struct node_st *left, *right; } NODE; NODE *tree; 结点由 left | data | right 三个域构成,图中给出了示例二叉树的二叉链表连接示意。
三叉链表表示:在二叉链表的基础上再增加一个指向双亲结点的指针域。
typedef struct node_st { char data; struct node_st *left, *right; struct node_st *parent; } NODE;结点由 left | data | right | parent 四个域构成,图中给出了示例二叉树的三叉链表连接示意。
6.4 二叉树的遍历:按一定的次序,对二叉树中的每个结点访问且仅访问一次。
通过遍历,就使二叉树这种本来非线性的结构映射为一种线性的排列。本节包括:
6.4.1 遍历的递归过程,四种遍历方式:
先根序遍历(DLR)的步骤:
int visit(NODE *node); int PreOrderTraverse(NODE *tree) { if (tree != NULL) { visit(tree); PreOrderTraverse(tree->left); PreOrderTraverse(tree->right); } }; 说明:原文该页页眉标注为「LDR(中根序)」,但所列步骤与函数名 PreOrderTraverse 均为先根序(DLR),此处按步骤与代码内容整理,建议对照原课件图片核对。
中根序遍历(LDR)的步骤:
int visit(NODE *node); int InOrderTraverse(NODE *tree) { if (tree != NULL) { InOrderTraverse(tree->left); visit(tree); InOrderTraverse(tree->right); } }; 说明:原文该页页眉标注为「DLR(先根序)」,但所列步骤与函数名 InOrderTraverse 均为中根序(LDR),此处按步骤与代码内容整理,建议对照原课件图片核对。
后根序遍历(LRD)的步骤:
int visit(NODE *node); int PostOrderTraverse(NODE *tree) { if (tree != NULL) { PostOrderTraverse(tree->left); PostOrderTraverse(tree->right); visit(tree); } }; 层序遍历:从根结点开始,按层次从上到下、同一层中从左到右的顺序依次访问二叉树中的每个结点,通常借助队列实现。
说明:原文该页仅保留标题,遍历过程的示例图示建议对照原课件图片查看。
6.4.2 遍历的非递归过程:虽然二叉树遍历的递归算法比较简单,但是其在实现时由于要进行反复的递归调用,会占用较多的存储空间,花费较多的运行时间,效率较低。
在实际应用时,常常需要将递归算法用非递归的方式实现,即利用栈,将递归过程转化为非递归过程:
先序非递归遍历:为进行非递归的访问,需要增加一个辅助的栈,用这个栈来实现原来的递归过程。
NODE (*stack)[NODE_NUM]; void PreOrderTraverse(NODE *tree) { if (tree == NULL) return FALSE; PushStack(&stack, tree); while (!EmptyStack(&stack)) { nextp = PopStack(&stack); visit(nextp); if (nextp->right != NULL) PushStack(&stack, nextp->right); if (nextp->left != NULL) PushStack(&stack, nextp->left); } return SUCCESS; }; 本页以表达式树 a + b * c - d / e 为例,逐步给出操作、栈的状态与输出结果三者的对应关系:根结点「-」先入栈,出栈后其右孩子「/」与左孩子「+」依次入栈,如此反复,最终得到先序序列 -+a*bc/de。
说明:原文该页为逐行的操作与栈状态、输出结果对照,字符粘连较严重,未还原为数据表格,建议对照原课件图片核对具体步骤。
中序非递归遍历:栈元素中除结点指针外,还需记录该结点的进栈次数。
typedef struct stack_st { NODE *node; int isfirst; } STACK; STACK stack[NODE_NUM]; int PushStack(STACK s[NODE_NUM], NODE *p, int id); int PopStack(STACK s[NODE_NUM], STACK &sp); void InOrderTraverse(NODE *tree) { if (tree == NULL) return FALSE; PushStack(&stack, tree, TRUE); while (!EmptyStack(&stack)) { PopStack(&stack, &next); if (next.isfirst == TRUE) { if (next.node->right != NULL) PushStack(&stack, next.node->right, TRUE); PushStack(&stack, next.node, FALSE); if (next.node->left != NULL) PushStack(&stack, next.node->left, TRUE); } else visit(next.node); } return SUCCESS; }; 本页以表达式树 a + b * c - d / e 为例,逐步给出操作、栈的状态与输出结果的对应关系:结点第一次出栈时按先右、再根、后左的次序重新进栈,第二次出栈时才访问,最终得到中序序列 a+b*c-d/e。
说明:原文该页为逐行的操作与栈状态、输出结果对照,字符粘连较严重,未还原为数据表格,建议对照原课件图片核对具体步骤。
后序非递归遍历:同样借助记录进栈次数的栈,但进栈次序改为先根、再右、后左,使访问次序为先左、再右、最后根。
void PostOrderTraverse(NODE *tree) { if (tree == NULL) return FALSE; PushStack(&stack, tree, TRUE); while (!EmptyStack(&stack)) { PopStack(&stack, &next); if (next.isfirst == TRUE) { PushStack(&stack, next.node, FALSE); if (next.node->right != NULL) PushStack(&stack, next.node->right, TRUE); if (next.node->left != NULL) PushStack(&stack, next.node->left, TRUE); } else visit(next.node); } return SUCCESS; }; 本页以表达式树 a + b * c - d / e 为例,逐步给出操作、栈的状态与输出结果的对应关系:结点第一次出栈时按先根、再右、后左的次序重新进栈,第二次出栈时才访问,最终得到后序序列 abc*+de/-。
说明:原文该页为逐行的操作与栈状态、输出结果对照,字符粘连较严重,未还原为数据表格,建议对照原课件图片核对具体步骤。
6.4.3 遍历的性质:
6.5 线索二叉树:通过遍历使二叉树中的结点从一种非线性的序列排列成了线性序列。
通过每个结点的左右孩子指针能够方便地找到结点的左右孩子,却很难找到其前驱和后继。若每个结点再增加两个指针域分别指向前驱与后继,则每个结点将有一个信息域和四个指针域,太浪费存储空间。
在二叉树的二叉链表存储结构中,如果树中的结点个数为 n,那么必有 2n 个指针域,但其中只有 n-1 个有效指针,其余的 n+1 个指针域必为空。一种比较巧妙的方法是利用这 n+1 个空指针域来存放结点的前驱和后继信息;为与指向左右孩子的指针相区别,必须引入标志信息。本节包括:
6.5.1 线索二叉树的定义:以结点的左孩子指针指示其左孩子或前驱(设置标志位 lid 来区分),以结点的右孩子指针指示其右孩子或后继(设置标志位 rid 来区分),则结点的结构演变为:
结点形式:lid | left | data | right | rid。
其中指向结点前驱和后继的指针,叫做线索;加上线索的二叉树称为线索二叉树。
6.5.2 线索二叉树的遍历:图中以表达式 a + b * c - d / e 对应的二叉树为例,分别给出先序线索树、中序线索树与后序线索树的线索连接示意。
6.6 树与二叉树的转换,本节包括:
6.6.1 树与二叉树的转换,对应规则为:
图中给出示例树(结点 A~F)的孩子兄弟链表表示与其对应的二叉树形态:按「第一个孩子作左孩子、第一个兄弟作右孩子」的规则,树中 A 的孩子 B、C、D 在二叉树中沿左、右链依次连接,B 的孩子 E、F 则成为 B 的左子树。
说明:原文该页主要为图示与粘连的字符序列,具体连接关系以课件图片为准。
6.6.2 森林与二叉树的转换:森林转化为二叉树的方法为:
图中给出了由若干棵树组成的森林转换为一棵二叉树的示例。
二叉树转化为森林的方法为:
通过树、森林与二叉树之间的转换,就可以借助二叉树的运算来实现树与森林的运算。
6.6.3 树与森林的遍历:树的遍历有两种形式。
说明:原文后(根)序遍历的三个步骤中写作「中序遍历」,与标题「后(根)序遍历」不一致,此处按标题与遍历含义整理,建议对照原课件图片核对。
6.7 赫夫曼树:赫夫曼树是一棵最优二叉树,其带权路径长度最短。本节包括:
6.7.1 最优二叉树:
6.7.2 前缀编码:进行不等长编码时,必须保证任何一个字符的编码都不能是其它字符编码的前缀,这样的编码称为前缀编码。
采用前缀编码可以保证译码时不会出现二义性,是设计不等长编码的基本约束。
6.7.3 赫夫曼编码:为了提高编码的效率,可以利用赫夫曼算法进行前缀编码。
把每个字符的出现频率记为 wi,设其编码长度为 li,则编码总长为 ∑wklk(k = 1…n)。如果设二叉树中的 n 片叶子结点的权值为 w1, w2, …, wn,且从根到叶子结点的路径长度为 li,那么 ∑wklk(k = 1…n)就为树的带权路径长度。
这样,要使前缀编码的总长度最短的问题,就转化成了设计一棵最优二叉树的问题。
6.8 小结:
下载地址:{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}