C++ program doing BST search


👍 g++ -std=c++11 bst_search.cpp
👍 ./a.out
      *
    31
        *
      29
        *
  25
      *
    20
      *
13
      *
    12
      *
  10
      *
    2
      *
found: 20
not found: 26

👍 cat bst_search.cpp
#include <iostream>
using namespace std;

typedef int Item;
struct node{Item item; node *l, *r;};
typedef node *link;

void printnode(Item x, int h, 
               bool external) {
  for (int i = 0; i < h; i++) 
    cout << "  ";
  if (external)
    cout << '*' << endl;
  else
    cout << x << endl;  
}

void show(link t, int h) {
  if (t == 0) {
    printnode(0, h, true); 
    return;
  }
  show(t->r, h+1);
  printnode(t->item, h, false);
  show(t->l, h+1);
}

Item* search(link p, Item i) {
  while (p != 0)
    if (i == p->item)
      return &p->item;
    else if (i < p->item)
      p = p->l;
    else
      p = p->r;
  return 0;
}

int main() {
  node n2{2}; 
  node n12{12}; 
  node n10{10, &n2, &n12}; 

  node n29{29}; 
  node n31{31, &n29}; 
  node n20{20}; 
  node n25{25, &n20, &n31}; 
 
  node n13{13, &n10, &n25}; 

  show(&n13, 0);

  Item *ptr;
  ptr = search(&n13, 20);
  if (ptr == 0)
    cout << "not found" << endl;
  else
    cout << "found: " << *ptr << endl;

  ptr = search(&n13, 26);
  if (ptr == 0)
    cout << "not found: 26" << endl;
  else
    cout << "found: " << *ptr << endl;
}


    

6.3 Searching a Binary Search Tree p222 of