BTreeの判定

何かよいインタビュー用の問題はないかリサーチしていたところ，ツリー構造のデータが二分木であるかどうか判定するコードを書け，というのが結構あることがわかった．

確かに基礎を見るにはよい問いかもしれない．
深さ優先ではこんな感じだろうか．

#include <iostream>
#include <string>
using namespace std;

typedef struct Node_Struct {
 int value;
 struct Node_Struct* l;
 struct Node_Struct* r;
} Node;

Node * add(Node* base, int value) {

 if (base == NULL) {
  cout << "adding " << value << " to this node" << endl;
  base = new Node;
  base->l = base->r = NULL;
  base->value = value;
 }
 else if (base->value > value) {
  cout << base->value << ">" << value << ".. L" << endl;
  base->l = add(base->l,value);
 }
 else {
  cout << base->value << "<" << value << ".. R" << endl;
  base->r = add( base->r, value);
 }
 return base;

}

void dump(const Node* n) {
 cout << "{" << "value:" << n->value << "}" << endl;
}

void traverse_r( Node* n ) {

 if (n == NULL)
  return;

 if (n->l != NULL)
  traverse_r(n->l);
 dump(n);
 if (n->r != NULL)
  traverse_r(n->r);

 
}


Node* build_btree( Node* n) {

 n = add(n, 15);
 n = add(n, 30);
 n = add(n, 48);
 n = add(n, 10);
 n = add(n, 15);
 n = add(n, 72);
 n = add(n, 60);
 n = add(n, 66);
 n = add(n, 26);
 n = add(n, 55);
 return n;

}

bool is_btree_d(Node *n, bool decision) {
 
 if (n == NULL || decision == false)
  return decision;
 if (n->l != NULL && n->r != NULL) {
  cout << n->l->value << ":" << n->r->value << endl;
  decision = n->l->value < n->r->value ? true : false;
 }

 cout << "movin to l" << endl;
 decision = is_btree_d(n->l, decision);
 cout << "moving to r" << endl;
 decision = is_btree_d(n->r, decision);
 return decision;
 
}

int main() {

 Node* n = NULL;
 n = build_btree(n);
 traverse_r( n );
 cout << "is this btree valid? - " << is_btree_d(n, true) << endl;

 return 0;
}