9 solutions

  • 5
    @ 2023-12-27 19:48:50

    题意

    第 ii 行输入 ii 的左子树和右子树，0 代表没有子树。

    思路

    先找出根，然后先序中序后序输出

    先序：先输出根，然后有左子树就递归下去，有右子树也递归下去

    中序：同理，输出顺序变成 左子树→根→右子树

    后序：同理，输出顺序变成 左子树→右子树→根

    拓展（层次遍历）

    层次遍历：按层数从上到下从左到右输出

    先把根推进队列

    然后只要队列没空（循环），把队列第一个节点的左子树推进队列（如果有的话），然后把右子树推进队列（同理）

    代码

    #include <bits/stdc++.h>
using namespace std;
int a[1000005][2],t[1000005];	// a 来存树，t 来找根
void xian(int g);	// 先序遍历
void zhong(int g);	// 中序遍历
void hou(int g);	// 后序遍历
void bfs(int g);	// 层次遍历
int main(int argc, char **argv){
	int n,rt = 1;	// rt 是根
	cin >> n;
	for (int i = 1;i <= n;i++){
		cin >> a[i][0] >> a[i][1];	// 输入 ai 节点的左孩子和右孩子
		t[a[i][0]] = 1;	// 标记他们不是根节点
		t[a[i][1]] = 1;
	}
	for (int i = 1;i <= n;i++){	// 寻找根节点
		if (!t[i]){
			rt = i;
			break;
		}
	}
	xian(rt);	// 先序遍历
	printf("\n");
	zhong(rt);	// 中序遍历
	printf("\n");
	hou(rt);	// 后序遍历
//	printf("\n");
//	bfs(rt);	// 层次遍历
	return 0;
}
void xian(int g){
	printf("%d ",g);	// 先输出根
	if (a[g][0])	xian(a[g][0]);	// 左孩子
	if (a[g][1])	xian(a[g][1]);	// 右孩子
}
void zhong(int g){
	if (a[g][0])	zhong(a[g][0]);	// 左孩子
	printf("%d ",g);	// 在中间输出根
	if (a[g][1])	zhong(a[g][1]);	// 右孩子
}
void hou(int g){
	if (a[g][0])	hou(a[g][0]);	// 左孩子
	if (a[g][1])	hou(a[g][1]);	// 右孩子
	printf("%d ",g);	// 后输出根
}
void bfs(int g){
	queue<int> q;
	q.push(g);	// 存入根
	while(!q.empty()){	// 遍历树
		int x = q.front();	// 找到当前根
		printf("%d ",x);
		if (a[x][0])	q.push(a[x][0]);	// 有左孩子，把孩子放进来（下一层）
		if (a[x][1])	q.push(a[x][1]);	// 有右孩子，把孩子放进来（下一层）
		q.pop();
	}
}
    • 4
      @ 2023-12-27 19:35:54 
      #include<bits/stdc++.h>
using namespace std;
int arr[1000000][12];

void qian(int x){
    cout<<x<<' ';
    if(arr[x][0]!=0) qian(arr[x][0]);
    if(arr[x][1]!=0) qian(arr[x][1]);
}
void zhong(int x){
    if(arr[x][0]!=0) zhong(arr[x][0]);
    cout<<x<<' ';
    if(arr[x][1]!=0) zhong(arr[x][1]);
}
void hou(int x){
    if(arr[x][0]!=0) hou(arr[x][0]);
    if(arr[x][1]!=0) hou(arr[x][1]);
    cout<<x<<' ';
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>arr[i][0]>>arr[i][1];
    qian(1);
    cout<<'\n';
    zhong(1);
    cout<<'\n';
    hou(1);
    return 0;
}
      • 4
        @ 2023-12-27 19:27:38 
        #include <iostream>
using namespace std;

struct node
{
    int lc;
    int rc;   
}tree[100000];

void qx(int dq)
{
	cout << dq << " ";
	if(tree[dq].lc!=0)qx(tree[dq].lc);
	if(tree[dq].rc!=0)qx(tree[dq].rc);
}

void zx(int dq)
{
	if(tree[dq].lc!=0)zx(tree[dq].lc);
	cout << dq << " ";
	if(tree[dq].rc!=0)zx(tree[dq].rc);
}

