SCAU 数据结构实验四树

58 阅读 0 评论 0 点赞

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 <iostream>
#include <cstdio>
#include <cstring>

using namespace std;
char tree[105];//树
char s[105];
int j=1,len;//j是读取字符串s时的指针，读取一个字符移动一次

void create(int root)//建树
{
    char ch;
    if(j>len)    return;//字符串结束（防止越界，第一次就错在这了）
    ch=s[j++];
    if(ch=='#')  return;//这里条件可以整理笔记
    tree[root]=ch;      //不符合上面所有条件才是我们想要的结点
    create(2*root);//左子树
    create(2*root+1);//右子树
}

void xian(int root)
{
    if(tree[root]=='\0') return;
    
    cout<<tree[root];//最先访问根结点
    xian(2*root);
    xian(2*root+1);
}

void zhong(int root)
{
    if(tree[root]=='\0') return;
    
    zhong(2*root);
    cout<<tree[root];//第二步访问根结点
    zhong(2*root+1);
}

void hou(int root)
{
    if(tree[root]=='\0') return;
    
    hou(2*root);
    hou(2*root+1);
    cout<<tree[root];//最后访问根结点
}
int main()
{
    gets(s+1);
    len=strlen(s+1);
    create(1);
    xian(1);
    cout<<endl;
    zhong(1);
    cout<<endl;
    hou(1);
    cout<<endl;
    return 0;
}

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<iostream>
#include<cstring>
using namespace std;
const int N=105;
char tree[N];
char s[N];
int id=1,len,num0,num1,num2;

void creat(int k){
	
	if(id>len) return ;
	
	char ch;
	ch=s[id++];
	if(ch=='#')return ;
	
	tree[k]=ch;
	creat(2*k);
	creat(2*k+1);
	
}

void deep(int k){
	if(tree[k]=='\0') return ;
	
	if(tree[k*2]!='\0'&&tree[k*2+1]!='\0')
	num2++;
	else if(tree[k*2]=='\0'&&tree[k*2+1]=='\0')
	num0++;
	else 
	num1++;
	
	deep(k*2);
	deep(k*2+1);
}
int main(){
	gets(s+1);
	len=strlen(s+1);
	creat(1);
	deep(1);
	cout<<num2<<endl<<num1<<endl<<num0<<endl;
	return 0;
}

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

输出样例

层次遍历

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=55;
char tree[N][3];
int n,ans,cnt,x,y;


int main(){
	memset(tree, 0, sizeof(tree));
	
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>x>>y;
		tree[x][1]?tree[x][2]=y:tree[x][1]=y;
		
	}
	//层次遍历
	ans=1;
	queue<int>q;
	//根节点入队
	q.push(1);
	//队列不为空
	while(q.size()){
		int len=q.size();
        ans=max(len,ans);
        
        for(int i=0;i<len;i++)
        {
            int t=q.front();
            q.pop();//弹出队头元素
            if(tree[t][1])
                q.push(tree[t][1]);
            if(tree[t][2])
                q.push(tree[t][2]);
        }
    }
    cout << ans;
	return 0;
}

18724 二叉树的遍历运算

Description

二叉树的三种遍历都可以通过递归实现。
如果我们知道一棵二叉树的先序和中序序列，可以用递归的方法求后序遍历序列。

输入格式

两行，第一行一个字符串，表示树的先序遍历，第二行一个字符串，表示树的中序遍历。
树的结点一律用小写字母表示,且字符串长度不超过30。

输出格式

一个字符串，树的后序序列。

输入样例

abcde
bcade

输出样例

cbeda

#include <iostream>
#include <cstring>
#include <queue>
#include<string>
using namespace std;
const int N = 55;

void tree (string pre,string in){
	if(pre=="\0"||in=="\0")return ;
	
	//找到根节点在中序序列中对应的下标
	int pos=in.find(pre[0]);
	
	//递归左子树
	//先序序列的左子树是从下标1开始，长度为pos的子串（下标0是根）
	//中序序列的左子树是下标0开始，长度为pos的子串
	tree(pre.substr(1,pos),in.substr(0,pos));
	
	//递归右子树
	//先序序列的右子树是从下标1+pos开始到末尾的子串
	//中序序列的右子树是从下标1+pos开始到末尾的子串
	tree(pre.substr(1+pos),in.substr(1+pos));
	
	//输出根节点
	cout<<pre[0];
}
int main() {
    string pre ,in;
    cin>>pre>>in;
    tree(pre,in);
    return 0;
}

substr的用法

int main() {
    std::string str = "Hello, World!";
    
    std::string substr1 = str.substr(7, 5); // 从索引7开始，长度为5的子串
    std::cout << substr1 << std::endl; // 输出: World

    std::string substr2 = str.substr(7); // 从索引7开始直到字符串末尾
    std::cout << substr2 << std::endl; // 输出: World!

    std::string substr3 = str.substr(0, 5); // 从索引0开始，长度为5的子串
    std::cout << substr3 << std::endl; // 输出: Hello

    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

输出样例

这个方法看似巧妙，实际有大问题
校oj的数据太弱

#include <iostream>
#include <cstring>
#include <queue>
#include<string>
using namespace std;
const int N=1000;
int tree[N][N]; 
int n,x,y,ans;

int dfs(int k){
	if(!k)return 0; 
	int lchild=dfs(tree[k][1]);
	int rchild=dfs(tree[k][2]);
	//是路径不是节点数
	ans=max(ans,lchild+rchild);
	int len=max(lchild,rchild)+1;
	return len; 
}
int main() {
   cin>>n;
   for(int i=1;i<n;i++){
	cin>>x>>y;
	if(tree[x][1])tree[x][2]=y;
	else tree[x][1]=y;
   }
   dfs(1);
   cout<<ans;
    return 0;
}

本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！

转载请注明出处：免费源码网-免费的源码资源网站 » SCAU 数据结构实验四树

点赞(0) 打赏

本文分类：文章资讯
本文标签：SCAU 数据结构实验四树
浏览次数：58 次浏览
本文链接：https://freeymw.com/article/12036.html

上一篇 > BC C language
下一篇 > OpenCv之简单的人脸识别项目（特征标注页面）

评论列表共有 0 条评论

暂无评论

SCAU 数据结构 实验四 树

8606 二叉树的构建及遍历操作

17121 求二叉树各种节点数

18924 二叉树的宽度

18724 二叉树的遍历运算

18923 二叉树的直径

评论列表 共有 0 条评论

发表评论 取消回复

SCAU 数据结构实验四树

评论列表共有 0 条评论

发表评论取消回复