数据结构作业12查缺补漏

2024-02-26 04:58
文章标签 数据结构 作业 补漏 查缺

本文主要是介绍数据结构作业12查缺补漏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、判断题

在这里插入图片描述
后序：左右根
中序：左根右

在这里插入图片描述
在这里插入图片描述

二、选择题

在这里插入图片描述

记住两点：
先序，后序遍历可以确定根节点。
中序遍历可以确定左子树和右子树。
做这种题就是，反复来回这两点
再来一题
在这里插入图片描述
还有这种题型
在这里插入图片描述

在这里插入图片描述
中序：左根右
后序取反：根右左

2-11
任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序(2分)
A.发生改变
B.不发生改变
C.不能确定
D.以上都不对

在这里插入图片描述

先序遍历顺序是：M-L-R，后序遍历顺序是：L-R-M，可以看到，只有中间的结点（M）顺序变化了，左右结点相对位置是不变的；
那可以推断出，要满足题意的话“二叉树的先序序列与后序序列正好相反”，说明整个二叉树左子树或者右子树有一个没有（遍历就成了，先：M-L·；后：L-M 或者 先：M-R ；后：R-M ）也就是必然是一条链。因此该二叉树的高度一定等于其节点数。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

树的度：树中所有结点的度的最大值。
二叉树：是由n(n>=0)个结点构成的、每个结点最多只有两个子树的有序树。
满二叉树：所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上。
在这里插入图片描述

完全二叉树：逻辑结构与满二叉树的前n个结点的逻辑结构相同。
1.只有一个结点，树的度为0.
2.不确定，（1）一个结点的二叉树度为0，（2）两个结点的二叉树度为1，（3）三个结点的二叉树可以为1或者2
3.二叉树是有序树，左右子树不可交换
4.正确
在这里插入图片描述
前6层总结点数为2^6-1=63，第7层结点数为24x2=48
因为是完全二叉树，第6层出现叶结点，所以该树最大有7层
总结点数63+48=111

三、编程题

6-1 统计二叉树度为2的结点个数 (10分)

本题要求实现一个函数，可统计二叉树中度为2的结点个数。

函数接口定义：

int NodeCount ( BiTree T);