void hx(int dq)
{
	if(tree[dq].lc!=0)hx(tree[dq].lc);
	if(tree[dq].rc!=0)hx(tree[dq].rc);
	cout << dq << " ";
}

int main()
{
    int n;
    cin >> n;
    for (int i=1;i<=n;i++)
    {
        cin >> tree[i].lc >> tree[i].rc;
    }
    qx(1);
    cout << endl;
    zx(1);
    cout << endl;
    hx(1);
    cout << endl;
}
        • 3
          @ 2023-12-26 22:19:19 
          像桶一样,用下标存储左右儿子

          #include<iostream>
using namespace std;
const int N=10e6;
struct node
{
 int l,r;//左右儿子
}tree[N];//一棵"树"
void pre(int x)
{
 cout<<x<<" ";//前序
 if(tree[x].l!=0)pre(tree[x].l);
 if(tree[x].r!=0)pre(tree[x].r);
}
void mid(int x)
{
 if(tree[x].l!=0)mid(tree[x].l);
 cout<<x<<" ";//中序
 if(tree[x].r!=0)mid(tree[x].r);
}
void end(int x)
{
 if(tree[x].l!=0)end(tree[x].l);
 if(tree[x].r!=0)end(tree[x].r);
 cout<<x<<" ";//后序
}
int main()
{
 int n;
 cin>>n;//输入
 for(int i=0;i<n;i++)
 {
  int l,r;
  cin>>l>>r;//输入
  tree[i+1].l=l;//设置左
  tree[i+1].r=r;//设置右
 }
 pre(1);cout<<endl;//输出
 mid(1);cout<<endl;//输出
 end(1);cout<<endl;//输出
 return 0;//完结散花
}
          • 2
            @ 2025-1-18 14:04:55 
            //freopen("xx.in","r",stdin);
//freopen("xx.out","w",stdout);
#include<bits/stdc++.h>
#include<iostream> 
#include<iomanip>
#include<cmath>
#include<algorithm> 
#include<string> 
#include<cstdio>
#include<cstring> 
//#include<vector>
//#include<map>
//#include<stack>  
//#include<queue> 
//#include<set>
using namespace std; 
struct node{
	int x,y;
};
node g[100010];
int yt[100010];
int dfsqian(int u){//前序遍历
	cout<<u<<" ";
	if(g[u].x!=0)dfsqian(g[u].x);
	if(g[u].y!=0)dfsqian(g[u].y);
}
int dfszhong(int u){//中序遍历
	if(g[u].x!=0)dfszhong(g[u].x);
	cout<<u<<" ";
	if(g[u].y!=0)dfszhong(g[u].y);
}
int dfshou(int u){//后序遍历
	if(g[u].x!=0)dfshou(g[u].x);
	if(g[u].y!=0)dfshou(g[u].y);
	cout<<u<<" ";
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>g[i].x;
		cin>>g[i].y;
	}
	dfsqian(1);
	cout<<'\n';
	dfszhong(1);
	cout<<'\n';
	dfshou(1);
	return 0;
	
}
            • 2
              @ 2023-12-27 20:09:55 
              #include<iostream>
#include<queue>
using namespace std;
int tree[10000000][2],n;
void fro(int x){
     cout<<x<<" ";
     if(tree[x][0]!=0) fro(tree[x][0]);
     if(tree[x][1]!=0) fro(tree[x][1]);
}//前序
void mid(int x){
     if(tree[x][0]!=0) mid(tree[x][0]);
     cout<<x<<" ";
     if(tree[x][1]!=0) mid(tree[x][1]);
}//中序
void end(int x){
     if(tree[x][0]!=0) end(tree[x][0]);
     if(tree[x][1]!=0) end(tree[x][1]);
     cout<<x<<" ";
}//后室(bushi)
void BFS(int root){
     queue<int> bfs;
     bfs.push(root);
     while(bfs.empty()!=true){
          int x=bfs.front();
          bfs.pop();
          cout<<x<<" ";
          if(tree[x][0]!=0) bfs.push(tree[x][0]);
          if(tree[x][1]!=0) bfs.push(tree[x][1]);
     }
}//BFS

