面試算法知識梳理(10) - 二叉查找樹

面試算法代碼知識梳理系列

面試算法知識梳理(1) - 排序算法
面試算法知識梳理(2) - 字符串算法第一部分
面試算法知識梳理(3) - 字符串算法第二部分
面試算法知識梳理(4) - 數(shù)組第一部分
面試算法知識梳理(5) - 數(shù)組第二部分
面試算法知識梳理(6) - 數(shù)組第三部分
面試算法知識梳理(7) - 數(shù)組第四部分
面試算法知識梳理(8) - 二分查找算法及其變型
面試算法知識梳理(9) - 鏈表算法第一部分
面試算法知識梳理(10) - 二叉查找樹
面試算法知識梳理(11) - 二叉樹算法第一部分
面試算法知識梳理(12) - 二叉樹算法第二部分
面試算法知識梳理(13) - 二叉樹算法第三部分


一缩焦、概述

二叉查找樹 又稱為 二叉搜索樹驼修,它是一棵空樹,或者是具有下列性質(zhì)的 二叉樹

  • 若左子樹不空背稼,則左子樹上所有結(jié)點的值均小于或等于它的結(jié)點
  • 若右子樹不空兼砖,則右子樹上所有結(jié)點的值均大于或等于它的根結(jié)點的值
  • 左测蘑、右子樹也分別為二叉查找樹

下面我們就來一起梳理一下和二叉查找樹相關(guān)的知識點:

  • 建立二叉查找樹
  • 刪除二叉查找樹中指定元素
  • 非遞歸遍歷二叉查找樹(先序遍歷、中序遍歷制肮、后序遍歷)

二冒窍、代碼實現(xiàn)

2.1 建立二叉查找樹

二叉查找樹的表示

二叉查找樹可以用Tree來表示,它包含一個root變量豺鼻,用于存放這棵樹的根結(jié)點综液,size表示樹中元素的個數(shù),每個結(jié)點Node包含以下的變量:

  • parent:指向其父結(jié)點
  • left儒飒、right:分別指向它的左孩子和右孩子
  • value:該結(jié)點存儲的值

代碼實現(xiàn)

下面我們輸入一個數(shù)組p谬莹,通過它建立一個二叉查找樹,并通過 遞歸中序遍歷 的方式打印出樹中的元素,按照二叉查找樹的定義附帽,最后輸出的結(jié)果必然是遞增排序的埠戳。

class Untitled {
    
    static class Tree {
        int size;
        Node root;
    }
    
    static class Node {
        Node parent;
        Node left;
        Node right;
        int value;
    }
    
    static void insertNode(Tree tree, int value) {
        if (tree == null) {
            return;
        }
        Node tNode = tree.root;
        //待插入結(jié)點的父結(jié)點,如果遍歷完為空蕉扮,說明此時是一個空樹整胃。
        Node pNode = null;
        //新的結(jié)點。
        Node nNode = new Node();
        nNode.value = value;
        while (tNode != null) {
            pNode = tNode;
            if (tNode.value > value) {
                tNode = tNode.left;
            } else {
                tNode = tNode.right;
            }
        }
        nNode.parent = pNode;
        if (pNode == null) {
            tree.root = nNode;
        } else if (pNode.value > value) {
            pNode.left = nNode;
        } else {
            pNode.right = nNode;
        }
        tree.size++;
    }
    
    static Tree createBinTree(int p[], int len) {
        Tree tree = new Tree();
        for (int i=0; i<len; i++) {
            int value = p[i];
            insertNode(tree, value);
        }
        return tree;
    }
    
    //遞歸的方式中序打印二叉查找樹喳钟,最后輸出的順序必然是遞增的爪模。
    static void printInOrder(Node node) {
        if (node == null) {
            return;
        }
        printInOrder(node.left);
        System.out.println(node.value);
        printInOrder(node.right);
    }
    
    public static void main(String[] args) {
        int p[] = {4,5,6,1,2,3};
        Tree tree = createBinTree(p, p.length);
        printInOrder(tree.root);
    }
}

