同學去阿裡面試的時候，要求寫出代碼：
現在有一棵二叉排序樹，每個節點保存一個int類型的值，刪除值為10以下的節點（樹中可能不含值為10的節點），說一下思路，寫一下算法。
算了原來錯誤的思路就不拿出來誤導大家了，只能說想簡單了，花了幾天空閒的時間思考這個問題，終於把代碼寫出來了，雖然琢磨了一段時間，但是終究還是寫出來了。
二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm
【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm
在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm
【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm
二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm
經過測試數據或者自己畫圖，感覺有這麼幾個難點把
1.如果數據是這樣：6,5,7,8,15，就是先開始根結點的值小於10，後來右子樹中=存在大於10的結點，由於需要釋放小於10的結點，就需要重新調整根結點
2.如果數據是這樣：6,5,7,8,15,14,9,8,13,11,10，就是先開始小於10，然後右子樹出現了大於了10，結果峰回路轉左子樹中又有小於10的結點，其實這組數據基本就包含了核心代碼的思想
代碼思想：如果當前結點小於10的話，就循環查找右子樹，直到找到第一個大於10的結點p，然後調整樹結構，接著循環查找p的左子樹，直到找到又出現第一個小於10的結點，然後遞歸查找右子樹和左子樹整個過程，直到沒有大於10的結點為止
代碼如下，其中題目要求為刪除的值為10，當然更通用的是刪除值為val以下的結點(如果結點值等於val，也會被刪除)，另外在創建樹的時候由於為了方便測試代碼，所以隨機生成，但是對於有相同值，會自動忽略，也就是樹中的所有結點值都是唯一的：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct biTree{
struct biTree*lchild,*rchild;
int data;
};
struct biTree* createBST(struct biTree *root,int val){
if(root==NULL){
root=(struct biTree*)malloc(sizeof(struct biTree));
root->data=val;
root->lchild=root->rchild=NULL;
return root;
}
if(val<root->data) root->lchild=createBST(root->lchild,val);
else if(val>root->data) root->rchild=createBST(root->rchild,val);
return root;
}
void inOrder(struct biTree*root){
if(root==NULL) return ;
inOrder(root->lchild);
printf("%d ",root->data);
inOrder(root->rchild);
}
int delVal(struct biTree **root,int val){
if(root==NULL) return 0;
struct biTree *p=*root,*pre=*root;
struct biTree *q=(struct biTree*)malloc(sizeof(struct biTree));
while(1){
int value=(*root)->data;
while(p&&p->data<=val){
pre=p;
p=p->rchild;
free(pre);
}
if(value<val) *root=p; //其實只會調整一次根結點
else q->lchild=p;
while(p&&p->data>val){
pre=p;
p=p->lchild;
}
if(p==NULL) break;
q=pre;
}
return 1;
}
int main(){
int i;
while(1){
int a[30];
struct biTree *root=NULL;
unsigned int seed;
seed = time(0);
srand(seed);
for(i=0;i<10;i++){
a[i]=rand()%100+1;
}
for(i=0;i<10;i++){
printf("%d ",a[i]);
}
printf("\n");
for(i=0;i<9;i++) root=createBST(root,a[i]);
inOrder(root);
printf("\n");
int val;
scanf("%d",&val); //輸入某個值，小於這個值的所有結點都會被刪除
delVal(&root,val);
inOrder(root);
printf("\n\n");
root=NULL;
}
return 0;
}
