1 /* This testcase is part of GDB, the GNU debugger.
2
3 Copyright 2020-2024 Free Software Foundation, Inc.
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 *
make_node(int val)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
tree_insert(node * root,int val)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
inorder(node * root)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
main(int argc,char ** argv)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 }
98