二叉查找樹(shù)代碼實(shí)現(xiàn)

一荤堪、定義

  1. 查找二叉樹(shù)又叫二叉排序樹(shù)合陵,如果同時(shí)滿足以下性質(zhì):
    1. 左右子樹(shù)都是二叉樹(shù)枢赔;
    2. 如果左子樹(shù)不為空,那么左子樹(shù)上面的所有節(jié)點(diǎn)的關(guān)鍵字都比根節(jié)點(diǎn)的關(guān)鍵字杏抵糠爬;
    3. 如果右子樹(shù)不為空,那么右子樹(shù)上面的所有節(jié)點(diǎn)的關(guān)鍵字都比跟節(jié)點(diǎn)的關(guān)鍵字大举庶;
  2. 好處:方便查找执隧,可以提高查找效率,查找二叉樹(shù)越平衡户侥,查找的效率的越穩(wěn)定镀琉,效率越高,這種樹(shù)就是平衡二叉樹(shù)蕊唐;

二屋摔、代碼實(shí)現(xiàn)

public class SearchBinaryTree {

    private TreeNode root;//跟節(jié)點(diǎn)

    /**
     * 創(chuàng)建查找二叉樹(shù),如果關(guān)鍵字比根節(jié)點(diǎn)的關(guān)鍵字大替梨,就往右邊插入钓试,
     * 如果關(guān)鍵字比根節(jié)點(diǎn)小,就往左邊插入
     * @param data 帶插入的數(shù)據(jù)
     * @return
     */
    public TreeNode put(int data) {
        TreeNode node = null;
        TreeNode parent = null;
        //首先判斷根節(jié)點(diǎn)副瀑,如果根節(jié)點(diǎn)為空弓熏,則新創(chuàng)建的節(jié)點(diǎn)為根節(jié)點(diǎn)
        if (root == null) {
            node = new TreeNode(0, data);
            root = node;
            return node;
        } else {
            //如果不是根節(jié)點(diǎn),就需要不停地遍歷已有的節(jié)點(diǎn)糠睡,找到滿足條件的節(jié)點(diǎn)的位置挽鞠,然后插入節(jié)點(diǎn)
            //和根節(jié)點(diǎn)進(jìn)行比較,首先要拿到根節(jié)點(diǎn)
            node = root;
            while (node != null) {
                //把當(dāng)前結(jié)點(diǎn)制定為父節(jié)點(diǎn)狈孔,然后比較左右孩子和當(dāng)前節(jié)點(diǎn)的大小
                parent = node;
                //如果要插入的數(shù)據(jù)比當(dāng)前結(jié)點(diǎn)要大信认,就需要往右子樹(shù)上找
                if (data > node.data) {
                    node = node.rightChild;
                } else if (data < node.data) {
                    node = node.leftChild;
                } else {
                    return node;
                }
            }
            //while循環(huán)結(jié)束,就表示找到了要插入的地方均抽,
            // 接下來(lái)就是創(chuàng)建節(jié)點(diǎn)嫁赏,然后把這個(gè)節(jié)點(diǎn)掛在指定的位置
            //角標(biāo)默認(rèn)是0
            node = new TreeNode(0, data);
            //節(jié)點(diǎn)創(chuàng)建完畢,需要判斷放在父節(jié)點(diǎn)的左邊還是右邊
            if (data < parent.data) {
                parent.leftChild = node;
            } else {
                parent.rightChild = node;
            }
            //指定這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)
            node.parent = parent;
            return node;
        }
    }

    /**
     * 刪除二叉查找樹(shù)中的某個(gè)節(jié)點(diǎn)油挥,
     * <strong>因?yàn)槭嵌娌檎覙?shù)潦蝇,所以是刪除某個(gè)節(jié)點(diǎn)后,需要對(duì)剩下的節(jié)點(diǎn)進(jìn)行
     * 重新排序喘漏,使之依然是二叉查找樹(shù)
     * </strong>
     * @param data
     */
    public void deleteNode(int data) {
        //要想刪除某個(gè)節(jié)點(diǎn)护蝶,必須先找到這個(gè)節(jié)點(diǎn)
        TreeNode node = searchNode(data);
        //如果node為空华烟,表示沒(méi)有找到
        if (node == null) {
            throw new NoSuchElementException("沒(méi)有指定的節(jié)點(diǎn)");
        } else {
            delete(node);
        }
    }

