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
输出样例
2
层次遍历
#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
输出样例
3
这个方法看似巧妙，实际有大问题
校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;
}
