數(shù)據(jù)結(jié)構(gòu)-二叉查找樹(查找,插入糖儡,刪除伐坏,遍歷)

一、什么是二叉查找樹

二叉查找樹是一顆空樹握联,或者是具有一下性質(zhì)的二叉樹:
1.若根結(jié)點的左子樹不為空桦沉,那么左子樹上所有結(jié)點的值都小于根節(jié)點的值
2.若根結(jié)點的右子樹不為空每瞒,那么右子樹上所有結(jié)點的值都小于根節(jié)點的值
3.根節(jié)點的左子樹和右子樹也是二叉查找樹

下圖就是一顆二叉查找樹,每個結(jié)點的值都大于他的左子樹的所有結(jié)點的值永部,每個結(jié)點的值都小于他的右子樹所有結(jié)點的值独泞。


圖一

下圖也是一個二叉查找樹,雖然他是一個斜樹苔埋,樹的高度等于結(jié)點的數(shù)量,但是他也符合二叉查找樹的定義(只是搜索的效率很低)蜒犯。


圖二

二组橄、二叉查找樹的作用

從名字就可以看出,我們構(gòu)造二叉查找樹的作用是高效地查找罚随、插入和刪除玉工。

2.1 查找

比如,我們在圖一所示的二叉查找樹中查找數(shù)字5是否存在淘菩,查找的步驟如下:
1遵班、5和結(jié)點④比較,5大于4潮改,下一步我們要搜索結(jié)點④的右子樹(根據(jù)二叉查找樹的定義狭郑,一個結(jié)點值小于他的右子樹上所有結(jié)點的值)
2、5和結(jié)點⑥比較汇在,5小于6翰萨,下一步我們要搜索結(jié)點⑥的左子樹
3、5等于結(jié)點5糕殉,查找成功

2.2 插入

我們依然用圖一作為例子亩鬼,這次我們要在圖一所示的二叉樹中插入一個7,步驟如下:
1阿蝶、7和根結(jié)點④比較雳锋,7大于4,下一步搜索右子樹
2羡洁、7和結(jié)點⑥比較玷过,7大于6,下一步搜索右子樹
3焚廊、7和結(jié)點⑧比較冶匹,7小于8,下一步搜索左子樹
4咆瘟、8的左子樹為空嚼隘,那么這里就是7應(yīng)該插入的位置,將7插入到8的左子樹中袒餐。
如下如所示


圖三-插入結(jié)點

2.3刪除結(jié)點

刪除結(jié)點比較復(fù)雜飞蛹,我們需要分為四種情況谤狡。
我們以下圖為例來分析這四種情況


圖四
2.3.1 待刪除的結(jié)點既沒有左子樹有沒有右子樹

用圖四作為例子,我們需要刪除結(jié)點9卧檐,步驟如下
1墓懂、我們首先要找到結(jié)點9的父節(jié)點8(如果要刪除的結(jié)點沒有父節(jié)點,也就是要刪除的結(jié)點就是根結(jié)點霉囚,那么直接將樹設(shè)置為空樹即可)捕仔。
2、我們將結(jié)點9從其父節(jié)點8的右子樹上刪除盈罐。


圖五
2.3.2 待刪除的結(jié)點只有左子樹

用圖四作為例子榜跌,我們要刪除結(jié)點15,它只有左子樹盅粪,刪除的步驟如下
1钓葫、找到待刪除的結(jié)點15
2、將結(jié)點15的左子結(jié)點的值12賦值給結(jié)點15
3票顾、將結(jié)點結(jié)點12的左子樹和右子樹分別設(shè)置為待刪除結(jié)點的左子樹和右子樹
如下圖所示:


圖六
2.3.3 待刪除的結(jié)點只有右子樹

用圖四作為例子础浮,我們要刪除結(jié)點5,和2.3.2類似奠骄,步驟如下
1豆同、找到待刪除的結(jié)點5
2、將結(jié)點5的右子結(jié)點的值8賦值給結(jié)點5
3戚揭、將結(jié)點結(jié)點8的左子樹和右子樹分別設(shè)置為待刪除結(jié)點的左子樹和右子樹

2.3.3 待刪除的結(jié)點有左子樹又有右子樹

首先我們應(yīng)該知道诱告,二叉查找樹中序遍歷時結(jié)點的值遞增的(大家可以自己想一下為什么)。
用圖四作為例子民晒,我們要刪除結(jié)點10精居,為了保持二叉查找樹的性質(zhì),我們需要找到中序遍歷中10的左邊一個結(jié)點或者右邊一個結(jié)點來替代10的位置潜必,這里我們選擇中序遍歷中10的左邊一個結(jié)點靴姿。刪除的步驟如下
1、首先找到待刪除的結(jié)點
2磁滚、找到中序遍歷中10的左邊的那個結(jié)點9和該節(jié)點的父節(jié)點8
3佛吓、刪除結(jié)點9
4、將結(jié)點10的值替換為9
如下圖所示