T是二叉树树根指针，函数NodeCount返回二叉树中度为2的结点个数，若树为空，返回0。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>typedef char ElemType;
typedef struct BiTNode
{ElemType data;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;BiTree Create();/* 细节在此不表 */int NodeCount ( BiTree T);int main()
{BiTree T = Create();printf("%d\n", NodeCount(T));return 0;
}
/* 你的代码将被嵌在这里 */

输出样例（对于图中给出的树）：
在这里插入图片描述

2

//思路：递归边界：树为空时，返回0；递归关系：先递归左子树，再递归右子树，每次遇到度为2的结点，count+1；
//注意：特殊情况为根结点只有左子树或右子树
int NodeCount ( BiTree T)
{int n=0;if(!T){n=0;}else {if(T->lchild&&T->rchild)//左右子树存在（根节点度为2）{n++;n+=NodeCount(T->lchild);n+=NodeCount(T->rchild);}else//只有左子树或只有右子树（根节点度为0或1）{n+=NodeCount(T->lchild);n+=NodeCount(T->rchild);}}return n;
}

大佬代码

6-2 后序输出第i个结点 (6分)

本题要求实现对于给定的二叉树，打印后序序列中指定序号的结点。

函数接口定义：

void PrintNode(BiTree T);

T是二叉树树根指针，PrintNode函数输出给定二叉树的后序序列中第n个结点，n为结点在后序序列中的序号，从1开始编号。

其中BinTree结构定义如下：

typedef char ElemType;
typedef struct BiTNode
{ElemType data;struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>typedef char ElemType;
typedef struct BiTNode
{ElemType data;struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;BiTree Create();/* 细节在此不表 */
void PrintNode(BiTree T);
int n;//要打印的结点的在先序序列中的序号
int main()
{BiTree T = Create();scanf("%d", &n);printf("The %d-th node in postorder is: ", n);PrintNode(T);printf("\n");return 0;
}
/* 你的代码将被嵌在这里 */

输出样例（对于图中给出的树，当输入的n为2时）：
在这里插入图片描述

The 2-th node in postorder is: G

//思路://递归关系:遍历大规模二叉树归结为遍历左子树、右子树、根。左右子树的遍历需要递归，递归的次数即后序输出中结点的次序
//递归边界:空树直接返回
//注意：定义变量k来记录递归次数，每递归一次，k++
int k=0;
void PrintNode(BiTree T)
{if(!T) return;if(T){ if(T->lchild){PrintNode(T->lchild);}if(T->rchild){PrintNode(T->rchild);}//printf("%d",T->data);if(++k==n){printf("%c",T->data);return;}} 
}

7-1 根据后序和中序遍历输出先序遍历 (25分)

本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。

输入格式:
第一行给出正整数N(≤30)，是树中结点的个数。随后两行，每行给出N个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。

输出格式:
在一行中输出Preorder: 以及该树的先序遍历结果。数字间有1个空格，行末不得有多余空格。

输入样例:

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例:

Preorder: 4 1 3 2 6 5 7

//思路：采用递归的思想，从中序数组找根节点，中序数组中这个根节点左边的就是左子树，右边就是右子树，递归左右两部分然后就可得所有节点
//注意：递归边界：空树，递归过程中要求出子树的长度来确定根节点 
//头文件包含
#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>//函数状态码定义
#define TRUE       1
#define FALSE      0
#define OK         1
#define ERROR      0
#define OVERFLOW   -1
#define INFEASIBLE -2typedef int Status;//二叉链表存储结构定义
typedef int TElemType;
typedef struct BiTNode{TElemType data;struct BiTNode  *lchild, *rchild; 
} BiTNode, *BiTree;//创建二叉树各结点，输入0代表创建空树。
//采用递归的思想创建
//递归边界：空树如何创建呢：直接输入0；
//递归关系：非空树的创建问题，可以归结为先创建根节点，输入其数据域值；再创建左子树；最后创建右子树。左右子树递归即可完成创建！
Status CreateBiTree(BiTree &T){TElemType e;scanf("%d",&e);if(e==0)T=NULL;else{T=(BiTree)malloc(sizeof(BiTNode));if(!T)exit(OVERFLOW);T->data=e;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}return OK;  
}BiTree createTree(int *InorderTree, int *PostOrderTree, int len)
{if (len <= 0) return NULL;else{BiTree T = (BiTNode*)malloc(sizeof(BiTNode));T->data = PostOrderTree[len-1];//根据后序遍历确定根节点int i;for (i = 0; i < len; i++){if (InorderTree[i] == PostOrderTree[len-1])//在中序遍历中找到根节点break;}T->lchild = createTree(InorderTree, PostOrderTree, i);//构建左子树T->rchild = createTree(InorderTree + i + 1, PostOrderTree + i, len - i - 1);//构建右子树return T;}
}void print_preorderTree(BiTree T)
{if (!T) return ;else{printf(" %d", T->data);//先序输出print_preorderTree(T->lchild);print_preorderTree(T->rchild);}
}int main()
{int n;int InorderTree[110], PostOrderTree[110];BiTree T;scanf("%d", &n);for(int i=0; i<n; i++){scanf("%d", &PostOrderTree[i]); //后序遍历}for(int i=0; i<n; i++){scanf("%d", &InorderTree[i]); //中序遍历}T = createTree(InorderTree, PostOrderTree, n);printf("Preorder:");print_preorderTree(T);return 0;
}

这篇关于数据结构作业12查缺补漏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/747764。

相关文章

作业提交过程之HDFSMapReduce

作业提交过程之HDFSMapReduce

作业提交全过程详解 （1）作业提交 第1步：Client调用job.waitForCompletion方法，向整个集群提交MapReduce作业。 第2步：Client向RM申请一个作业id。 第3步：RM给Client返回该job资源的提交路径和作业id。 第4步：Client提交jar包、切片信息和配置文件到指定的资源提交路径。 第5步：Client提交完资源后，向RM申请运行MrAp
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...
浙大数据结构：04-树7 二叉搜索树的操作集

浙大数据结构：04-树7 二叉搜索树的操作集

这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
阅读更多...
【数据结构入门】排序算法之交换排序与归并排序

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客，我们学习了排序算法中的插入排序和选择排序，接下来我们将继续探索交换排序与归并排序，这两个排序都是重头戏，让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换，让较大的元素逐渐向右移动，从而将最大的元素移动到最右边。 动画演示： 1.1.2 具体步
阅读更多...
数据结构：线性表的顺序存储

数据结构：线性表的顺序存储

文章目录 🍊自我介绍🍊线性表的顺序存储介绍概述例子 🍊顺序表的存储类型设计设计思路类型设计 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2