二叉搜索樹操作集

【二叉搜索樹】:一棵樹可以為空,如果不空亮隙,必須滿足以下性質(zhì):
非空左子樹的所有的鍵值小于其根節(jié)點的鍵值
非空右子樹的所有的鍵值大于其根節(jié)點的鍵值
左途凫、右子樹都是二叉搜索樹

二叉搜索樹
/* 搜索二叉樹操作集 */

#include<stdio.h>
#include<stdlib.h>

#define SIZE 10
typedef int ElementType;
typedef struct TNode *BinTree;
typedef BinTree Position;
typedef struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

BinTree Insert(ElementType X,BinTree bst);//二叉搜索樹建立、插入
void PreOrderTraversal(BinTree bst); //輸出二叉樹
BinTree FindMinNode(BinTree bst); //返回最小元素節(jié)點的指針
BinTree FindMaxNode(BinTree bst); //返回最大元素的節(jié)點指針
BinTree FindX(ElementType X, BinTree bst); //查找元素X并返回其節(jié)點指針
BinTree DeleteX(ElementType X, BinTree bst);//刪除指定節(jié)點X并返回其指針

int main()
{
    int x=1;
    BinTree BST = NULL;
    BinTree MinNodeOfBST=NULL;
    BinTree MaxNodeOfBST=NULL;
    BinTree findNodeX=NULL;

    int arrary[SIZE] = { 5,2,1,3,6,7,8,9,4,0 };
    for (int i = 0; i < SIZE; i++) {
        BST=Insert(arrary[i],BST);
    }

    PreOrderTraversal(BST);

    putchar('\n');
    MinNodeOfBST=FindMinNode(BST);
    MaxNodeOfBST=FindMaxNode(BST);
    printf("Min= %d  Max= %d\n", MinNodeOfBST->Data,MaxNodeOfBST->Data);

    findNodeX=FindX(x,BST);
    printf("%d\n", findNodeX->Data);

    BST=DeleteX(1,BST);
    PreOrderTraversal(BST);
    putchar('\n');
    BST = DeleteX(1, BST);

    system("pause");

    return 0;
}

/* 建立二叉樹溢吻、插入節(jié)點(只能插在葉節(jié)點) */
BinTree Insert(ElementType X,BinTree bst)
{
    if(!bst){
        /* 如果樹為空维费,生成并返回一個節(jié)點的二叉樹 */
        bst=(BinTree)malloc(sizeof(struct TNode));
        bst->Data=X;
        bst->Left=bst->Right=NULL;
    }else{
        /* 找到要插入節(jié)點的位置 */
        if(X<bst->Data){
            bst->Left=Insert(X,bst->Left); //遞歸插入左子樹
        }else if(X>bst->Data){
            bst->Right=Insert(X,bst->Right);//遞歸插入右子樹
        }else;
    }
    return bst;
}

/* 最小元素一定在樹的最左端分支的端節(jié)點 */
BinTree FindMinNode(BinTree bst)
{
    if(!bst)    return NULL;
    else if(!bst->Left) return bst;
    else    return FindMinNode(bst->Left);
}

/* 最大元素一定在樹的最右端分支的端節(jié)點 */
BinTree FindMaxNode(BinTree bst)
{
    if(!bst)    return NULL;
    else if(!bst->Right)    return bst;
    else return FindMaxNode(bst->Right);
    /*
        迭代實現(xiàn)
        if(bst){
            while(bst->Right)
                bst=bst->Right;
        }
        return bst;
    */
}

/* 
    查找元素X,并返回其指針
    x小于根節(jié)點鍵值促王,左子樹搜索
    x大于根節(jié)點鍵值犀盟,右子樹搜索
    結(jié)果相等,搜索完成蝇狼,返回指向此節(jié)點的指針 
 */
BinTree FindX(ElementType X, BinTree bst)
{
    if(bst){
        if(X>bst->Data) //位于右子樹
            return FindX(X,bst->Right);
        else if(X<bst->Data)    //位于左子樹
            return FindX(X,bst->Left);
        else
            return bst;
    }
}

