draw a BST with numbers using C++ Turtle

on mac, install XQuartz, download CTurtle.hpp and CImg.h



👍 g++ -std=c++14 -lX11 draw_bst.cpp && ./a.out
13 10 25 2 12 20 31 29 

    31
      29
  25
    20
13
    12
  10
    2

  inorder: 2 10 12 13 20 25 29 31 

👍 cat draw_bst.cpp
#include <iostream>
#include "CTurtle.hpp"
using namespace std;

template<class T> 
struct BSTNode {
  T key;
  BSTNode *left, *right;
  BSTNode(T k, BSTNode *l = 0, 
               BSTNode *r = 0) {
    key = k; left = l; right = r;
  }
};

template<class T> 
class BST {
private:
  BSTNode<T> *root;
  void printTree(BSTNode<T> *r, int depth){
    if(!r) return;
    printTree(r->right, depth + 2);
    cout << string(depth, ' ') 
         << r->key << endl;
    printTree(r->left, depth + 2);
  }
  template<typename F>
  void drawTree(cturtle::Turtle& t,
                BSTNode<T> *r,
                int s, 
                F fn) {
    if(!r)return;
    int saveX = t.xcor(), saveY = t.ycor();
    t.write(fn(r->key), 
            {"default"}, {"brown"}, 2);
    t.pencolor({"purple"}); 
    t.width(1);
    t.goTo(t.xcor()-s,t.ycor() - 50);
    drawTree(t, r->left, s/2, fn);
    t.goTo(t.xcor() + s, t.ycor() + 50);
    t.goTo(t.xcor() + s, t.ycor() - 50);
    drawTree(t, r->right, s/2, fn);
    t.goTo(saveX, saveY);
  }
  void inorder(BSTNode<T> *p) {
    if(!p) return;
    inorder(p->left);
    visit(p);
    inorder(p->right);
  }
  void preorder(BSTNode<T> *p) {
    if(!p) return;
    visit(p);
    preorder(p->left);
    preorder(p->right);
  }
  void postorder(BSTNode<T> *p) {
    if(!p) return;
    postorder(p->left);
    postorder(p->right);
    visit(p);
  }
  void visit(BSTNode<T> *n) {
    cout << n->key << " ";
  }
public:
  BST() {
    root = 0;
  }
  void print() {
    printTree(root, 0);
  }
  template<typename F>
  void draw(cturtle::Turtle& t, F fn) {
    t.width(1);t.pencolor({"purple"});
    t.right(90);t.penup();t.bk(200);
    t.pendown();t.left(90);
    drawTree(t, root, 128, fn);
  }
  void insert(T c) {
    BSTNode<T> *p = root, *prev = 0;
    while(p) {
      prev = p;
      if(c < p->key) p = p->left;
      else           p = p->right; 
    }
    if(root == 0) 
      root = new BSTNode<T>(c);
    else if(c < prev->key) 
      prev->left  = new BSTNode<T>(c); 
    else                   
      prev->right = new BSTNode<T>(c); 
  }
  void inorder() {
    inorder(root);
  }
  void preorder() {
    preorder(root);
  }
  void postorder() {
    postorder(root);
  }
};

int main() {
  int arr[]{13,10,25,2,12,20,31,29};
  BST<int> bst;
  for(int i = 0; 
      i < sizeof(arr)/sizeof(int); 
      i++) {
    int n = arr[i];
    cout << n << ' ';
    bst.insert(n);
  }
  cout << "\n\n";
  bst.print();

  cout << endl;
  cout << "  inorder: "; bst.inorder();
  cout << endl;
  
  cturtle::TurtleScreen ts;
  cturtle::Turtle turtle{ts};
  turtle.speed(1);
  auto fn = [](int i){return to_string(i);};
  bst.draw(turtle, fn); 
  ts.exitonclick();
}


    

To get rid of this warning msg on my mac:

ld: warning: dylib (/usr/local/lib/libX11.dylib) was built for newer macOS version (12.0) than being linked (11.3)

I run

export MACOSX_DEPLOYMENT_TARGET=12.0