運行結(jié)果

>> 1
>> 2
>> 3
>> 4
>> 5
>> 6

2.2 刪除二叉查找樹中指定元素

在二叉查找樹中刪除某個元素,其核心思想就是 找到待刪除結(jié)點的父結(jié)點荚藻,并將該父結(jié)點的leftright指向 待刪除結(jié)點的孩子結(jié)點

  • 如果待刪除結(jié)點只有一個孩子結(jié)點,那么用 該孩子結(jié)點替換待刪除結(jié)點 即可洁段。
  • 如果待刪除結(jié)點有兩個孩子結(jié)點应狱,那么就需要進行如下幾步操作:
    • 第一步:找到 待刪除結(jié)點的右子樹的最小結(jié)點 作為替換結(jié)點,如果該結(jié)點不是右子樹的根節(jié)點祠丝,那么還需要 先用最小結(jié)點的右結(jié)點來替換最小結(jié)點
    • 第二步:用第一步找到的結(jié)點替換待刪除結(jié)點
    • 第三步:將待刪除結(jié)點的左子樹的根節(jié)點嫁接到替換結(jié)點 上疾呻。
class Untitled {

    static class Tree {
        int size;
        Node root;
    }

    static class Node {
        Node parent;
        Node left;
        Node right;
        int value;
    }

    static void insertNode(Tree tree, int value) {
        if (tree == null) {
            return;
        }
        Node tNode = tree.root;
        //待插入結(jié)點的父結(jié)點,如果遍歷完為空写半,說明此時是一個空樹岸蜗。
        Node pNode = null;
        //新的結(jié)點。
        Node nNode = new Node();
        nNode.value = value;
        while (tNode != null) {
            pNode = tNode;
            if (tNode.value > value) {
                tNode = tNode.left;
            } else {
                tNode = tNode.right;
            }
        }
        nNode.parent = pNode;
        if (pNode == null) {
            tree.root = nNode;
        } else if (pNode.value > value) {
            pNode.left = nNode;
        } else {
            pNode.right = nNode;
        }
        tree.size++;
    }

    static Tree createBinTree(int p[], int len) {
        Tree tree = new Tree();
        for (int i=0; i<len; i++) {
            int value = p[i];
            insertNode(tree, value);
        }
        return tree;
    }

    static Node searchNode(Tree tree, int value) {
        if (tree == null) {
            return null;
        }
        Node find = null;
        Node node = tree.root;
        while (node != null) {
            if (node.value > value) {
                node = node.left;
            } else if (node.value < value) {
                node = node.right;
            } else {
                find = node;
                break;
            }
        }
        return find;
    }

    static Node minNode(Node node) {
        while (node != null && node.left != null) {
            node = node.left;
        }
        return node;
    }

    static void transPlant(Tree tree, Node deleteNode, Node replaceNode) {
        if (deleteNode.parent == null) {
            tree.root = replaceNode;
        } else if (deleteNode.parent.left == deleteNode) {
            deleteNode.parent.left = replaceNode;
        } else if (deleteNode.parent.right == deleteNode) {
            deleteNode.parent.right = replaceNode;
        }
        if (replaceNode != null) {
            replaceNode.parent = deleteNode.parent;
        }
    }

    static void deleteNode(Tree tree, int value) {
        if (tree == null) {
            return;
        }
        Node deleteNode = searchNode(tree, value);
        if (deleteNode != null) {
            if (deleteNode.left == null) {
                transPlant(tree, deleteNode, deleteNode.right);
            } else if (deleteNode.right == null) {
                transPlant(tree, deleteNode, deleteNode.left);
            } else {
                Node replaceNode = minNode(deleteNode.right);
                if (replaceNode != deleteNode.right) {
                    transPlant(tree, replaceNode, replaceNode.right);
                    deleteNode.right.parent = replaceNode;
                    replaceNode.right = deleteNode.right;
                }
                transPlant(tree, deleteNode, replaceNode);
                deleteNode.left.parent = replaceNode;
                replaceNode.left = deleteNode.left;
            }
        }
    }