int main(){
     cin>>n;
     for(int i=1;i<=n;i++){
          cin>>tree[i][0];
          cin>>tree[i][1];
     }
     fro(1);
     cout<<endl;
     mid(1);
     cout<<endl;
     end(1);
     cout<<endl;
}

              我是litianyue小号，这个歹马带上了BFS

              • 0
                @ 2025-1-18 13:52:27 
                #include<cstdio>
#define maxn (int)(1e6)

struct node
{
	int left,right;
};

node tree[maxn]={};
int n;

void pre_order(int);
void in_order(int);
void post_order(int);

int main()
{
	scanf("%d",&n);
	
	for(int i=1;i<=n;++i)
		scanf("%d %d",&tree[i].left,&tree[i].right);
	
	pre_order(1);
	printf("\n");
	
	in_order(1);
	printf("\n");
	
	post_order(1);
	printf("\n");
	
	return 6;
}

//前序
void pre_order(int n)
{
	if(n==0)
		return;
	
	printf("%d ",n);
	pre_order(tree[n].left);
	pre_order(tree[n].right);
}

//中序
void in_order(int n)
{
	if(n==0)
		return;
	
	in_order(tree[n].left);
	printf("%d ",n);
	in_order(tree[n].right);
}

//后序
void post_order(int n)
{
	if(n==0)
		return;
	
	post_order(tree[n].left);
	post_order(tree[n].right);
	printf("%d ",n);
}
                • 0
                  @ 2023-12-27 20:14:24 
                  #include<iostream>
#include<string>
#include<stack>
#include<queue>
using namespace std;
int tree[100000][3];
queue<int>q1;
void bfs(int r){
	q1.push(r);
	while(!q1.empty()){
		int x=q1.front();
		q1.pop();
		cout<<x<<" ";
		if(tree[x][1]!=0){
		q1.push(tree[x][1]);	
		}
		if(tree[x][2]!=0){
		q1.push(tree[x][2]);	
		}
	}
}
void qx(int x){
	cout<<x<<" ";
		if(tree[x][1]!=0){
		qx(tree[x][1]);	
		}
		if(tree[x][2]!=0){
		qx(tree[x][2]);
		}
}
void zx(int x){
        if(tree[x][1]!=0){
		zx(tree[x][1]);	
		}
		cout<<x<<" ";
		if(tree[x][2]!=0){
		zx(tree[x][2]);
		}
		
}
void hx(int x){
        if(tree[x][1]!=0){
		hx(tree[x][1]);	
		}
		
		if(tree[x][2]!=0){
		hx(tree[x][2]);
		}
		cout<<x<<" ";
}  
int main(){
	int n,lc,rc;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>lc>>rc;
		tree[i][1]=lc;
		tree[i][2]=rc;
	}
	qx(1);
	cout<<endl;
    zx(1);
    cout<<endl;
    hx(1);
}
                  • -8
                    @ 2023-12-27 19:32:50 
                    #include<bits/stdc++.h>
using namespace std;
struct node{
	int a;
	int l,r;
}a[int(2e+6)];
void f1(node x){
	cout<<x.a<<" ";
	if(x.l)
	f1(a[x.l]);
	if(x.r)
	f1(a[x.r]);
}
void f2(node x){
	if(x.l)
	f2(a[x.l]);
	cout<<x.a<<" ";
	if(x.r)
	f2(a[x.r]);
}
void f3(node x){
	if(x.l)
	f3(a[x.l]);
	if(x.r)
	f3(a[x.r]);
	cout<<x.a<<" ";
}