    /**
     * 刪除節(jié)點(diǎn)
     * @param node 要?jiǎng)h除的節(jié)點(diǎn)
     */
    private void delete(TreeNode node) {
        if (node == null) {
            throw new NoSuchElementException("沒(méi)有這個(gè)節(jié)點(diǎn)");
        } else {
            //如果當(dāng)前節(jié)點(diǎn)不為空翩迈,就需要判斷這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn),左右孩子節(jié)點(diǎn)是否為空
            TreeNode parent = node.parent;
            //如果 當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)盔夜,直接刪除
            if (node.leftChild == null && node.rightChild == null) {
                //需要判斷是父親的左兒子還是右兒子
                if (parent.leftChild == node) {
                    parent.leftChild = null;
                    node.parent = null;
                } else {
                    parent.rightChild = null;
                    node.parent = null;
                }
            } else if (node.leftChild != null && node.rightChild == null) {
                //如果被刪除的節(jié)點(diǎn)有左孩子沒(méi)有右孩子
                //這是還需要判斷這個(gè)節(jié)點(diǎn)是在父節(jié)點(diǎn)的左子樹(shù)上负饲,還是在右子樹(shù)上
                //如果這個(gè)節(jié)點(diǎn)在左子樹(shù)上堤魁,就需要把這個(gè)節(jié)點(diǎn)的左孩子放在parent的左子樹(shù)上
                if (parent.leftChild == node) {
                    parent.leftChild = node.leftChild;
                } else {
                    parent.rightChild = node.leftChild;
                }
            } else if (node.leftChild == null && node.rightChild != null) {
                //如果被刪除的節(jié)點(diǎn)有右孩子而沒(méi)有左孩子
                if (parent.leftChild == node) {
                    parent.leftChild = node.rightChild;
                } else {
                    parent.rightChild = node.rightChild;
                }
            } else if (node.leftChild != null && node.rightChild != null) {
                //如果被刪除的節(jié)點(diǎn)既有左孩子又有右孩子
                //找后繼節(jié)點(diǎn)
                TreeNode next = getNextNode(node);
                delete(next);
                node.data = next.data;
            }
        }
    }

