matlab编程实现二进制树搜索,数据结构: 二进制搜索树（用C语言实现）
有關(guān)二叉樹的基本知識(shí)，請參閱我的博客之一: 二叉樹的鏈?zhǔn)酱鎯?chǔ)
說明:
二進(jìn)制排序樹是具有以下屬性的空樹或二進(jìn)制樹:
1. 如果左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值均小于其根節(jié)點(diǎn)的值;
2. 如果右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于其根節(jié)點(diǎn)的值；
3. 左右子樹也是二叉排序樹
說明:
通過重復(fù)將節(jié)點(diǎn)插入二叉樹來構(gòu)造二叉樹！
如果二叉樹為空樹二叉排序樹的建立c，則將元素插入為根節(jié)點(diǎn).
如果根節(jié)點(diǎn)的鍵值等于key，則插入失敗；
如果鍵小于根節(jié)點(diǎn)的鍵值二叉排序樹的建立c，它將被插入到根的左子樹中；否則，它將被插入到根的右子樹中
新插入的節(jié)點(diǎn)必須是葉節(jié)點(diǎn)！
代碼分析:
void InsertBST(BiStree &Tree,ElemType e)
{
BiStree T =Tree; //定義執(zhí)行副本，！
BiStree father =NULL; //定義
while (T&&T->data.key!=e.key)
{
father=T;
if(e.key>T->data.key)
T=T->Rchild;
else
T=T->Lchild;
}
if(T) //跳出循環(huán)的只有兩種情況，要么就是T不存在，要么就是找到了對應(yīng)元素！T 存在說明，只能是對應(yīng)元素也存在，那我我們就不用插入了
return;
BiSnode *s = (BiSnode*)malloc(sizeof(BiSnode));//能到這里，說明節(jié)點(diǎn)不存在，新建一個(gè)節(jié)點(diǎn)，并初始化！
s->data=e;
s->Rchild=s->Lchild=NULL;
if(father==NULL) //如果farther不存在，那說明就是沒有執(zhí)行While語句，也即是樹是空的，因?yàn)橐坏﹫?zhí)行，就不會(huì)為NULL！
Tree=s;
else if(e.key>father->data.key) //到這里說明Farther存在,那么剩下的就是往farther左右節(jié)點(diǎn)插入元素了
father->Rchild=s;
else
father->Lchild=s;
}
說明:
刪除操作的基礎(chǔ)是查找元素. 首先，您需要找到要?jiǎng)h除的元素. 如果找到它，將其刪除. 如果找不到，則無需刪除它.
找到一些代碼:
void DelBST(BiStree &Tree,char key)
{
if(!Tree) //如果節(jié)點(diǎn)為空節(jié)點(diǎn)，說明要?jiǎng)h除的元素不可能存在，所以返回就好！
return;
else //下面是節(jié)點(diǎn)存在的分情況判斷：
{
if(Tree->data.key==key) //如果找到了要?jiǎng)h除的節(jié)點(diǎn)！
{
deleteNode(Tree); //刪除該節(jié)點(diǎn)
}
else if(Tree->data.key
DelBST(Tree->Rchild,key);
else
DelBST(Tree->Lchild,key);//如果要?jiǎng)h除的節(jié)點(diǎn)小于該節(jié)點(diǎn)，則往該節(jié)點(diǎn)的左子樹方向進(jìn)行查找
}
}
現(xiàn)在我們已經(jīng)找到了元素，要?jiǎng)h除它，我們必須實(shí)現(xiàn)deleteNode(Tree);方法！
但是，刪除元素的操作有很多情況，我們必須分別處理它們:
★要?jiǎng)h除的節(jié)點(diǎn)* p是葉節(jié)點(diǎn)
★要?jiǎng)h除的節(jié)點(diǎn)* p只是一個(gè)非空子樹
★要?jiǎng)h除的節(jié)點(diǎn)* p具有兩個(gè)非空子樹
如何找到直接的前任: 找到要?jiǎng)h除的節(jié)點(diǎn)的第一個(gè)左子樹，然后繼續(xù)向右走！
刪除代碼如下:
void deleteNode(BiStree &p)
{
if(!p->Rchild) //對第一種及第二種情況的處理
{
BiSnode * q =p;
p=p->Lchild;
free(q);
}
else if(!p->Lchild) //對第一種及第二種情況的處理
{
BiSnode * q =p;
p=p->Rchild;
free(q);
} else
{
BiSnode * q =p;
BiSnode * s =p->Lchild;
while (s->Rchild)
{
q=s;
s=s->Rchild;
}
//s指向被刪節(jié)點(diǎn)p的前驅(qū)
p->data=s->data;
if(q!=p) //詳見下兩圖
q->Rchild=s->Lchild; //左圖
else
q->Lchild=s->Lchild; //右圖
free(s);
}
}
該代碼不會(huì)被降級，非常簡單！
查找鍵值為K的記錄:
如果二進(jìn)制排序樹是空樹，則搜索失敗并返回；
如果根節(jié)點(diǎn)的鍵值等于key，則搜索成功并返回；
如果根節(jié)點(diǎn)的鍵值大于key，則繼續(xù)在根的左子樹上搜索；否則，繼續(xù)在根的右子樹上搜索
本文來自電腦雜談，轉(zhuǎn)載請注明本文網(wǎng)址：
http://www.pc-fly.com/a/jisuanjixue/article-177261-1.html
總結(jié)
以上是生活随笔為你收集整理的matlab编程实现二进制树搜索,数据结构: 二进制搜索树（用C语言实现）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 光华科技光刻胶_光刻胶领衔国产替代，20
- 下一篇： stm32f103移植到f0_STM32