第9周树和二叉树（下）第6讲-本周小结.pdf

《第9周树和二叉树（下）第6讲-本周小结.pdf》由会员分享，可在线阅读，更多相关《第9周树和二叉树（下）第6讲-本周小结.pdf（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1二叉树遍历 1/23 某种次序某种次序 访问所有节点访问所有节点 不重复访问不重复访问 先序遍历先序遍历 中序遍历中序遍历 后序遍历后序遍历 层次遍历层次遍历 具有递归性具有递归性 二叉树算法二叉树算法 二叉树查找二叉树查找 二叉树遍历二叉树遍历 2/23 基于递归遍历基于递归遍历 采用递归数据结构的递归算法设计方法采用递归数据结构的递归算法设计方法 N LR b f(b)：大问题：大问题 f(L)：小问题：小问题f(R)：小问题：小问题 3部分组成，两种类型：节点，子树部分组成，两种类型：节点，子树 先节点，再子树先节点，再子树 先序先序 先子树，再节点先子树，再节点 后序后序 3/23

2、假设二叉树采用二叉链存储结构，设计一个算假设二叉树采用二叉链存储结构，设计一个算 法求二叉树法求二叉树b中度为中度为2的节点个数。的节点个数。 N LR b f(b)：度为：度为2的节点数的节点数 f(b-lchild)： L中度为中度为2的的 节点数节点数 f(b-rchild)： R中度为中度为2的的 节点数节点数 f(b)=0当当b=NULL f(b)=1+f(b-lchild)+f(b-rchild) 当当b节点度为节点度为2 f(b)=f(b-lchild)+f(b-rchild) 其他情况其他情况 4/23 int dnodes(BTNode *b) if (b=NULL) ret