    /**
     * 找到某個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)
     * @param node
     * @return
     */
    private TreeNode getNextNode(TreeNode node) {
        if (node == null) {
            return null;
        } else {
            //如果這個(gè)節(jié)點(diǎn)的右子樹(shù)不為空,就在右子樹(shù)里面找到key最小的節(jié)點(diǎn)
            if (node.rightChild != null) {
                return getMinTreeNode(node);
            } else {
                TreeNode parent = node.parent;
                while (parent == null && node == parent.rightChild) {
                    node = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        }
    }

    /**
     * 找到這個(gè)節(jié)點(diǎn)的子樹(shù)下面key最小的節(jié)點(diǎn),最小的節(jié)點(diǎn)一定在該節(jié)點(diǎn)的左子樹(shù)上的最末端
     * @param node
     * @return
     */
    private TreeNode getMinTreeNode(TreeNode node) {
        if (node == null) {
            return null;
        } else {
            while (node.leftChild != null) {
                node = node.leftChild;
            }
        }
        return node;
    }

    private TreeNode searchNode(int data) {
        TreeNode node;
        //先從根節(jié)點(diǎn)開(kāi)始找
        node = root;
        if (node == null) {
            return null;
        } else {
            while (node != null && data != node.data) {
                if (data > node.data) {
                    node = node.rightChild;
                } else if (data < node.data) {
                    node = node.leftChild;
                } else {
                    return node;
                }
            }
            //當(dāng)while循環(huán)結(jié)束后返十,就表示已經(jīng)遍歷完了整個(gè)二叉查找樹(shù)妥泉,
            // 有可能找到,有可能找不到洞坑,即node有可能為null
            return node;
        }
    }

    /**
     * 中序遍歷二叉查找樹(shù)盲链,如果樹(shù)構(gòu)建的正確,中序遍歷出來(lái)應(yīng)該是升序的
     * @param node
     */
    public void midOrderTraverse(TreeNode node) {
        midOrderTraverse(node.leftChild);
        System.out.print(node.data + " ");
        midOrderTraverse(node.rightChild);
    }

    private static final class TreeNode {
        private int key;//二叉查找樹(shù)的關(guān)鍵字迟杂,通過(guò)這個(gè)關(guān)鍵字對(duì)節(jié)點(diǎn)進(jìn)行排序
        private TreeNode leftChild;
        private TreeNode rightChild;
        private TreeNode parent;
        private int data;

        public TreeNode(int key, int data) {
            this.key = key;
            this.data = data;
            this.leftChild = null;
            this.rightChild = null;
            this.parent = null;
        }

        public int getKey() {
            return key;
        }

        public void setKey(int key) {
            this.key = key;
        }

        public TreeNode getLeftChild() {
            return leftChild;
        }

        public void setLeftChild(TreeNode leftChild) {
            this.leftChild = leftChild;
        }

        public TreeNode getRightChild() {
            return rightChild;
        }

        public void setRightChild(TreeNode rightChild) {
            this.rightChild = rightChild;
        }

        public TreeNode getParent() {
            return parent;
        }

        public void setParent(TreeNode parent) {
            this.parent = parent;
        }

        public int getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }
    }
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末刽沾,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子排拷,更是在濱河造成了極大的恐慌侧漓,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,681評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件监氢,死亡現(xiàn)場(chǎng)離奇詭異布蔗,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)浪腐,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門纵揍,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人议街,你說(shuō)我怎么就攤上這事骡男。” “怎么了傍睹?”我有些...
    開(kāi)封第一講書人閱讀 169,421評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵隔盛,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我拾稳,道長(zhǎng)吮炕,這世上最難降的妖魔是什么? 我笑而不...
    開(kāi)封第一講書人閱讀 60,114評(píng)論 1 300
  • 正文 為了忘掉前任访得,我火速辦了婚禮龙亲,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘悍抑。我一直安慰自己鳄炉,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布搜骡。 她就那樣靜靜地躺著拂盯,像睡著了一般。 火紅的嫁衣襯著肌膚如雪记靡。 梳的紋絲不亂的頭發(fā)上谈竿,一...
    開(kāi)封第一講書人閱讀 52,713評(píng)論 1 312
  • 那天团驱,我揣著相機(jī)與錄音,去河邊找鬼空凸。 笑死嚎花,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的呀洲。 我是一名探鬼主播紊选,決...
    沈念sama閱讀 41,170評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼道逗!你這毒婦竟也來(lái)了丛楚?” 一聲冷哼從身側(cè)響起,我...
    開(kāi)封第一講書人閱讀 40,116評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤憔辫,失蹤者是張志新(化名)和其女友劉穎趣些,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體贰您,經(jīng)...
    沈念sama閱讀 46,651評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡坏平,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評(píng)論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了锦亦。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片舶替。...
    茶點(diǎn)故事閱讀 40,865評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖杠园,靈堂內(nèi)的尸體忽然破棺而出顾瞪,到底是詐尸還是另有隱情,我是刑警寧澤抛蚁,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布陈醒,位于F島的核電站,受9級(jí)特大地震影響瞧甩,放射性物質(zhì)發(fā)生泄漏钉跷。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評(píng)論 3 336
  • 文/蒙蒙 一肚逸、第九天 我趴在偏房一處隱蔽的房頂上張望爷辙。 院中可真熱鬧,春花似錦朦促、人聲如沸膝晾。這莊子的主人今日做“春日...
    開(kāi)封第一講書人閱讀 32,699評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)血当。三九已至,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間歹颓,已是汗流浹背坯屿。 一陣腳步聲響...
    開(kāi)封第一講書人閱讀 33,814評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工油湖, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留巍扛,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,299評(píng)論 3 379
  • 正文 我出身青樓乏德,卻偏偏與公主長(zhǎng)得像撤奸,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子喊括,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評(píng)論 2 361

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

  • 樹(shù)的概述 樹(shù)是一種非常常用的數(shù)據(jù)結(jié)構(gòu)胧瓜,樹(shù)與前面介紹的線性表,棧郑什,隊(duì)列等線性結(jié)構(gòu)不同府喳,樹(shù)是一種非線性結(jié)構(gòu) 1.樹(shù)的定...
    Jack921閱讀 4,462評(píng)論 1 31
  • 原文出處:http://www.cnblogs.com/maybe2030/p/4715035.html引文出處:...
    明教de教主閱讀 9,192評(píng)論 0 7
  • 目錄 [1. 順序查找][2. 二分查找][3. 插值查找][4. 斐波那契查找][5. 樹(shù)表查找][6. 分塊查...
    jiangmo閱讀 17,686評(píng)論 4 6
  • DD出生后的第54天的傍晚,準(zhǔn)備給他洗澡蘑拯,打開(kāi)尿不濕钝满,發(fā)現(xiàn)很多比較臭的大便。于是申窘,我們先用小盆給他清洗弯蚜,結(jié)果...
    滴兜外婆張敏閱讀 627評(píng)論 9 4
  • 二十歲,是個(gè)好年齡剃法,不早不晚碎捺,也不需要將就。 你充實(shí)自己贷洲,努力學(xué)習(xí)收厨,是你該做的;你自由灑脫优构,享受青...
    郭雪寒閱讀 495評(píng)論 5 3