1/* This testcase is part of GDB, the GNU debugger. 2 3 Copyright 2020 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 21struct node { 22 int id; 23 node *left; 24 node *right; 25 bool visited; 26}; 27 28node node_array[50]; 29unsigned int CUR_IDX = 0; 30 31node * 32make_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 43void 44tree_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 62void 63inorder (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 85int 86main (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