二叉搜索樹的節(jié)點(diǎn)刪除

BST示例代碼如下:

#include<iostream>
using namespace std;
class Node {
public:
    int data;
    Node *lchild, *rchild, *father;
    Node(int _data, Node *_father = NULL) {
        data = _data;
        lchild = NULL;
        rchild = NULL;
        father = _father;
    }
    ~Node() {
        if (lchild != NULL) {
            delete lchild;
        }
        if (rchild != NULL) {
            delete rchild;
        }
    }
    void insert(int value) {
        if (value == data) {
            return;
        } else if (value > data) {
            if (rchild == NULL) {
                rchild = new Node(value, this);
            } else {
                rchild->insert(value);
            }
        } else {
            if (lchild == NULL) {
                lchild = new Node(value, this);
            } else {
                lchild->insert(value);
            }
        }
    }
    Node* search(int value) {
        if (data == value) {
            return this;
        } else if (value > data) {
            if (rchild == NULL) {
                return NULL;
            } else {
                return rchild->search(value);
            }
        } else {
            if (lchild == NULL) {
                return NULL;
            } else {
                return lchild->search(value);
            }
        }
    }
    Node* predecessor() {
        Node *temp = lchild;
        while (temp != NULL && temp->rchild != NULL) {
            temp = temp->rchild;
        }
        return temp;
    }
    Node* successor() {
        Node *temp = rchild;
        while (temp != NULL && temp->lchild != NULL) {
            temp = temp->lchild;
        }
        return temp;
    }

};
class BinaryTree {
private:
    Node *root;
public:
    BinaryTree() {
        root = NULL;
    }
    ~BinaryTree() {
        if (root != NULL) {
            delete root;
        }
    }
    void insert(int value) {
        if (root == NULL) {
            root = new Node(value);
        } else {
            root->insert(value);
        }
    }
    bool find(int value) {
        if (root->search(value) == NULL) {
            return false;
        } else {
           return true;
        }
    }
};
int main() {
    BinaryTree binarytree;
    int arr[10] = { 8, 9, 10, 3, 2, 1, 6, 4, 7, 5 };
    for (int i = 0; i < 10; i++) {
        binarytree.insert(arr[i]);
    }
    int value;
    cin >> value;
    if (binarytree.find(value)) {
        cout << "search success!" << endl;
    } else {
        cout << "search failed!" << endl;
    }
    return 0;
}


BST的元素刪除

BST節(jié)點(diǎn)的前驅(qū)與后繼搜索

某個BST節(jié)點(diǎn)的前驅(qū)汇陆,即為值比它小的最大的一個節(jié)點(diǎn)——進(jìn)入該節(jié)點(diǎn)的左子樹,然后不斷搜索左子樹的右孩子看尼,找到最后的節(jié)點(diǎn)即可

Node* predecessor(){
    Node* temp=lchild;
    while(temp!=NULL&&temp->lchild!=NULL){
        temp=temp->lchild;
    }
    return temp;
}

后繼也是一樣兆览,完全相反即可匿醒,此處略


刪除度數(shù)為0或者1的節(jié)點(diǎn)

對于一個非空的節(jié)點(diǎn),首先檢查它是否有左孩子或者右孩子——因?yàn)樵摴?jié)點(diǎn)度數(shù)為0或者1梯码,所以最多只能有一個孩子
對于節(jié)點(diǎn)delete_node的孩子temp,首先孩子的父親設(shè)置為delete_node的父親鳄抒,然后斷開其與delete_node的聯(lián)系
接下來判斷delete_node是其父節(jié)點(diǎn)的左孩子還是右孩子,確認(rèn)之后把temp換上
最后直接刪除delete_node
代碼如下:

void remove_node(Node* delete_node){ //delete_node的度為0或者1
        Node* temp=NULL;
        if(delete_node->lchild!=NULL){
            temp=delete_node->lchild;
            temp->father=delete_node->father;
            delete_node->lchild=NULL;
        }
        if(delete_node->rchild!=NULL){
            temp=delete_node->rchild;
            temp->father=delete_node->father;
            delete_node->rchild=NULL;
        }
        if(delete_node->father->lchild==delete_node){
            delete_node->father->lchild=temp;
        }
        else{
            delete_node->father->rchild=temp;
        }
        delete delete_node;
    }

