二分探索木構造について

Question

C言語で二分探索木を実装しました．
ここで内部道長を，木の内部節点のレベルの総和とします．また，根のレベルを0とします．このとき，以下のようなコードを書いたのですが，~~これはうまく実装できているでしょうか．~~結果が正しいものとはなりませんでした．1~10を昇順で入れたときには総和は45になると思うのですが42と表示されています．これは再帰のどこが原因で発生しているのでしょうか．
いくつかのファイルを用いて行っています．
実行した結果をコードの下に載せます．

#include <stdlib.h>
#include<stdio.h>
#include "Item.h"
typedef struct STnode* link;
struct STnode { 
Item item; link l, r; int N; 
};
static link head, z;
link NEW(Item item, link l, link r, int N){
 link x = malloc(sizeof *x); 
  x->item = item; x->l = l; x->r = r; x->N = N;
  return x;
}
void STinit(){ 
  head = (z = NEW(NULLitem, 0, 0, 0));
}
int STcount(void) {
 return head->N; 
}
Item searchR(link h, Key v){
 Key t = key(h->item);
  if (h == z) return NULLitem;
  if eq(v, t) return h->item;
  if less(v, t) return searchR(h->l, v);
  else return searchR(h->r, v);
}
Item STsearch(Key v) {
 return searchR(head, v);
} 
link insertR(link h, Item item){ 
Key v = key(item), t = key(h->item);
  if (h == z) return NEW(item, z, z, 1);
  if less(v, t) 
	   h->l = insertR(h->l, item);
  else h->r = insertR(h->r, item);
  (h->N)++; return h;
}
void STinsert(Item item){
 head = insertR(head, item); 
}
int ipathR(link h){
  if(h == NULL) return 0;
  else return 2 + ipathR(h->l) + ipathR(h->r);
}

int STipathlength(){ 
return ipathR(head); 
}

#include <stdio.h>
#include <stdlib.h>
#include "Item.h"
#include "ST.h"

int main(int argc, char *argv[])
{  int N, M, maxN = atoi(argv[1]), sw = atoi(argv[2]);
  Key v; Item item;
  STinit(maxN); srand(1);
  for (M = 0, N = 0; N < maxN; N++)
    {
      if (sw == 1) v = ITEMrand();
      else if (sw == 2) v = N+1;
      else if (ITEMscan(&v) == EOF) break;
      item = STsearch(v); if (item.key != NULLitem.key) continue;
      key(item) = v;
      STinsert(item); M++;
    }
  int INlength = STipathlength();
  printf("ipathlength:%d\n",INlength);
  return 0;
}

##実行結果
./ST 30 1
41 153 292 491 2995 3902 4827 5436 5705 6334 9961 11478 11942 12382 14604 15724 16827 17421 18467 18716 19169 19718 19895 23281 24464 26500 26962 28145 29358 32391
ipathlength:122

./STtest 10 2
1 2 3 4 5 6 7 8 9 10
ipathlength:42

##追記

int ipathR(link h){
  if(h == NULL) return 0;
  else {
    printf("%d %d\n",ipathR(h->l),ipathR(h->r));
    return 1 + ipathR(h->l) + ipathR(h->r);
  }
}

int STipathlength(){ return ipathR(head); }

関数の中を以下のようにしてどのような値で動いているのかを見たのですが結果が以下のようになってしまい，
0 0
がなぜこんなに多く表示されるのかわからないです．

(結果)
./STtest 2 2
0 0
0 0
1 1
0 0
0 0
0 0
1 3
0 0
0 0
0 0
1 1
0 0
0 0
ipathlength:5

Comments

[fana]

・意味不明．
「うまく実装」とは何か？　その完結すらしてなさそうなコード断片から他者に何を判断しろと要求しているのか？
・「実行した結果」とやらがあるのならば，そこから勝手に「うまいかどうか」を判断すればよろしいのでは？
（・あとこれは個人的意見だが，コードが汚すぎて見たくもない．）

[grape_ll]

こちらの説明がよくないようですね．申し訳ございません．
うまいというのは，結果が正しい=うまく実装できている，と勝手に定義していました．
includeしているものを提示しようか迷ったのですが，ただファイルが多くなって見づらくなるだけになるそうだと勝手に判断してしまいました．個人的には再帰のところさえ見れば，プログラミングに強い方なら本質が見抜けると思っていたので，この張り付けたファイルには他にもいろいろ書いていたのですが本題とは関係ないと思い省かせていただきました．
結果は出せているのですが，自分の確認だけでは安心には足らないと判断したので投稿させていただいてます．
コードの汚さについては，これから改善したいと思います．

[fana]

そもそも質問内容が何なのかわからなかった　→　質問内容が明確になったようなので，プログラミングに強い方であれば回答可能な状態になったのかもしれません．

[grape_ll]

ご指摘ありがとうございました。これからも質問する際には内容をできる限り明確にするようにしたいと思います．

Answer 1

int ipathR(link h,int p){
if(h == z) return 0;
else{
return p + ipathR(h->l,p+1) + ipathR(h->r,p+1);
}
}
このようにすることで出来ました．