    //遞歸的方式中序打印二叉查找樹叠蝇,最后輸出的順序必然是遞增的璃岳。
    static void printInOrder(Node node) {
        if (node == null) {
            return;
        }
        printInOrder(node.left);
        System.out.println(node.value);
        printInOrder(node.right);
    }

    public static void main(String[] args) {
        int p[] = {3,5,6,1,2,4};
        Tree tree = createBinTree(p, p.length);
        deleteNode(tree, 3);
        printInOrder(tree.root);
    }
}

運行結(jié)果

>> 1
>> 2
>> 4
>> 5
>> 6

2.3 非遞歸遍歷方式

解決思路

對于二叉樹的遞歸遍歷,相信大家已經(jīng)很熟悉了悔捶,這里演示的是如何通過“椓蹇叮”來實現(xiàn)二叉樹的非遞歸遍歷:

class Untitled {

    static class Tree {
        int size;
        Node root;
    }

    static class Node {
        Node parent;
        Node left;
        Node right;
        int value;
    }

    static void insertNode(Tree tree, int value) {
        if (tree == null) {
            return;
        }
        Node tNode = tree.root;
        //待插入結(jié)點的父結(jié)點,如果遍歷完為空蜕该,說明此時是一個空樹犁柜。
        Node pNode = null;
        //新的結(jié)點。
        Node nNode = new Node();
        nNode.value = value;
        while (tNode != null) {
            pNode = tNode;
            if (tNode.value > value) {
                tNode = tNode.left;
            } else {
                tNode = tNode.right;
            }
        }
        nNode.parent = pNode;
        if (pNode == null) {
            tree.root = nNode;
        } else if (pNode.value > value) {
            pNode.left = nNode;
        } else {
            pNode.right = nNode;
        }
        tree.size++;
    }

    static Tree createBinTree(int p[], int len) {
        Tree tree = new Tree();
        for (int i=0; i<len; i++) {
            int value = p[i];
            insertNode(tree, value);
        }
        return tree;
    }
    
    //先序遍歷堂淡。
    static void printPreOrder(Tree tree) {
        Node p[] = new Node[tree.size];
        int index = -1;
        Node node = tree.root;
        while (node != null || index >= 0) {
            while (node != null) {
                int value = node.value;
                System.out.println(node.value);
                index++;
                p[index] = node;
                node = node.left;
            }
            if (index >= 0) {
                node = p[index];
                p[index] = null;
                index--;
            }
            node = node.right;
        }
    }
    
    //中序遍歷馋缅。
    static void printInOrder(Tree tree) {
        Node p[] = new Node[tree.size];
        int index = -1;
        Node node = tree.root;
        while (node != null || index >= 0) {
            while (node != null) {
                int value = node.value;
                index++;
                p[index] = node;
                node = node.left;
            }
            if (index >= 0) {
                node = p[index];
                System.out.println(node.value);
                p[index] = null;
                index--;
            
            }
            node = node.right;
        }
    }
    
    //后序遍歷。
    static void printPostOrder(Tree tree) {
        Node p[] = new Node[tree.size];
        int index = 0;
        Node curNode = tree.root;
        Node preNode = null;
        p[index] = curNode;
        while (index >= 0) {
            curNode = p[index];
            //如果沒有孩子結(jié)點绢淀。
            boolean hasNoChild = (curNode.left == null && curNode.right == null);
            //如果它的左孩子或者右孩子已經(jīng)被訪問過萤悴。
            boolean hasVisit = preNode == curNode.left || preNode == curNode.right;
            if (hasNoChild || hasVisit) {
                System.out.println(curNode.value);
                p[index] = null;
                index--;
                preNode = curNode;
            } else {
                //左孩子先入棧,保證右孩子先被訪問更啄。
                if (curNode.left != null) {
                    index++;
                    p[index] = curNode.left;
                } 
                if (curNode.right != null) {
                    index++;
                    p[index] = curNode.right;
                }
            }
        }
    }
    
