当前位置：首页 > web >正文

MYOJ_7443《洛谷 U556408 》【模板】二叉树基础训练 (自己上传的题，想上主题库qwq)(二叉树基础操作模板)

web 2025/7/6 23:29:31

题目描述

输入一个带空结点的先序遍历序列，生成一棵二叉树。用#表示空结点。例：根结点是A，左孩子是B，右孩子是C，这样一棵二叉树的带空结点的先序遍历序列为：AB##C##

生成二叉树后，请分别输出

这棵二叉树的深度
这棵二叉树叶子结点数
这棵二叉树的先序遍历序列
这棵二叉树的中序遍历序列
这棵二叉树的后序遍历序列
这棵二叉树的层次遍历序列

输入

一行由大写字母和#组成的字符串，为带空结点的先序遍历序列。

输出

第1行：这棵二叉树的深度第2行：这棵二叉树叶子结点数第3行：这棵二叉树的先序遍历序列第4行：这棵二叉树的中序遍历序列第5行：这棵二叉树的后序遍历序列第6行：这棵二叉树的层次遍历序列

样例输入输出

输入：ABD###CE##F##

输出：
3
3
ABDCEF
DBAECF
DBEFCA
ABCDEF

思路：

模板，无需多说

STEP 1:节点数组，指针初始指向数组开头，每个节点包含一个字符值val和左右子节点指针

STEP 2:递归建树，“#”空节点，使用先序遍历顺序创建树（根-左-右），每次调用会消耗两个字符（左右子节点）

STEP 3:递归计算树的深度，空节点深度为0，非空节点深度为左右子树深度最大值加1

STEP 4:递归计算叶子节点：空节点返回0，左右子节点都为空的是叶子节点，返回1，否则返回左右子树叶子节点数之和

STEP 5:遍历顺序，再再再讲一遍：

先序：根-左-右
中序：左-根-右
后序：左-右-根

STEP 5:使用队列实现BFS层次遍历,按层次从上到下、从左到右遍历节点每个节点出队时打印值，并将其非空子节点入队

STEP 6:输入，建树，按要求输出。

代码

#include<bits/stdc++.h>
#define N 105
using namespace std;
struct Node
{char val;Node*left,*right;
}node[N],*p=node;
//扩展先序遍历序列的第一个字符是v，生成一棵树，返回树根节点地址 
Node*createTree(char v)
{if(v=='#'){return NULL;}Node*np=++p;np->val=v;np->left=createTree(getchar());np->right=createTree(getchar());return np;
}
//二叉树深度 
int getDepth(Node*r)
{int le,ri;if(r==NULL){return 0;}else{le=getDepth(r->left);ri=getDepth(r->right);return le>ri?(le+1):(ri+1);}
}
//二叉树叶子结点个数 
int NodeNum(Node*r)
{if(r==NULL){return 0;}else if(r->left==NULL&&r->right==NULL){return 1;}return NodeNum(r->left)+NodeNum(r->right);
}
//先序遍历以r为根的子树 
void preOrder(Node*r)
{if(r==NULL){return;}cout<<r->val;preOrder(r->left);preOrder(r->right);
}
//中序遍历以r为根的子树 
void inOrder(Node*r)
{if(r==NULL){return;}inOrder(r->left);cout<<r->val;inOrder(r->right);
}
//后序遍历以r为根的子树 
void postOrder(Node*r)
{if(r==NULL){return;}postOrder(r->left);postOrder(r->right);cout<<r->val;
}
//树的层次遍历
void bfs(Node*v)
{queue<Node*>que;que.push(v);while(!que.empty()){Node*z=que.front();cout<<z->val;que.pop();Node*ch[2]={z->left,z->right};for(int i=0;i<2;i++){if(ch[i]!=NULL){que.push(ch[i]);}}}
}
int main()
{Node*root=createTree(getchar());cout<<getDepth(root)<<"\n";cout<<NodeNum(root)<<"\n";preOrder(root);cout<<"\n";inOrder(root);cout<<"\n";postOrder(root);cout<<"\n";bfs(root);return 0;
}