/* 
    二叉搜索樹刪除指定元素阅畴,并返回二叉樹指針 
    刪除葉節(jié)點:直接刪除,并修改其父節(jié)點指針為NULL
    刪除節(jié)點只有一個孩子節(jié)點:
    將其父節(jié)點的指針指向要刪除的節(jié)點的孩子節(jié)點
    刪除節(jié)點有兩個孩子節(jié)點:
    用另一個節(jié)點替代被刪除節(jié)點(右子樹的最小元素或者左子樹的最大元素)
*/
BinTree DeleteX(ElementType X,BinTree bst)
{
    BinTree temp;
    if(!bst)    printf("Not Find X\n");
    else if(X<bst->Data)    //位于左子樹
        bst->Left=DeleteX(X,bst->Left);
    else if(X>bst->Data)    //位于右子樹
        bst->Right=DeleteX(X,bst->Right);
    else    //要刪除的點
        if(bst->Left&&bst->Right) { //左右節(jié)點均存在
            temp=FindMaxNode(bst);
            bst->Data=temp->Data;
            bst->Right=DeleteX(bst->Data,bst->Right);
        }else{      //小于等于一個節(jié)點
            temp=bst;
            if(!bst->Left)
                bst=bst->Right;
            else if(!bst->Right)
                bst=bst->Left;
            free(temp);
        }
        return bst;
}

/* 輸出二叉樹 */
void PreOrderTraversal(BinTree bst)
{
    if(bst){
        printf("%d ", bst->Data);
        PreOrderTraversal(bst->Left);
        PreOrderTraversal(bst->Right);
    }
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末迅耘,一起剝皮案震驚了整個濱河市贱枣,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌颤专,老刑警劉巖纽哥,帶你破解...
    沈念sama閱讀 222,590評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異栖秕,居然都是意外死亡春塌,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,157評論 3 399
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來摔笤,“玉大人,你說我怎么就攤上這事垦写÷朗溃” “怎么了?”我有些...
    開封第一講書人閱讀 169,301評論 0 362
  • 文/不壞的土叔 我叫張陵梯投,是天一觀的道長命辖。 經(jīng)常有香客問我,道長分蓖,這世上最難降的妖魔是什么尔艇? 我笑而不...
    開封第一講書人閱讀 60,078評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮么鹤,結(jié)果婚禮上终娃,老公的妹妹穿的比我還像新娘。我一直安慰自己蒸甜,他們只是感情好棠耕,可當我...
    茶點故事閱讀 69,082評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著柠新,像睡著了一般窍荧。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上恨憎,一...
    開封第一講書人閱讀 52,682評論 1 312
  • 那天蕊退,我揣著相機與錄音,去河邊找鬼憔恳。 笑死瓤荔,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的喇嘱。 我是一名探鬼主播茉贡,決...
    沈念sama閱讀 41,155評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼者铜!你這毒婦竟也來了腔丧?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,098評論 0 277
  • 序言:老撾萬榮一對情侶失蹤作烟,失蹤者是張志新(化名)和其女友劉穎愉粤,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體拿撩,經(jīng)...
    沈念sama閱讀 46,638評論 1 319
  • 正文 獨居荒郊野嶺守林人離奇死亡衣厘,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,701評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片影暴。...
    茶點故事閱讀 40,852評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡错邦,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出型宙,到底是詐尸還是另有隱情撬呢,我是刑警寧澤,帶...
    沈念sama閱讀 36,520評論 5 351
  • 正文 年R本政府宣布妆兑,位于F島的核電站魂拦,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏搁嗓。R本人自食惡果不足惜芯勘,卻給世界環(huán)境...
    茶點故事閱讀 42,181評論 3 335
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望腺逛。 院中可真熱鬧荷愕,春花似錦、人聲如沸棍矛。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,674評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽茄靠。三九已至茂契,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間慨绳,已是汗流浹背掉冶。 一陣腳步聲響...
    開封第一講書人閱讀 33,788評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留脐雪,地道東北人厌小。 一個月前我還...
    沈念sama閱讀 49,279評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像战秋,于是被迫代替她去往敵國和親璧亚。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,851評論 2 361

推薦閱讀更多精彩內(nèi)容