数据结构

您所在的位置:网站首页 已知产品a的结构树如下图所示 数据结构

数据结构

2023-11-18 13:05| 来源: 网络整理| 查看: 265

练习1

1 . 设一棵二叉树的先序序列:ABDFCEGH,中序序列:BFDAGEHC. (1)画出这棵二叉树。 (2)画出这棵二叉树的后序线索树。 (3)将这棵二叉树转换成对应的树(或森林)

2 . 假设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为0.07、0.19、0.02、0.06、0.32、0.03、0.21和0.10。 (1)试为这8个字母设计哈夫曼编码。 (2)试设计另一种由二进制表示的等长编码方案。 (3)对于上述实例,比较两种方案的优缺点。

3 . 【408真题】如果一棵非空k(k≥2)叉树T中每个非叶子结点都有k个孩子,则称T为正则后k树。请回答下列问题并给出推导过程。 (1)若T有m个非叶子结点,则T中的叶子结点有多少个? (2)若T的高度为h(根的高度为1),则T的结点个数最多为多少个?最少为多少个?(提示,答案皆与K有关)

4 . 【算法题】以二叉链表为存储结构,交换二叉树每个结点的左孩子和有孩子。(编程实现后,只需将swapLR函数写在本子上)

//二叉树编程练习 typedef char ElemType; typedef struct BiTNode{ //数据域 ElemType data; //指向左孩子结点的指针 struct BiTNode *lchild; //指向左孩子结点的指针 struct BiTNode *rchild; }BiTNode, *BiTree; //创建一个二叉树 //按照先序遍历创建二叉树,空节点使用#表示,每个字符以空格隔开 //ABD##E##CF##G## 是一个层次遍历序列为ABCDEFE的满二叉树 int CreateBiTree(BiTree *T){ char ch; scanf("%c", &ch); //如果输入为空,则返回一颗空树 if(ch == '#'){ *T = NULL; } else { *T = (BiTNode *) malloc(sizeof(BiTNode)); if(!(*T)){ exit(OVERFLOW); } (*T)->data = ch; CreateBiTree(&((*T)->lchild)); CreateBiTree(&((*T)->rchild)); } return OK; } //交换二叉树每个结点的左右子树 void swapLR(BiTree *T){ //... } //打印二叉树 void printTree(BiTNode *root, int spaces) { int loop; while (root != NULL) { printTree(root->rchild, spaces + 4); for (loop = 1; loop BiTree root; CreateBiTree(&root); printf("root 结点的值为:%c\n", root->data); printf("root 结点左子树的值为:%c\n", root->lchild->data); printf("root 结点右子树的值为:%c\n", root->rchild->data); printTree(root, 0); //调用交换二叉树 swapLR(&root); printTree(root, 0); return 0; } 练习2

​ 在练习1,第四题给出的存储结构下,进行编程练习。

二叉树先序遍历的非递归算法。

提示:要写出二叉树的非递归算法,主要任务就是用自己定义的栈来代替系统栈的功能。以下图二叉树为例,各节点进栈、出栈过程如下图所示。

资源分配图 资源分配图

​ 初态:栈为空

​ ①结点1入栈。

​ ②出栈、输出结点1,并将结点1的左右孩子结点(2、4)入栈;右孩子先入栈,左孩子后入栈(栈的先进后出特性)。

​ ③出栈,输出栈顶结点2,将结点2的左右孩子结点入栈。

​ ④出栈,输出结点3,结点3为叶子结点,无结点入栈。

​ ⑤出栈,输出结点5,结点5为叶子结点,无结点入栈。

​ 出栈,出处栈顶结点4,此时栈空,进入终态。

​ 遍历序列为:1,2,3,5,4

​ 结合上面的提示,编写出先序遍历的非递归代码。

二叉树中序遍历的非递归算法。

​ 提示:参考上一题,各节点的进栈、出栈过程如下图所示,结合上一题,写出代码。

资源分配图 试设计出一个算法,求二叉树中值为x的结点的层次。(根节点的层次为1)

​ 提示:遍历的过程中,保存当前访问结点的层号,向下递归是层号++;访问解释左右子孩子时,回退到上一层时,层号–。

练习1参考答案: 1.答案:1、2、3的答案分别是下图中(a)、(b)、©所示。

资源分配图

2.答案: (1)可以将频率放大100倍(可选、可不选),不影响哈夫曼树的构造。 ​ w={7, 19, 2, 6, 32, 3, 21, 10},根据哈夫曼树的构造规则,构造的哈夫曼树如下所示(不一定唯一,做左右子树可以交换):

资源分配图

(2)哈夫曼编码和等长编码如下如所示(答案不唯一):

资源分配图

(3)对于上述两种方案,等长编码的构造显然比哈夫曼编码的构造简单。但是,哈夫曼编码是最优前缀编码。对于包括n个字符的数据文件,分别以它们的出现次数为权值构造哈夫曼树,则利用该树对应的哈夫曼编码对文件进行编码,能使该文件压缩后对应的二进制文件的长度最短。 哈夫曼编码对应二叉树的WPL为: WPL1=2x(0.19+0.32+0.21)+4x(0.07+0.06+0.10)+5x(0.02+0.03)=1.44+0.92+0.25=2.61 等长编码对应二叉树的WPL为: WPL2=3x(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3

3.答案: (1)根据定义,正则k叉树中仅含有两类结点:叶子结点(个数记为n0)和度为k的分支结点(个数记为n).树T中的结点总数n=n0+n=n0+m.树中所含的边数e=n-1,这些边均为m个度为k的结点发出的,即e=m * k.整理得:n0+m=m * k+1,故n0=(k-1)xm+1. (2)高度为h的正则k叉树T中,含最多结点的树形为:除第h层外,第1到第h-1层的结点都是度为k的分支结点,而第h层均为叶子结点,即树是“满”树。此时第j(1≤j≤h)层结点数为k-1,结点总数M1为: M 1 = ∑ j − 1 h k j − 1 = k h − 1 k − 1 M_1 =\sum_{j-1}^{h}{k^{j-1}} = \frac{k^h-1}{k-1} M1​=j−1∑h​kj−1=k−1kh−1​ ​ 含最少结点的正则k叉树的树形为:第1层只有根结点,第2到第h-1层仅含1个分支结点和k-1个叶子结点,第h层有k个结点。即除根外第2到第h层中每层的节点数均为k,故T中所含结点总数M2为: M 2 = 1 + ( h − 1 ) ∗ k M_2 =1 + (h-1)*k M2​=1+(h−1)∗k 4.答案:

void swapLR(BiTree *T){ if(T == NULL){ return; } //如果左右子树均为空,无须交换 if((*T)->lchild == NULL && (*T)->rchild == NULL){ return; } else { //交换左右子树 BiTNode *tmp = (*T)->lchild; (*T)->lchild = (*T)->rchild; (*T)->rchild = tmp; } swapLR(&(*T)->lchild); swapLR(&(*T)->rchild); } 资源分配图


【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3