int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		a[i].a=i;
		cin>>a[i].l>>a[i].r;
	}
	f1(a[1]);
	cout<<"\n";
	f2(a[1]);
	cout<<"\n";
	f3(a[1]);
	cout<<"\n";
}
                    • @ 2023-12-27 19:48:25

                      我推huangyuran👍👍 ，因为他的题解代码清晰👀️ ，思路明了🚀️ ，简直就是教科书级的题解，之后他每次题解我都会**点赞*

                      ***❤️ ❤️

                    • @ 2023-12-27 19:57:45

                      我推huangyuran👍👍 ，因为他的题解​歹🐎清晰​👀️ ，​死路明了​🚀️ ，简直就是胶壳树级的题解，之后他每次题解我都会**巅寁*

                      ***❤️ ❤️

                    • @ 2023-12-27 20:16:05

                      我杀huangyuran 👎👎，因为他的题解​歹🐎斯人​👀️ ，​死路明了​ 😕，简直就是大沟市级的题解，每次他发的题解我都会**插屏*

                      ***

                    • @ 2023-12-29 20:15:16

                      @ 上一个爱心没换 我杀huangyuran 👎👎，因为他的题解​歹🐎斯人​👀️ ，​死路明了​ 😕，简直就是大沟市级的题解，每次他发的题解我都会**插屏*

                      *** 👎 👎

                    • @ 2023-12-29 20:19:01

                      @ 我退黄鱼然，因为他的体接待吗侵袭，思路民聊，简直就是教科书的题解，zhihoutameicitijiewodohuidianzan

                    • @ 2024-1-21 19:45:10

                      我推huangyuran👍👍 ，因为他的题解​歹🐎氢烯​👀️ ，​死鹿冥料​🚀️ ，简直就是胶咳鼠级的题解，之后他每次题解我都会**电糌*

                      ***❤️ ❤️

                    • @ 2024-1-23 21:21:33

                      一个爱好和平的lj系（Only on Line）

                      //不转载自垃圾锐云何

                      年龄：十二（好吧，其实系12.99……）

                      喜欢：写代码，写歹马，写题解，折腾讨论……打篮球、游泳、写文案、写小说、玩游戏……青色、简约风、光滑、纯色、明亮……芒果、草莓、哈密瓜……酸汤肥牛、方便面、魔芋爽、风味海带、炖羊肉、鱼汤、兰州拉面……硬科幻、科普、历史……（为防止误会，先声明，这里的是朋友，不是大家常说的喜欢）夏晓曦、黄尚、黄月、黄武、肖林熹、蒋余涵、刘雅琪、唐彦霖、赵圣熹、潘焯欣、潘伟明、黄旻哲、林子轩、庄皓钧、周宛曈、巩亮……曾腹肌、黄惠霞老师、综合实践刘老师、1号好宿管、2号好宿管、胖胖女宿管……tiger（有点特殊，课外老师就1个啦）……数学刘老师、科学肖老师、科学陈老师……

                      综上所述，我好像有点泛爱呢！

                      讨厌的东西：榴莲、关BB、LTY、括号写下面的歹马@潘伟明、不是为了评价而是为了好玩或针对某人的无脑差评（虽然我也无所谓，差评不影响RP）@李天粤。

                      我的优点：阳光开朗、五官端正、需要智商时智商在线、智商在线时不低、正义感强、没有框架、为人随和、幽默有趣

                      我的缺点：有良心、智商长期不在线、情绪易受他人影响、情绪不好时不会克制、体质--、瘦弱（身高只有1660000微米左右，体重只有0.08吨）、有时会在还没反应过来时说脏话。

                      最喜欢的东西：斥巨资（￥50！50!）买的三国杀（过年我爷爷给的红包钱，心在滴血）

                      最喜欢的人：夏晓曦^v^

                      偶像：于谦（明朝那个，对，就被朱祁镇斩了的辣个）

                      兽技：13694266123（我妈不让我把兽技卡从手表里拔出来，所以有防骚扰，你懂得，您拨打的用户正在通话中辣种）

                      萎信：HYR130808

                      账户通用密码：校内才能看

                  • 1

                  二叉树的遍历

                  Information

                  ID
                  968
                  Time
                  1000ms
                  Memory
                  128MiB
                  Difficulty
                  5
                  Tags
                  # Submissions
                  89
                  Accepted
                  35
                  Uploaded By
                  1. About
                  2. Contact Us
                  3. Privacy
                  4. Terms of Service
                  5. Copyright Complaint
                  6. Language
                  7. Legacy mode
                  8. Theme
                  2. 粤ICP备2022044963号-1
                  3. Worker 0, 27ms
                  4. Powered by Hydro v4.13.3 Community