YZOJ P3643 题解

发表于 | 阅读次数：

题面：https://fzyzoi.tk/OnlineJudge/problem_show.php?id=3643

主要思路就是建一棵树，然后根据三种遍历的定义写一个函数，再分别输出遍历结果。

  • Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/*
	3
	2 3
	0 0
	0 0
*/
/*
	1 2 3
	2 1 3
	2 3 1
*/
#include <cstdio>
#define maxn 100000

int n/*结点数*/, l[maxn + 10]/*左儿子*/, r[maxn + 10]/*右儿子*/;

struct tree {/*树的结构体*/
	int data;
	tree *lchild, *rchild;
};

namespace Lonely {
	inline int read() {
		#define in(n) n=read()
	    register int x=0; register char ch = getchar();
	    for(; ch < '0' || ch > '9'; ch = getchar());
	    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	    return x;
    }

    inline void write(int x) {
    	#define out(n) write(n)
    	#define outn(n) write(n), putchar('\n')
	    if(x < 0) {putchar('-');x = -x;}
	    if(x >= 10)write(x / 10);
	    putchar(x % 10 + '0');
    }

    tree *ctetree(int i) {/*建树*/
    	tree *t = NULL;
		t = new tree();
		t -> data = i;
		if(l[i])t -> lchild = ctetree(l[i]);
		if(r[i])t -> rchild = ctetree(r[i]);
		return t;
	}

	void pre(tree *root) {/*前序*/
		if(root) {
			out(root -> data), putchar(' ');
			pre(root -> lchild);
			pre(root -> rchild);
		}
		else return;
	}

	void ino(tree *root) {/*中序*/
		if(root) {
		   ino(root -> lchild);
		   out(root -> data), putchar(' ');
		   ino(root -> rchild);
	    }
	    else return;
	}

	void pos(tree *root) {/*后序*/
		if(root) {
		   pos(root -> lchild);
		   pos(root -> rchild);
		   out(root -> data), putchar(' ');
	    }
	    else return;
	}

	int Main() {/*分别输出*/
		in(n);
		for(int i = 1; i <= n; i++)
		    in(l[i]), in(r[i]);
		tree *root = ctetree(1);
		pre(root);
		putchar('\n');
		ino(root);
		putchar('\n');
		pos(root);
		return 0;
	}
}

int main() {
	return Lonely::Main();
}

$\color{gray}{\mathcal{By}}$ $\color{gray}{\mathfrak{NULL}}$