排序二叉樹，搜尋二叉樹，查找二叉樹都是一個意思，隻是叫法不同而已。下面的文章中我們統稱為排序二叉樹。本文主要是針對高中資訊學，是以其中不涉及到指針，所有需要用指針的地方都直接使用數組進行模拟。
排序二叉樹定義：
（1）若左子樹不空，則左子樹上所有結點的值均小于或等于它的根結點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大于或等于它的根結點的值；
（3）左、右子樹也分别為二叉排序樹；
從定義中我們可以知道：左<根<右；是以使用中序周遊排序二叉樹一定是一個遞增序列。
節點定義：
struct node{
int data;//節點值的類型，以整型為例
int left;//左兒子數組下标
int right;//右兒子數組下标
int father;//該節點的父節點數組下标
int freq;//該節點的值出現的頻率
};
node arr[105]={0};//定義一個大小為105的數組。可以裝105個元素，
int root=1;//根節點對應的數組下标
建樹：
排序二叉樹的建立并不難，因為建樹的過程就是将值一個一個插入到樹中去的過程。例如這裡使用随機函數生成100個随機值，然後依次插入到排序二叉樹中就完成了建樹。
srand(unsigned(time(NULL)));
int x;
for(int i=1;i<101;i++){
arr[i].data=rand()%10000;
insert(root,i);//調用插入函數
}
插入元素：
向二叉樹中插入元素需要通過将待插入的值和某個節點對比，決定是插入到這個節點的左邊還是右邊。例如要想下面的二叉樹中插入21，首先21和3相比，比3大則一定在3的右邊，然後21和8比，又大；則到8的右邊，而8的右邊沒有，那麼将21插入作為8的右兒子
實作代碼：
void insert(int index,int i){//i為要插入的值的下标,index為插入過程中與arr[i]相比的值的數組下标
int y=arr[index].data;
int x=arr[i].data;
if(x==y){//如果找到了一個相同的，就将頻率加1
arr[index].freq++;
return ;
}
if(arr[index].left!=0&&x<y)//如果x<y并且y有左兒子，就到左邊去插入
insert(arr[index].left,i);
else if(arr[index].right!=0&&x>y)//如果x<y并且y有右兒子，就到右邊去插入
insert(arr[index].right,i);
else if(arr[index].left==0&&x<y){//如果x<y并且y沒有左兒子，就插入到y的左邊
arr[index].left=i;
arr[index].freq=1;
arr[i].father=index;
return;
}
else if(arr[index].right==0&&x>y){//如果x>y并且y沒有右兒子，就插入到y的右邊
arr[index].right=i;
arr[i].father=index;
arr[index].freq=1;
return;
}
}
查找元素：
查找元素很容易，隻有兩種結果：找到和找不到。找到就是其中某個值和要查找的值相等，找不到就是把樹都走完了，但是還是沒有相等的。查找和插入很相似，同樣是通過比較決定到左還是右邊去查找。
比如：查找7
1.和12相比小------左
2.和6相比大--------右
3.和8相比小--------左
4.和7相比等--------找到
若是在第3步，8不存在左子樹，那麼傳回找不到
實作代碼：
int find(int r,int da){//da表示要查找的資料，r表示一路比較的資料的下标
int dar=arr[r].data;
int dl=arr[r].left;
int dr=arr[r].right;
if(da==dar)//相等，傳回資料下表
return r;
else if(da<dar&&dl)//小于，且資料存在左子樹，到左邊去找
find(dl,da);
else if(da>dar&&dr)//大于，且資料存在右子樹，到右邊去找
find(dr,da);
else{//否則傳回-1表示沒有找到
//cout<<"not find!"<<endl;
return -1;
}
}
删除元素：
删除元素是排序二叉樹中最難的操作，比較繁雜。因為删除一個元素有幾種情況：
1.該元素是葉子結點
2.該元素隻有左子樹
3.該元素隻有右子樹
4.該元素左右子樹都存在
這還沒完，我們删除的時候還要判斷我們要删除的元素到底是他的父元素的左兒子還是右兒子。以及要判斷删除的節點是不是根節點。
其實對于前三種情況都簡單；關鍵是第4種兩個子樹都存在的情況，這裡删除操作有幾種方法：
1.找到右子樹中最小的值min，然後用min替換要删除的元素，最後删掉min。
2.找到左子樹中最大值max，然後用max替換要删除的元素，最後删掉max
3.找到左子樹中的最大值max，然後将右子樹作為max的右子樹，最後将元素删除并讓該元素的左兒子上位。
4.和3一樣，找到右子樹min，然後接上去。。。。。。
這裡可以看到這裡的四種方式前兩種操作起來要容易一些，可以省一些事。
例如我要删除圖中的6
1.用7覆寫6，然後删除7
2.5覆寫6，删除5
3.将3作為12的左兒子，然後把6的右兒子連到5的右邊
代碼實作
void del(int index,int num){
int x=find(index,num);
if(x<0)return;
int l=arr[x].left;
int r=arr[x].right;
int f=arr[x].father;
if(l!=0&&r!=0){
int temp=r;
while(arr[temp].left)temp=arr[temp].left;//找到右子樹中的最小節點
arr[x].data=arr[temp].data;//将最小節點和目前需要删除的節點進行替換
arr[x].freq=arr[temp].freq;
if(temp!=r)//temp!=r則去掉最小節點的父節點的left
arr[arr[temp].father].left=0;
else{//temp==r表示右子節點不存在左樹，則直接用右子節點的right替換待删除的right
arr[x].right=arr[temp].right;
arr[arr[x].right].father=x;
}
arr[temp].father=0;
}
else{
int temp=0;
if(l==0)
temp=r;
else
temp=l;
if(arr[f].left==x)
arr[f].left=temp;
else
arr[f].right=temp;
arr[x].father=0;
if(temp)
arr[temp].father=f;
if(x==root)
root=temp;
}
}
運作截圖：使用中序周遊後是一個上升序列