C/C++教程
SCAU程序设计在线实训平台_实验_数据结构_实验4
本文主要是介绍SCAU程序设计在线实训平台_实验_数据结构_实验4，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
8606 二叉树的构建及遍历操作【有手就行】
Description
构造二叉链表表示的二叉树：按先序次序输入二叉树中结点的值（一个字符），’#'字符表示空树，构造二叉链表表示的二叉树T；再输出三种遍历序列。本题只给出部分代码,请补全内容。
#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef char ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;//左右孩子指针
} BiTNode,*BiTree;
Status CreateBiTree(BiTree &T) { // 算法6.4
// 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树，
// 构造二叉链表表示的二叉树T。
char ch;
scanf("%c",&ch);
if (ch=='#') T = NULL;
else {
if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
________________________ // 生成根结点
_______________________ // 构造左子树
_________________________ // 构造右子树
}
return OK;
} // CreateBiTree
Status PreOrderTraverse( BiTree T) {
// 前序遍历二叉树T的递归算法
//补全代码,可用多个语句
} // PreOrderTraverse
Status InOrderTraverse( BiTree T) {
// 中序遍历二叉树T的递归算法
//补全代码,可用多个语句
} // InOrderTraverse
Status PostOrderTraverse( BiTree T) {
// 后序遍历二叉树T的递归算法
//补全代码,可用多个语句
} // PostOrderTraverse
int main() //主函数
{
//补充代码
}//main
输入格式
第一行：输入一棵二叉树的先序遍历序列
输出格式
第一行：二叉树的先序遍历序列
第二行：二叉树的中序遍历序列
第三行：二叉树的后序遍历序列
输入样例
AB##C##
输出样例
ABC
BAC
BCA
代码实现
#include "stdio.h"
#include "malloc.h"
#include <iostream>
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef char ElemType;
typedef struct BiTNode {
ElemType data;
struct BiTNode *lchild, *rchild;//左右孩子指针
} BiTNode, *BiTree;
Status CreateBiTree(BiTree &T) { // 算法6.4
// 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树，
// 构造二叉链表表示的二叉树T。
char ch;
scanf("%c", &ch);
if (ch == '#') T = NULL;
else {
if (!(T = (BiTNode *) malloc(sizeof(BiTNode)))) return ERROR;
T->data = ch; // 生成根结点
CreateBiTree(T->lchild); // 构造左子树
CreateBiTree(T->rchild); // 构造右子树
}
return OK;
} // CreateBiTree
Status PreOrderTraverse(BiTree T) {
// 前序遍历二叉树T的递归算法
//补全代码,可用多个语句
if (T == NULL)return ERROR;
cout << T->data;
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
} // PreOrderTraverse
Status InOrderTraverse(BiTree T) {
// 中序遍历二叉树T的递归算法
//补全代码,可用多个语句
if (!T)return ERROR;
InOrderTraverse(T->lchild);
cout << T->data;
InOrderTraverse(T->rchild);
} // InOrderTraverse
Status PostOrderTraverse(BiTree T) {
// 后序遍历二叉树T的递归算法
//补全代码,可用多个语句
if (!T)return ERROR;
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout << T->data;
} // PostOrderTraverse
int main() //主函数
{
//补充代码
BiTree P;
CreateBiTree(P);
PreOrderTraverse(P);cout<<endl;
InOrderTraverse(P);cout<<endl;
PostOrderTraverse(P);cout<<endl;
}//main
17121 求二叉树各种节点数【背关系】
Description
构造二叉链表表示的二叉树：按先序次序输入二叉树中结点的值（一个字符），’#'字符表示空树，构造二叉链表表示的二叉树T,并求此二叉树中度为2的节点总数，度为1的节点总数，度为0的节点总数
#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef char ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;//左右孩子指针
} BiTNode,*BiTree;
Status CreateBiTree(BiTree &T) { // 算法6.4
// 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树，
// 构造二叉链表表示的二叉树T。
char ch;
scanf("%c",&ch);
if (ch=='#') T = NULL;
else {
if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
________________________ // 生成根结点
_______________________ // 构造左子树
_________________________ // 构造右子树
}
return OK;
} // CreateBiTree
int main() //主函数
{
//补充代码
}//main
输入格式
第一行输入先序次序二叉树中结点
输出格式
第一行输出度为2的节点数
第二行输出度为1的节点数
第三行输出度为0的节点数
输入样例
ABC###D##
输出样例
1
1
2
代码实现
#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef char ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;//左右孩子指针
} BiTNode,*BiTree;
int n0=0,n=0;
Status CreateBiTree(BiTree &T) { // 算法6.4
// 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树，
// 构造二叉链表表示的二叉树T。
char ch;
scanf("%c",&ch);
if (ch=='#') T = NULL;
else {
if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
T->data=ch; // 生成根结点
n++;
CreateBiTree(T->lchild);// 构造左子树
CreateBiTree(T->rchild); // 构造右子树
}
return OK;
} // CreateBiTree
void f(BiTree &T){
if(!T)return;
if(!T->lchild&&!T->rchild)n0++;
f(T->lchild);
f(T->rchild);
}
int main() //主函数
{
//补充代码
BiTree T;
CreateBiTree(T);
f(T);
printf("%d\n%d\n%d\n",n0-1,n-2*n0+1,n0);
//n0为叶子节点数
//叶子节点数=度2节点数+1
//所有节点树-叶子节点树-度2节点数=度1节点数
}//main
18924 二叉树的宽度【可偷懒】
Description
二叉树的宽度指的是具有节点数目最多的那一层的节点个数。
1
/
2 3
/
4
答案为2, 第二层节点数最多，为2个节点。
输入格式
共n行。
第一行一个整数n，表示有n个结点，编号为1至n,结点1为树根。（1<=n<=50）
第二行至第n行，每行有两个整数x和y，表示在二叉树中x为y的父节点。x第一次出现时y为左孩子
输出格式
输出二叉树的宽度。
输入样例
5
1 2
1 3
2 4
2 5
输出样例
2
代码实现【二维数组偷懒法】
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<vector<int>> array(50);
array[0].push_back(1);
int n;
cin >> n;
for(int i=0;i<n-1;i++){
int x,y;
cin>>x>>y;
for(int j=0;j<50;j++){
if(array[j].back()>=x){
array[j+1].push_back(y);
break;
}
}
}
int max=0;
for(int i=0;i<50;i++){
if(max<array[i].size())max=array[i].size();
}
cout << max<<endl;
return 0;
}
18724 二叉树的遍历运算【值得一看★】
Description
二叉树的三种遍历都可以通过递归实现。
如果我们知道一棵二叉树的先序和中序序列，可以用递归的方法求后序遍历序列。
输入格式
两行，第一行一个字符串，表示树的先序遍历，第二行一个字符串，表示树的中序遍历。树的结点一律用小写字母表示。
输出格式
一个字符串，树的后序序列。
输入样例
abcde
bcade
输出样例
cbeda
代码实现
#include <iostream>
#include <cstring>
using namespace std;
char pre[1000],mid[1000],res[1000];
void cut(char pre[],char mid[],int len,int loc){
if(len<=0)return;
int i=0;
while(pre[0]!=mid[i])i++;//找到中序中的根节点
cut(pre+1,mid,i,loc-(len-i-1)-1);//loc - 右子树长度 - 1 = 左子树根节点该在的位置，也就是根节点左边的字符
cut(pre+i+1,mid+i+1,len-i-1, loc - 1);//loc - 1 = 右子树根节点该在的位置，也就是
res[loc]=pre[0];//loc 为 根节点在后序序列中该在位置
}
int main() {
cin>>pre>>mid;
int len=strlen(mid);
cut(pre,mid,len,len-1);
cout<<res<<endl;
return 0;
}
18923 二叉树的直径【值得一看★】
Description
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
1
/
2 3
/ \
4 5
答案为3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
输入格式
共n行。
第一行一个整数n，表示有n个结点，编号为1至n。
第二行至第n行，每行有两个整数x和y，表示在二叉树中x为y的父节点。x第一次出现时y为左孩子
输出格式
输出二叉树的直径。
输入样例
5
1 2
1 3
2 4
2 5
输出样例
3
代码实现
#include "stdio.h"
#include "malloc.h"
#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct BiTNode {
ElemType data;
struct BiTNode *lchild, *rchild;//左右孩子指针
} BiTNode, *BiTree;
//插入数据到指定树下
void insertData(BiTree &T, ElemType data) {
BiTree P = new BiTNode;//P是一个新子树指针
P->data = data;
P->lchild = NULL;
P->rchild = NULL;
if (T == NULL) {
T = P;
}
//先左后右
else {
if (T->lchild == NULL) {
T->lchild = P;
} else {
T->rchild = P;
}
}
}
//先序查找父元素
void preOrderSearch(BiTree T, ElemType x, BiTree &result) {
if (T) {
//cout <<"CMP "<< T->data <<" AND "<<x<<endl;
if (T->data == x){
result = T;
}
preOrderSearch(T->lchild, x, result);
preOrderSearch(T->rchild, x, result);
}
} // PreOrder
//递归求最大深度
int maxDiameter = 0;
int MaxDepth(BiTree &T) {
if (T == NULL) return 0;
int leftDepth = MaxDepth(T->lchild);
int rightDepth = MaxDepth(T->rchild);
int diameter = leftDepth + rightDepth;
maxDiameter = diameter > maxDiameter ? diameter : maxDiameter;
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
int main() //主函数
{
BiTree P = NULL;
int n;
cin >> n;
n--;
insertData(P, 1);//第一个节点，手动插入（待优化）
// PreOrderShow(P);
while (n--) {
ElemType f, z;
cin >> f >> z;
BiTree res = NULL;
preOrderSearch(P, f, res);//查找到要插入的子树
insertData(res, z);
//PreOrderShow(res);
}
MaxDepth(P);
cout << maxDiameter;
}//main
8609 哈夫曼树【值得一看★★★】
Description
利用静态链表建立赫夫曼树，建树过程中要求左子树权值小于右子树权值，求各结点的编码。要求：叶子结点的个数n及结点值由键盘录入。本题给出程序代码,要求修改以满足测试要求.
#include "stdio.h"
#include "malloc.h"
#include "string.h"
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
void Select(HuffmanTree &HT, int n, int &s1, int &s2)
//在HT[1..n]中选择parent为0且weight最小的两个结点，
// 其序号分别为s1和s2。
{
int i;
s1=-1;s2=-1;
for (i=1;i<=n;i++) {
if (HT[i].parent==0)
if (s1==-1) s1=i;
else
if (s2==-1 )
if (HT[i].weight0)，构造哈夫曼树HT，
// 并求出n个字符的哈夫曼编码HC
int i, j, m, s1, s2, start;
char *cd;
unsigned int c, f;
if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用
for (i=1; i<=n; i++) { //初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
printf("\n哈夫曼树的构造过程如下所示：\n");
printf("HT初态:\n 结点 weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" 按任意键，继续 ...");
getch();
for (i=n+1; i<=m; i++) { // 建哈夫曼树
// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，
// 其序号分别为s1和s2。
Select(HT, i-1, s1, s2);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
printf("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" 结点 weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意键，继续 ...");
getch();
}
//--- 从叶子到根逆向求每个字符的哈夫曼编码 ---
cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间
cd[n-1] = '\0'; // 编码结束符。
for (i=1; i<=n; ++i) { // 逐个字符求哈夫曼编码
start = n-1; // 编码结束符位置
for (c=i, f=HT[i].parent; f!=0; c=f, f=HT[f].parent)
// 从叶子到根逆向求编码
if (HT[f].lchild==c) cd[--start] = '0';
else cd[--start] = '1';
HC[i] = (char *)malloc((n-start)*sizeof(char));
// 为第i个字符编码分配空间
strcpy(HC[i], &cd[start]); // 从cd复制编码(串)到HC
}
free(cd); //释放工作空间
} //HuffmanCoding
void main()
{
int i,n;
int *w;
HuffmanTree HT;
HuffmanCode HC;
printf("Node Number:");
scanf("%d",&n); //权值个数
w=(int *)malloc(n*sizeof(int));
printf("Input weights:");
for ( i=0;i<n;i++) //录入权值
scanf("%d",&w[i]);
HC=(char **)malloc((n+1)*sizeof(char*)); //0空间未用
HT=(HuffmanTree)malloc((2*n+1+1)*sizeof(HTNode));//0空间未用
HuffmanCoding(HT, HC, w, n);
printf("\n");
for (i = 1; i<n+1; i++){
puts(HC[i]); //输出哈夫曼编码
free(HC[i]); //释放空间
}
free(HC);
free(HT);
}//main
输入格式
第一行：权值个数
第二行：输入n个权值，用空格分隔
输出格式
输出n行
每行表示各权值对应的哈夫曼编码
输入样例
8
5 29 7 8 14 23 3 11
输出样例
0001
10
1110
1111
110
01
0000
001
代码实现
#include "stdio.h"
#include "malloc.h"
#include "string.h"
#include <iostream>
using namespace std;
typedef struct {
unsigned int weight;
unsigned int parent, lchild, rchild;
} HTNode, *HuffmanTree;
void Select(HuffmanTree &HT, int n, int &s1, int &s2)
//在HT[1..n]中选择parent为0且weight最小的两个结点，
// 其序号分别为s1和s2。
{
s1 = 0;//0单元不用
s2 = 0;
//找第一个
for (int i = 1; i <= n; i++) {
if (HT[i].parent == 0) {
if (s1 == 0) s1 = i;//假设当前节点最小（初始）
else if (HT[i].weight < HT[s1].weight)s1 = i;
}
}
for (int i = 1; i <= n; i++) {
//跳过s1找s2，如果找不到s2将=0
if (HT[i].parent == 0&& i != s1) {
if (s2 == 0)s2 = i;//假设当前节点最小（初始）
if (HT[i].weight < HT[s2].weight )s2 = i;
}
}
}
void createHuffmanTree(HuffmanTree &HT, int n) {
if (n <= 1) return;
int m = 2 * n - 1;//从权值节点数目推树的节点个数
HT = new HTNode[m + 1]; // 0号单元未用，实际大小需+1
for (int i = 0; i <= m; i++) { //初始化所有节点
HT[i].weight = 0;
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
for (int i = 1; i <= n; i++) { //输入权值节点（下标1到n）
cin >> HT[i].weight;
}
for (int i = n + 1; i <= m; i++) { // 即将合成的树放在i 一直往后退
int s1, s2;
Select(HT, i - 1, s1, s2);//在新树前（i前）选两颗权值最小的
//新树生成
HT[s1].parent = i;
HT[s2].parent = i;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
}
typedef char **HuffmanCode;
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int n) {
HC = new char*[n + 1];//二级指针，储存每个节点的编码
char *tmp = new char[n];//每个节点逆推得到的编码临时储存（定长）
tmp[n - 1] = '\0';// 编码结束符
for (int i = 1; i <= n; i++) {// 逐个节点求哈夫曼编码,这里1-n的节点全为初始节点
int start = n - 1;// 编码结束符位置（倒推用）
//一直回溯
int child = i, par = HT[i].parent;//子节点，双亲节点下标
while(par != 0){
if (HT[par].lchild == child) tmp[--start] = '0';//在父母的左边
else tmp[--start] = '1';//在父母的右边
child = par;
par = HT[par].parent;
}
HC[i] = new char[n-start];// 为第i个字符编码分配空间,变长编码实现
strcpy(HC[i], &tmp[start]); //缩短
}
delete tmp; //释放工作空间
} //HuffmanCoding
int main() {
int i, n;
HuffmanTree HT;
HuffmanCode HC;
cin>>n; //权值个数
//创建哈夫曼树
createHuffmanTree(HT, n);
//获取编码
HuffmanCoding(HT, HC, n);
//输出哈夫曼编码
for (i = 1; i < n + 1; i++)cout <<HC[i]<<endl;
//释放
delete HC;
delete HT;
}//main
这篇关于SCAU程序设计在线实训平台_实验_数据结构_实验4的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
增量更新怎么做？-icode9专业技术文章分享11-23
-
压缩包加密方案有哪些？-icode9专业技术文章分享11-23
-
用shell怎么写一个开机时自动同步远程仓库的代码？-icode9专业技术文章分享11-23
-
webman可以同步自己的仓库吗？-icode9专业技术文章分享11-23
-
在 Webman 中怎么判断是否有某命令进程正在运行？-icode9专业技术文章分享11-23
-
如何重置new Swiper?-icode9专业技术文章分享11-23
-
oss直传有什么好处？-icode9专业技术文章分享11-23
-
如何将oss直传封装成一个组件在其他页面调用时都可以使用？-icode9专业技术文章分享11-23
-
怎么使用laravel 11在代码里获取路由列表？-icode9专业技术文章分享11-23
-
怎么实现ansible playbook 备份代码中命名包含时间戳功能？-icode9专业技术文章分享11-22
-
ansible 的archive 参数是什么意思？-icode9专业技术文章分享11-22
-
ansible 中怎么只用archive 排除某个目录？-icode9专业技术文章分享11-22
-
exclude_path参数是什么作用？-icode9专业技术文章分享11-22
-
微信开放平台第三方平台什么时候调用数据预拉取和数据周期性更新接口？-icode9专业技术文章分享11-22
-
uniapp 实现聊天消息会话的列表功能怎么实现？-icode9专业技术文章分享11-22
栏目导航