3、urn 0; if (b-lchild!=NULL else return dnodes(b-lchild)+dnodes(b-rchild); 算法如下：算法如下： 5/23 假设二叉树采用二叉链存储结构，设计一个算假设二叉树采用二叉链存储结构，设计一个算 法求二叉树法求二叉树b中第中第k层的节点个数。层的节点个数。 设计算法为设计算法为knumber(b，h，k， else/处理非空树处理非空树 if (h=k) n+;/当前访问的节点在第当前访问的节点在第k层时，层时，n增增1 else if (hlchild，h+1，k，n); knumber(b-rchild，h+1，k，n); 基

4、于先序遍历的思路 7/23 假设二叉树采用二叉链存储结构，设计一个假设二叉树采用二叉链存储结构，设计一个 算法求二叉树算法求二叉树b的宽度（的宽度（采用递归方法采用递归方法）。）。 levelnumber(BTNode *b，int h，int a)：求二叉树：求二叉树b中所中所 有层的节点个数，存放在有层的节点个数，存放在a数组中，数组中，ah表示第表示第h层节点个数层节点个数 f(b，h，a) 不做任何事情不做任何事情当当b=NULL f(b，h，a) ah+; 其他情况其他情况 f(b-lchild，h+1，a) f(b-rchild，h+1，a) 8/23 void levelnumb

5、er(BTNode *b，int h，int a) if (b=NULL) return; else ah+; levelnumber(b-lchild，h+1，a); levelnumber(b-lchild，h+1，a); 9/23 int BTWidth1(BTNode *b) int width=0，i; int aMaxSize; for (i=1;iwidth) width=ai; i+; return width; 10/23 B A C D 每个节点有唯一的双亲节点每个节点有唯一的双亲节点 节点的层次节点的层次 = 双亲节点的层次双亲节点的层次+1 11/23 假设二叉树采用二

6、叉链存储结构，设计一个算假设二叉树采用二叉链存储结构，设计一个算 法求二叉树法求二叉树b的宽度（的宽度（采用层次遍历方法采用层次遍历方法）。）。 int BTWidth2(BTNode *b) struct int lno;/节点的层次节点的层次 BTNode *p;/节点指针节点指针 QuMaxSize;/定义非环形队列定义非环形队列 int front，rear;/定义队头和队尾指针定义队头和队尾指针 int lnum，width，i，n; front=rear=0;/置队列为空队置队列为空队 12/23 if (b!=NULL) rear+; Qurear.p=b;/根节点进队根节点进队

7、 Qurear.lno=1;/根节点的层次为根节点的层次为1 while (rear!=front)/队不空时循环队不空时循环 front+; b=Qufront.p;/出队节点出队节点p lnum=Qufront.lno; if (b-lchild!=NULL)/有左孩子，将其进队有左孩子，将其进队 rear+; Qurear.p=b-lchild; Qurear.lno=lnum+1; if (b-rchild!=NULL)/有右孩子，将其进队有右孩子，将其进队 rear+; Qurear.p=b-rchild; Qurear.lno=lnum+1; 13/23 width=0; lnum

8、=1; i=1;/width存放宽度存放宽度 while (i=rear) n=0; while (iwidth) width=n; return width; else return 0; 14/23 2二叉树的构造 由中序序列和先序序列由中序序列和先序序列可以唯一构造可以唯一构造一棵二叉树一棵二叉树 由中序序列和后序序列由中序序列和后序序列可以唯一构造可以唯一构造一棵二叉树一棵二叉树 由中序序列和层次序列由中序序列和层次序列可以唯一构造可以唯一构造一棵二叉树一棵二叉树 15/23 由一个固定的先序序列（含由一个固定的先序序列（含n个不同的节点），个不同的节点）， 构造的二叉树个数构造的二叉

9、树个数？ 当当n=3，结果为，结果为5。 A B C A B C A BC A B C A B C 第第n个个Catalan数数 16/23 若某非空二叉树的先序序列和中序序列正好相反，若某非空二叉树的先序序列和中序序列正好相反， 则该二叉树的形态是什么？则该二叉树的形态是什么？ 先序序列先序序列 N L R 中序序列的反序中序序列的反序 R N L R为空为空 所有节点没有右 子树的单支树 17/23 3线索二叉树 二叉链二叉链 + 空指针改为线索空指针改为线索 线索二叉树 左、右空指针指向前驱、后继节点左、右空指针指向前驱、后继节点 前驱、后继节点与遍历方式有关前驱、后继节点与遍历方式有关

10、 先序线索二叉树 中序线索二叉树 后序线索二叉树 18/23 以中序线索二叉树说明：以中序线索二叉树说明： 对二叉树中序遍历，递归算法：时间复杂度均为对二叉树中序遍历，递归算法：时间复杂度均为O(n)，空间复，空间复 杂度均为杂度均为O(h) 对二叉树中序遍历，非递归算法：时间复杂度均为对二叉树中序遍历，非递归算法：时间复杂度均为O(n)，空间，空间 复杂度均为复杂度均为O(h) 对中序线索二叉树中序遍历，时间复杂度均为对中序线索二叉树中序遍历，时间复杂度均为O(n)，空间复杂，空间复杂 度均为度均为O(1) 19/23 根节点的最左下节点根节点的最左下节点 根节点的最右下节点根节点的最右下节

11、点 20/23 4哈夫曼树 n0个叶子节点，含有权值个叶子节点，含有权值 构造哈夫曼树：权值越小距离根节点越远构造哈夫曼树：权值越小距离根节点越远 构造哈夫曼编码：权值越小编码越长构造哈夫曼编码：权值越小编码越长 21/23 哈夫曼树中：哈夫曼树中： 哈夫曼树满足二叉树的性质哈夫曼树满足二叉树的性质 n1=0 没有两个字符的编码相同没有两个字符的编码相同 没有两个字符编码的前缀相同没有两个字符编码的前缀相同 22/23 如果一棵哈夫曼树如果一棵哈夫曼树T中共有中共有255个节点，那么个节点，那么 该树用于对几个字符进行哈夫曼编码？该树用于对几个字符进行哈夫曼编码？ n=255，n1=0 n0=n2+1，总节点数，总节点数n = n0+n2 = 2n0-1 n0 = (n+1)/2 = 128 所以该树用于对所以该树用于对128个字符进行哈夫曼编码。个字符进行哈夫曼编码。 23/23