]>
Commit | Line | Data |
---|---|---|
d0ce17d8 CT |
1 | /* This testcase is part of GDB, the GNU debugger. |
2 | ||
3666a048 | 3 | Copyright 2020-2021 Free Software Foundation, Inc. |
d0ce17d8 CT |
4 | |
5 | This program is free software; you can redistribute it and/or modify | |
6 | it under the terms of the GNU General Public License as published by | |
7 | the Free Software Foundation; either version 3 of the License, or | |
8 | (at your option) any later version. | |
9 | ||
10 | This program is distributed in the hope that it will be useful, | |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
13 | GNU General Public License for more details. | |
14 | ||
15 | You should have received a copy of the GNU General Public License | |
16 | along with this program. If not, see <http://www.gnu.org/licenses/>. */ | |
17 | ||
18 | #include <iostream> | |
19 | #include <vector> | |
20 | ||
21 | struct node { | |
22 | int id; | |
23 | node *left; | |
24 | node *right; | |
25 | bool visited; | |
26 | }; | |
27 | ||
28 | node node_array[50]; | |
29 | unsigned int CUR_IDX = 0; | |
30 | ||
31 | node * | |
32 | make_node (int val) | |
33 | { | |
34 | node *new_node = &(node_array[CUR_IDX++]); | |
35 | new_node->left = NULL; | |
36 | new_node->right = NULL; | |
37 | new_node->id = val; | |
38 | new_node->visited = false; | |
39 | ||
40 | return new_node; | |
41 | } | |
42 | ||
43 | void | |
44 | tree_insert (node *root, int val) | |
45 | { | |
46 | if (val < root->id) | |
47 | { | |
48 | if (root->left) | |
49 | tree_insert (root->left, val); | |
50 | else | |
51 | root->left = make_node(val); | |
52 | } | |
53 | else if (val > root->id) | |
54 | { | |
55 | if (root->right) | |
56 | tree_insert (root->right, val); | |
57 | else | |
58 | root->right = make_node(val); | |
59 | } | |
60 | } | |
61 | ||
62 | void | |
63 | inorder (node *root) | |
64 | { | |
65 | std::vector<node *> todo; | |
66 | todo.push_back (root); | |
67 | while (!todo.empty()) | |
68 | { | |
69 | node *curr = todo.back(); | |
70 | todo.pop_back(); /* break-here */ | |
71 | if (curr->visited) | |
72 | std::cout << curr->id << " "; | |
73 | else | |
74 | { | |
75 | curr->visited = true; | |
76 | if (curr->right) | |
77 | todo.push_back (curr->right); | |
78 | todo.push_back (curr); | |
79 | if (curr->left) | |
80 | todo.push_back (curr->left); | |
81 | } | |
82 | } | |
83 | } | |
84 | ||
85 | int | |
86 | main (int argc, char **argv) | |
87 | { | |
88 | node *root = make_node (35); | |
89 | ||
90 | tree_insert (root, 28); | |
91 | tree_insert (root, 20); | |
92 | tree_insert (root, 60); | |
93 | ||
94 | inorder (root); | |
95 | ||
96 | return 0; | |
97 | } |