圖七

2.4 時間復(fù)雜度分析

當(dāng)二位查找樹是一顆完全二叉樹時垂攘,樹的高度是log(n) + 1维雇,那么查找,插入晒他,刪除的時間復(fù)雜度都是log(n)吱型。
但是如果二叉查找樹不平衡,更機端的情況下變?yōu)橐粋€斜樹陨仅,如圖二所示津滞,那么時間復(fù)雜度就會退化為O(n)铝侵。

三、代碼

這里我使用java來寫二叉查找樹的搜索触徐,插入咪鲜,刪除。其他語言思路一樣撞鹉。
我創(chuàng)建了一個類BinarySearchTree疟丙,類中有一個靜態(tài)內(nèi)部類TreeNode用來表示二叉樹的結(jié)點,類中有一個TreeNode類型成員變量head用來保存二叉查找樹的根節(jié)點鸟雏。
思路在第二章已經(jīng)說明隆敢,這里就不多解釋了。
大家多練練手崔慧,明白其中的原理即可。

package MyBinarySearchTree;

import java.util.Stack;


public class BinarySearchTree {
    /**
     * 在二叉搜索樹中搜索是否存在指定的結(jié)點穴墅,如果存在指定結(jié)點惶室,返回該結(jié)點,否則返回該結(jié)點在二叉樹中所處位置的父節(jié)點
     * @param head
     * @param key
     * @return
     */
    public TreeNode head = null;  //根節(jié)點
    /**
     * 設(shè)置根節(jié)點的值
     * @param val
     */
    public void setHeadValue(int val) {
        if (head == null) {
            head = new TreeNode();
            head.value = val;
        } else {
            head.value = val;
        }
    }
    /**
     * 在二叉搜索樹中搜索指定結(jié)點
     * @param key
     * @return
     */
    public boolean search(int key) {
        TreeNode res = search(head, null, key);
        if (res != null && res.value == key) {
            return true;
        } else {
            return false;
        }
    }
    /**
     * 輸入根節(jié)點玄货,父節(jié)點皇钞,和要查找的值,找到指定結(jié)點松捉,如果該節(jié)點存在夹界?返回該結(jié)點:否則返回該結(jié)點的父節(jié)點
     * @param myHead
     * @param father
     * @param key
     * @return
     */
    private TreeNode search(TreeNode myHead, TreeNode father, int key) {
        if (myHead == null) {
            return father;
        } else if (myHead.value == key) {
            return myHead;
        } else if (myHead.value > key) {
            return search(myHead.left, myHead, key);
        } else {
            return search(myHead.right, myHead, key);
        }
    }
    /**
     * 插入結(jié)點,返回結(jié)點引用
     * @param head
     * @param key
     * @return
     */
    public TreeNode insert(int key) {
        TreeNode res = null;
        if (head == null) {   //如果樹為空隘世,創(chuàng)建根節(jié)點可柿,返回
            head = new TreeNode();
            head.value = key;
            res = head;
        } else {
            res = search(head, null, key);  //搜索該節(jié)點
            if (res.value != key) {     //如果二叉搜索樹中不存在該結(jié)點,進行插入
                TreeNode newNode = new TreeNode();
                newNode.value = key;
                if (newNode.value > res.value) {
                    res.right = newNode;
                } else {
                    res.left = newNode;
                }
                res = newNode;
            }
        }
        return res;
    }
    /**
     * 刪除指定結(jié)點丙者,如果存在該結(jié)點复斥,返回true,否則返回false
     * @param key
     * @return
     */
    public boolean delete(int key) {
        if (head == null) {
            return false;
        }
        TreeNode parent = null;
        TreeNode cur = head;
        while (cur != null) {  //找到要刪除的結(jié)點和其父節(jié)點
            if (cur.value == key) {
                break;
            } else if (cur.value > key){
                parent = cur;
                cur = cur.left;
            } else {
                parent = cur;
                cur = cur.right;
            }
        }
        if (cur == null) { //如果不存在該結(jié)點,不需要刪除械媒,返回
            return false;
        } else {           //二叉搜索樹中存在該結(jié)點
            if (cur.left == null && cur.right == null) {  //要刪除的結(jié)點的左右子樹都為空
                if (parent == null) { //要刪除的結(jié)點就是根節(jié)點目锭,并且其沒有子結(jié)點,將根節(jié)點設(shè)置為null
                    head = null;
                } else {  //從parent中刪除該結(jié)點
                    if (parent.left == cur) {
                        parent.left = null;
                    } else {
                        parent.right = null;
                    }
                }
            } else if (cur.left == null) {  //要刪除的結(jié)點的左子樹為空纷捞,要刪除結(jié)點的右結(jié)點頂替
                cur.value = cur.right.value;
                cur.left = cur.right.left;
                cur.right = cur.right.right;
            } else if (cur.right == null) {  //要刪除的結(jié)點的右子樹為空痢虹,要刪除結(jié)點的左結(jié)點頂替
                cur.value = cur.left.value;
                cur.right = cur.left.right;
                cur.left = cur.left.left;
            } else {   //要刪除的結(jié)點的所有子樹都不為空,找到中序遍歷的前一個結(jié)點主儡,替換并刪除奖唯。
                TreeNode temp = cur;
                parent = cur;
                cur = cur.left;
                while (cur.right != null) {
                    parent = cur;
                    cur = cur.right;
                }
                temp.value = cur.value;
                if (parent.left == cur) {
                    parent.left = cur.left;
                } else {
                    parent.right = cur.left;
                }
            }
            return true;
        }
    }
    /**
     * 中序遍歷
     */
    public void midSearch() {
        TreeNode cur = head;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            System.out.println(cur.value);
            cur = cur.right;
        }
    }
    /**
     * 二叉樹結(jié)點
     * @author TinyMonster
     *
     */
    public static class TreeNode {
        int value = 0;
        TreeNode left = null;
        TreeNode right = null;
    }
    /*
     * 
     */
    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.setHeadValue(4);
        tree.insert(2);
        tree.insert(1);
        tree.insert(3);
        tree.insert(6);
        tree.insert(5);
        tree.insert(7);
        tree.midSearch();
        System.out.println("-----查找結(jié)點7-----");
        System.out.println(tree.search(7));
        System.out.println("-----刪除結(jié)點7-----");
        tree.delete(7);
        tree.midSearch();
        System.out.println("-----刪除結(jié)點4-----");
        tree.delete(4);
        tree.midSearch();
    }
}

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市缀辩,隨后出現(xiàn)的幾起案子臭埋,更是在濱河造成了極大的恐慌踪央,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,627評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件瓢阴,死亡現(xiàn)場離奇詭異畅蹂,居然都是意外死亡,警方通過查閱死者的電腦和手機荣恐,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,180評論 3 399
  • 文/潘曉璐 我一進店門液斜,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人叠穆,你說我怎么就攤上這事少漆。” “怎么了硼被?”我有些...
    開封第一講書人閱讀 169,346評論 0 362
  • 文/不壞的土叔 我叫張陵示损,是天一觀的道長。 經(jīng)常有香客問我嚷硫,道長检访,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,097評論 1 300
  • 正文 為了忘掉前任仔掸,我火速辦了婚禮脆贵,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘起暮。我一直安慰自己卖氨,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 69,100評論 6 398
  • 文/花漫 我一把揭開白布负懦。 她就那樣靜靜地躺著筒捺,像睡著了一般。 火紅的嫁衣襯著肌膚如雪密似。 梳的紋絲不亂的頭發(fā)上焙矛,一...
    開封第一講書人閱讀 52,696評論 1 312
  • 那天,我揣著相機與錄音残腌,去河邊找鬼村斟。 笑死,一個胖子當(dāng)著我的面吹牛抛猫,可吹牛的內(nèi)容都是我干的蟆盹。 我是一名探鬼主播,決...
    沈念sama閱讀 41,165評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼闺金,長吁一口氣:“原來是場噩夢啊……” “哼逾滥!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,108評論 0 277
  • 序言:老撾萬榮一對情侶失蹤寨昙,失蹤者是張志新(化名)和其女友劉穎讥巡,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體舔哪,經(jīng)...
    沈念sama閱讀 46,646評論 1 319
  • 正文 獨居荒郊野嶺守林人離奇死亡欢顷,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,709評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了捉蚤。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片抬驴。...
    茶點故事閱讀 40,861評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖缆巧,靈堂內(nèi)的尸體忽然破棺而出布持,到底是詐尸還是另有隱情,我是刑警寧澤陕悬,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布题暖,位于F島的核電站,受9級特大地震影響捉超,放射性物質(zhì)發(fā)生泄漏芙委。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,196評論 3 336
  • 文/蒙蒙 一狂秦、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧推捐,春花似錦裂问、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,698評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至皮壁,卻和暖如春椭更,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背蛾魄。 一陣腳步聲響...
    開封第一講書人閱讀 33,804評論 1 274
  • 我被黑心中介騙來泰國打工虑瀑, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人滴须。 一個月前我還...
    沈念sama閱讀 49,287評論 3 379
  • 正文 我出身青樓舌狗,卻偏偏與公主長得像,于是被迫代替她去往敵國和親扔水。 傳聞我的和親對象是個殘疾皇子痛侍,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,860評論 2 361