    //遞歸的方式中序打印二叉查找樹稚疹,最后輸出的順序必然是遞增的。
    static void printInOrder(Node node) {
        if (node == null) {
            return;
        }
        printInOrder(node.left);
        System.out.println(node.value);
        printInOrder(node.right);
    }

    public static void main(String[] args) {
        int p[] = {3,5,6,1,2,4};
        Tree tree = createBinTree(p, p.length);
        System.out.println("- 先序遍歷 - ");
        printPreOrder(tree);
        System.out.println("- 中序遍歷 - ");
        printInOrder(tree);
        System.out.println("- 后序遍歷 - ");
        printPostOrder(tree);
    }
}

運行結(jié)果

- 先序遍歷 - 
3
1
2
5
4
6
- 中序遍歷 - 
1
2
3
4
5
6
- 后序遍歷 - 
6
4
5
2
1
3

更多文章,歡迎訪問我的 Android 知識梳理系列:

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末内狗,一起剝皮案震驚了整個濱河市怪嫌,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌柳沙,老刑警劉巖岩灭,帶你破解...
    沈念sama閱讀 222,946評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異赂鲤,居然都是意外死亡噪径,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,336評論 3 399
  • 文/潘曉璐 我一進店門数初,熙熙樓的掌柜王于貴愁眉苦臉地迎上來找爱,“玉大人,你說我怎么就攤上這事泡孩〕瞪悖” “怎么了?”我有些...
    開封第一講書人閱讀 169,716評論 0 364
  • 文/不壞的土叔 我叫張陵仑鸥,是天一觀的道長吮播。 經(jīng)常有香客問我,道長眼俊,這世上最難降的妖魔是什么意狠? 我笑而不...
    開封第一講書人閱讀 60,222評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮疮胖,結(jié)果婚禮上环戈,老公的妹妹穿的比我還像新娘。我一直安慰自己澎灸,他們只是感情好谷市,可當我...
    茶點故事閱讀 69,223評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著击孩,像睡著了一般迫悠。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上巩梢,一...
    開封第一講書人閱讀 52,807評論 1 314
  • 那天创泄,我揣著相機與錄音,去河邊找鬼括蝠。 笑死鞠抑,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的忌警。 我是一名探鬼主播搁拙,決...
    沈念sama閱讀 41,235評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了箕速?” 一聲冷哼從身側(cè)響起酪碘,我...
    開封第一講書人閱讀 40,189評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎盐茎,沒想到半個月后兴垦,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,712評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡字柠,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,775評論 3 343
  • 正文 我和宋清朗相戀三年探越,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片窑业。...
    茶點故事閱讀 40,926評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡钦幔,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出常柄,到底是詐尸還是另有隱情拐纱,我是刑警寧澤秸架,帶...
    沈念sama閱讀 36,580評論 5 351
  • 正文 年R本政府宣布咆蒿,位于F島的核電站沃测,受9級特大地震影響蒂破,放射性物質(zhì)發(fā)生泄漏附迷。R本人自食惡果不足惜喇伯,卻給世界環(huán)境...
    茶點故事閱讀 42,259評論 3 336
  • 文/蒙蒙 一艾猜、第九天 我趴在偏房一處隱蔽的房頂上張望淤毛。 院中可真熱鬧钱床,春花似錦查牌、人聲如沸纸颜。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,750評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽狂票。三九已至,卻和暖如春掂器,著一層夾襖步出監(jiān)牢的瞬間国瓮,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,867評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留与斤,地道東北人磷支。 一個月前我還...
    沈念sama閱讀 49,368評論 3 379
  • 正文 我出身青樓廓潜,卻偏偏與公主長得像,于是被迫代替她去往敵國和親悼院。 傳聞我的和親對象是個殘疾皇子据途,可洞房花燭夜當晚...
    茶點故事閱讀 45,930評論 2 361