当前位置：网站首页>树的的遍历

树的的遍历

2022-04-22 05:50:00 【FOWng_lp】

先序遍历

简记：根左右

后序遍历

简记：左右根

中序遍历

简记：左根右

先序遍历21nod 1591

在这里插入图片描述

#include<cstdio>
#include<iostream>
using namespace std;
struct node{
    
	int l;
	int r;
	};
struct node N[100005];
void search(int cnt){
    
	if(cnt==0)return;
	cout << cnt << endl;
	search(N[cnt].l);
	search(N[cnt].r);
	}
int main(){
    
	int n,a,b;
	cin >> n;
	for(int i = 1;i <= n;i++){
    
		cin >> a >> b;
		N[i].l = a;
		N[i].r = b;
		}
	search(1);

	return 0;
	}

后续遍历51node 2350

在这里插入图片描述

#include<cstdio>
#include<iostream>
using namespace std;
struct node{
    
	int l;
	int r;
	};
struct node N[100005];
int ct[100005];
void search(int cnt){
    
	if(cnt==0)return;
	search(N[cnt].l);
	search(N[cnt].r);
	cout << cnt << endl;
	}
int main(){
    
	int n,a,b;
	cin >> n;
	for(int i = 1;i <= n;i++){
    
		cin >> a >> b;
		N[i].l = a;
		N[i].r = b;
		}
	search(1);

	return 0;
	}

POJ 2499

http://poj.org/problem?id=2499

在这里插入图片描述

题目大意
特殊结构的二叉树求最小路径
每一个节点为（a，b）数对，其左子节点一定为（a+b,b）右子节点一定为（a,a+b）,根节点是（1,1）。问到达指定节点（a,b）最小走的次数中，需要往左子节点走多少次，往右子节点多少次。
注意此二叉树可以自行构造！

#include<cstdio>
#include<iostream>
using namespace std;
int main(){
    
	int n,a,b,ans1,ans2;
	cin >> n;
	for(int i = 1;i <= n;i++){
    
		cout << "Scenario #"<<i<<':'<<endl;
		cin >> a >> b;
	// cout << a << " ok "<< b <<endl;
		ans1 = 0,ans2=0;
		while(a!=1||b!=1){
    
			//qcout<< "ok" <<endl;
			if(a==b){
    
				ans1+=(a-1);
				ans2+=(b-1);
				break;
				}
			if(a==1||b==1){
    
				ans1+=(a-1);
				ans2+=(b-1);
				break;
				}
			if(a>b){
    
				ans1 += a / b;
				a = a%b;
				}
			if(b>a){
    
				ans2 += b/a;
				b = b%a;
				}
			}
			cout << ans1 << ' ' << ans2 <<endl;
			cout <<endl;
		}
	return 0;
	}