projects / deliverable / binutils-gdb.git / blame
| Commit | Line | Data |
|---|---|---|
| d0ce17d8 CT |
1 | /* This testcase is part of GDB, the GNU debugger. |
| 2 | ||
| 88b9d363 | 3 | Copyright 2020-2022 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 | } |