刪除度數(shù)為2的節(jié)點(diǎn)

首先找到待刪除的節(jié)點(diǎn)
如果節(jié)點(diǎn)的左孩子存在耐朴,就把delete_node設(shè)置為節(jié)點(diǎn)的前驅(qū)
右孩子存在則設(shè)定為后繼
都不存在則設(shè)定為節(jié)點(diǎn)自身(此時待刪除的節(jié)點(diǎn)為葉子節(jié)點(diǎn))
把delete_node的data值賦給原本待刪除的節(jié)點(diǎn)——相當(dāng)于將待刪除的節(jié)點(diǎn)與delete_node調(diào)換
最后直接刪除delete_node

bool delete_tree(int value){
    Node *delete_node,*current_node;
    current_node=search(value);
    if(current_node==NULL){
          return false;
    }
    if(current_node->lchild!=NULL){
        delete_node=current_node->predecessor();
    }
    else if(current_node->rchild!=NULL){
        delete_node=current_node->successor();
    }
    else{
        delete_node=current_node;
    }
    current_node->data=delete_node->data;
    remove_node(delete_node);
    return true;
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末疤祭,一起剝皮案震驚了整個濱河市侨核,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌械荷,老刑警劉巖吨瞎,帶你破解...
    沈念sama閱讀 222,464評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件痹兜,死亡現(xiàn)場離奇詭異,居然都是意外死亡颤诀,警方通過查閱死者的電腦和手機(jī)字旭,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,033評論 3 399
  • 文/潘曉璐 我一進(jìn)店門崖叫,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人心傀,你說我怎么就攤上這事屈暗≈校” “怎么了?”我有些...
    開封第一講書人閱讀 169,078評論 0 362
  • 文/不壞的土叔 我叫張陵宰翅,是天一觀的道長。 經(jīng)常有香客問我堕油,道長潘飘,這世上最難降的妖魔是什么掉缺? 我笑而不...
    開封第一講書人閱讀 59,979評論 1 299
  • 正文 為了忘掉前任,我火速辦了婚禮眶明,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘搜囱。我一直安慰自己丑瞧,他們只是感情好柑土,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,001評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著绊汹,像睡著了一般稽屏。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上西乖,一...
    開封第一講書人閱讀 52,584評論 1 312
  • 那天狐榔,我揣著相機(jī)與錄音,去河邊找鬼获雕。 笑死薄腻,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的届案。 我是一名探鬼主播庵楷,決...
    沈念sama閱讀 41,085評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼楣颠!你這毒婦竟也來了尽纽?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,023評論 0 277
  • 序言:老撾萬榮一對情侶失蹤球碉,失蹤者是張志新(化名)和其女友劉穎蜓斧,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體睁冬,經(jīng)...
    沈念sama閱讀 46,555評論 1 319
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,626評論 3 342
  • 正文 我和宋清朗相戀三年看疙,在試婚紗的時候發(fā)現(xiàn)自己被綠了豆拨。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,769評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡能庆,死狀恐怖施禾,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情搁胆,我是刑警寧澤弥搞,帶...
    沈念sama閱讀 36,439評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站渠旁,受9級特大地震影響攀例,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜顾腊,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,115評論 3 335
  • 文/蒙蒙 一粤铭、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧杂靶,春花似錦梆惯、人聲如沸酱鸭。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,601評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽凹髓。三九已至,卻和暖如春怯屉,著一層夾襖步出監(jiān)牢的瞬間蔚舀,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,702評論 1 274
  • 我被黑心中介騙來泰國打工蚀之, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留蝗敢,地道東北人足删。 一個月前我還...
    沈念sama閱讀 49,191評論 3 378
  • 正文 我出身青樓,卻偏偏與公主長得像讶泰,于是被迫代替她去往敵國和親拂到。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,781評論 2 361

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