当前位置：网站首页>Traversal of tree

Traversal of tree

2022-04-23 05:08:00 【FOWng_ lp】

The first sequence traversal

Brief notes ： Root left and right

After the sequence traversal

Brief notes ： Left and right

In the sequence traversal

Brief notes ： Left root right

The first sequence traversal 21nod 1591

Insert picture description here

#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;
	}

Subsequent traversal 51node 2350

Insert picture description here

#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

Insert picture description here

The main idea of the topic
Finding the minimum path of binary tree with special structure
Each node is （a,b） Number pair , Its child node must be left （a+b,b） The right child node must be （a,a+b）, The root node is （1,1）. Ask to reach the specified node （a,b） The minimum number of walks , How many times do I need to go to the left child node , How many times to the right child node .
Note that this binary tree can be constructed by itself ！

#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;
	}