二分順序木を使ったソート

二分順序木を扱うコードをつくってみました。
二分木に対して、右の子の値 >= 親の値、左の子の値 < 親の値として順序木を生成し、
通りがけ走査をすることで値のソーティングができます。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAX 100

//ノードの構造体
typedef struct binaly_tree{
  int id;
  struct binaly_tree *left;
  struct binaly_tree *right;
}node;

//根の宣言
node root;

//根に枝を追加していく
void addNode(node *p,int id)
{
  if(p->id <= id){
    if(p->right == NULL){
      node *new = (node*)malloc(sizeof(struct binaly_tree));
      new->id = id;
      new->left = NULL;
      new->right = NULL;
      p->right = new;
    }else
      addNode(p->right,id);
  }else
    if(p->left == NULL){
      node *new = (node*)malloc(sizeof(struct binaly_tree));
      new->id = id;
      new->left =NULL;
      new->right = NULL;
      p->left = new;
    }else
      addNode(p->left,id);
}

//通りがけ走査
void torigake(node *p)
{
  static int depth=0;
  depth++;
  if(p->left != NULL)
    torigake(p->left);
  depth--;
  printf("depth :\t%d\t%d\n",depth,p->id);
  depth++;
  if(p->right != NULL)
    torigake(p->right);
  depth--;
}

int main()
{
  int n,i;
  srand((unsigned)time(NULL));

  //初期化
  root.id = rand() % MAX;
  root.right = NULL;
  root.left = NULL;

  for(i=0;i<MAX;i++)
    addNode(&root,rand() % MAX);
  torigake(&root);
  return 0;
}

実行結果

depth : 3       1
depth : 2       3
depth : 5       4
depth : 4       5
depth : 5       5
depth : 6       5
depth : 3       6
depth : 5       6
...
depth : 7       97
depth : 6       99
depth : 7       99

通りがかり走査について

void torigake(node *p)
{
  static int depth=0;
  depth++;
  if(p->left != NULL)
    torigake(p->left);
  depth--;
  printf("depth :\t%d\t%d\n",depth,p->id);
  depth++;
  if(p->right != NULL)
    torigake(p->right);
  depth--;
}

再帰の深さを表示するためにstatic変数depthを加算しているが、必要なところだけを残すと、

void torigake(node *p)
{
  if(p->left != NULL)
    torigake(p->left);
  printf("depth :\t%d\t%d\n",depth,p->id);
  if(p->right != NULL)
    torigake(p->right);
}