二分木の実装とか

ノードを構造体で表す

typedef struct _node {
	int val;
	struct _node *lch;
	struct _node *rch;
} node;

赤色注意。まだ、typedefしていないので、こう書かなければ、エラー

挿入

//x：挿入する数字 p：検索するノード
node *insert(node *p, int x) {
	//ノードなし
	if(p == NULL) {
		node *q = new node;
		//新しいノードの設定 
		q->val = x;
		q->lch = q->rch = NULL;
		return q;
        //ノードが存在する
	} else {
		//xがそのノードより小さい→左に進め。
		if(x < p->val) {
			//さらに奥に進む。
			p->lch = insert(p->lch, x);
		//xがそのノードよりも大きい→右に進め
		} else if(x > p->val) {
                        //さらに奥に進む
			p->rch = insert(p->rch, x);
		}
                //x挿入後の根のノードの結果を返す。
		return p;
	}
	//同じ数字だった時はNULLを返す。
	return NULL;
}

どんどん奥に進んでいくと、子ノードを持たないか、一つだけしか子ノードを持たないノードにたどり着く。
そういうノードでももちろん、else判定されるので、左（か右、もしくはどちらの方向にしろ）指し示したところにいってもノードが存在しないということが起こりうる。
その時に、新しくノードを作って、道（木の枝）を伸ばしていく。というか、接着していく。ということをやって、ノードが挿入される。

検索

bool find(node *p, int x) {
	//進んでもノードが存在しなかった
	if(p == NULL) {
		return false;
	}
	//数がxのノード発見！！
	else if(x == p->val) {
		return true;

	//xが小さいので、左へ進む
	} else if(x < p->val) {
		return find(p->lch, x);

	//xが大きいので、右へ進む
	} else if(x > p->val) {
		return find(p->rch, x);
	}

	//なにか、予想外のxが放り込まれる
	return false;
}

こちらも、基本的には挿入と同じ。

削除
この図を参考に。