一篇文章學(xué)會(huì)二叉樹和二叉查找樹

BaronZhang 發(fā)布于2019-08-26 13:46 / 2231人閱讀

摘要：二叉樹和二叉查找樹一個(gè)父節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)分別稱為左節(jié)點(diǎn)和右節(jié)點(diǎn)。下圖展示了一顆二叉樹當(dāng)考慮某種特殊的二叉樹，比如二叉查找樹時(shí)，確定子節(jié)點(diǎn)非常重要。實(shí)現(xiàn)二叉查找樹定義對(duì)象?，F(xiàn)在可以創(chuàng)建一個(gè)類來表示二叉查找樹。因此二叉查找樹也被叫做二叉排序樹。

樹是計(jì)算機(jī)科學(xué)中經(jīng)常用到的一種數(shù)據(jù)結(jié)構(gòu)。樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，以分層的方式存儲(chǔ)數(shù)據(jù)。

樹被用來存儲(chǔ)具有層級(jí)關(guān)系的數(shù)據(jù)，比如文件系統(tǒng)中的文件。

樹還可以用來存儲(chǔ)有序列表。

樹的定義

樹是由一組以邊連接的節(jié)點(diǎn)組成。公司的組織結(jié)構(gòu)圖就是一個(gè)樹的例子。

組織結(jié)構(gòu)圖就是一種樹

一棵樹最上面的節(jié)點(diǎn)成為根節(jié)點(diǎn)。如果一個(gè)節(jié)點(diǎn)下面連接著多個(gè)節(jié)點(diǎn)，那么該節(jié)點(diǎn)稱為父節(jié)點(diǎn)，它下面的節(jié)點(diǎn)稱為子節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)可以有0個(gè)，1個(gè)或者多個(gè)子節(jié)點(diǎn)。沒有任何子節(jié)點(diǎn)的節(jié)點(diǎn)稱為葉子節(jié)點(diǎn)。下圖展示了一些樹的術(shù)語(yǔ)。

沿著一組特定的邊，可以從一個(gè)節(jié)點(diǎn)走到另外一個(gè)與它不直接相連的節(jié)點(diǎn)。從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的這一組邊稱為路徑。以特定的順序訪問樹中所有的節(jié)點(diǎn)稱為樹的遍歷。

樹可以分為幾個(gè)層次，根節(jié)點(diǎn)是第0層，它的子節(jié)點(diǎn)是第1層，子節(jié)點(diǎn)的子節(jié)點(diǎn)是第2層，以此類推。樹中任何一層的節(jié)點(diǎn)都可以看成是子樹的根，該子樹包含根節(jié)點(diǎn)的子節(jié)點(diǎn)，子節(jié)點(diǎn)的子節(jié)點(diǎn)等。我們定義樹的層數(shù)就是樹的深度。

節(jié)點(diǎn)的高度：節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長(zhǎng)路徑（邊樹）。
節(jié)點(diǎn)的深度：根節(jié)點(diǎn)到這個(gè)節(jié)點(diǎn)所經(jīng)歷的邊的個(gè)數(shù)。
節(jié)點(diǎn)的層數(shù)：節(jié)點(diǎn)的深度+1。
節(jié)點(diǎn)的高度：根節(jié)點(diǎn)的高度。

下面舉個(gè)例子來看：

每一個(gè)節(jié)點(diǎn)都有一個(gè)與之關(guān)聯(lián)的值，該值有時(shí)被稱為鍵。

二叉樹是一種特殊的樹。它的子節(jié)點(diǎn)不超過2個(gè)。二叉樹具有一些特殊的計(jì)算性質(zhì)，使得在它之上的一些操作異常高效。

二叉樹和二叉查找樹

一個(gè)父節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)分別稱為左節(jié)點(diǎn)和右節(jié)點(diǎn)。左節(jié)點(diǎn)包含一組特定的值，右節(jié)點(diǎn)包含一組特定的值。

下圖展示了一顆二叉樹：

當(dāng)考慮某種特殊的二叉樹，比如二叉查找樹時(shí)，確定子節(jié)點(diǎn)非常重要。二叉查找樹是一種特殊的二叉樹，相對(duì)較小的值保存在左節(jié)點(diǎn)中，較大的值保存在右節(jié)點(diǎn)中。這一特性使得查找的效率很高，對(duì)于數(shù)值和非數(shù)值的數(shù)據(jù)，比如單詞和字符串，也是如此。

我們來看下圖中的樹：

編號(hào)2的二叉樹中，葉子節(jié)點(diǎn)全在最底層，除了葉子節(jié)點(diǎn)以外的每個(gè)節(jié)點(diǎn)都有左右兩個(gè)子節(jié)點(diǎn)，這種二叉樹叫做滿二叉樹。

編號(hào)3的二叉樹中，葉子節(jié)點(diǎn)都在最底下兩層，最后一層的葉子節(jié)點(diǎn)都靠左排列，并且除了最后一層，其它層的節(jié)點(diǎn)個(gè)數(shù)都達(dá)到最大，這種二叉樹叫做完全二叉樹。

實(shí)現(xiàn)二叉查找樹（BST）

定義 Node?對(duì)象。

function node(data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
    this.show = show;

    function show() {
        return this.data;
    }
}

現(xiàn)在可以創(chuàng)建一個(gè) BST?類來表示二叉查找樹。我們讓類只包含一個(gè)數(shù)據(jù)成員：一個(gè)表示二叉查找樹根節(jié)點(diǎn)的 Node?對(duì)象。該類的構(gòu)造函數(shù)將根節(jié)點(diǎn)初始化為?null ，以此創(chuàng)建一個(gè)空節(jié)點(diǎn)。

BST?首先要有一個(gè)?insert()?方法，用來向樹中插入新節(jié)點(diǎn)。首先要?jiǎng)?chuàng)建一個(gè) Node?對(duì)象，將數(shù)據(jù)傳入該對(duì)象保存。
其次，檢查 BST?是否有根節(jié)點(diǎn)，如果沒有，則這是棵新樹，該節(jié)點(diǎn)就是根節(jié)點(diǎn)，這個(gè)方法到此也就結(jié)束了；否則，進(jìn)入下一步。

如果待插入節(jié)點(diǎn)不是根節(jié)點(diǎn)，那么就準(zhǔn)備遍歷 BST ，找到插入的適當(dāng)位置。該過程類似遍歷鏈表。用一個(gè)節(jié)點(diǎn)保存當(dāng)前節(jié)點(diǎn)，一層層地遍歷 BST 。

進(jìn)入 BST?以后，下一步就需要確定將該節(jié)點(diǎn)放在什么位置。找到正確的插入點(diǎn)時(shí)，會(huì)跳出循環(huán)。

查找正確的插入點(diǎn)的算法如下：

設(shè)根節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)；

如果待插入的節(jié)點(diǎn)小于當(dāng)前節(jié)點(diǎn)，則設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的左節(jié)點(diǎn)；反之，執(zhí)行第四步；

如果當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)為?null ，就將新的節(jié)點(diǎn)插入這個(gè)位置，退出循環(huán)；反之，繼續(xù)執(zhí)行下一次循環(huán)；

設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的右節(jié)點(diǎn)；

如果當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)為 null ，就將新的節(jié)點(diǎn)插入該位置，退出循環(huán)；反之，繼續(xù)執(zhí)行下一次循環(huán)。

function BST() {
    this.root = null;
    this.insert = insert;
  
    function insert(data) {
        var n = new Node(data, null, null);
        if(this.root == null) {
            this.root = n;
        }else {
            var currentNode = this.root;
            var parent;
            while(true) {
                parent = currentNode;
                if(data < currentNode.data) {
                    currentNode = currentNode.left;
                    if(currentNode == null) {
                        parent.left = n;
                        break;
                    }
                }else {
                    currentNode = currentNode.right;
                    if(currentNode.data == null) {
                        parent.right = n;
                        break;
                    }
                }
            }
        }
    }
  
}

另外一個(gè)寫法，其實(shí)思路是一樣的，但是上面的稍微簡(jiǎn)潔一些。（代碼思路來自王爭(zhēng)老師的《數(shù)據(jù)結(jié)構(gòu)與算法之美?》）

function insert(data) {
        var node = new Node(data, null, null);
        if(this.root == null) {
            this.root = node;
        }else {
            p = this.root;
            while(p !== null) {
                if(data < p.data) {
                    if(p.left == null) {
                        p.left = node;
                        return;
                    }
                    p = p.left;
                }else {
                    if(p.right == null) {
                        p.right = node;
                        return;
                    }
                    p = p.right;
                }
            }
        }
    }

遍歷二叉查找樹

有三種遍歷二叉樹的方法：中序、先序、后序。

中序遍歷按照節(jié)點(diǎn)上的鍵值，以升序訪問 BST?上的所有節(jié)點(diǎn)。
先序遍歷先訪問根節(jié)點(diǎn)，然后以同樣的方式訪問左子樹和右子樹。
后序遍歷先訪問葉子節(jié)點(diǎn)，從左子樹到右子樹，再到根節(jié)點(diǎn)。

先序遍歷是指，對(duì)于樹中的任意節(jié)點(diǎn)來說，先打印這個(gè)節(jié)點(diǎn)，然后在打印它的左子樹，最后打印它的右子樹。
中序遍歷是指，對(duì)于樹中的任意節(jié)點(diǎn)來說，先打印它的左子樹，然后打印它自己，最后打印它的右子樹。
后序遍歷是指，對(duì)于樹中的任意節(jié)點(diǎn)來說，先打印它的左子樹，然后打印它的右子樹，最后打印它自己。

中序遍歷的代碼如下：

function inOrder(node) {
        if(!(node == null)) {
            this.inOrder(node.left);
            console.log(node.show());
            this.inOrder(node.right);
        }
    }

var bst = new BST();
bst.insert(17)
bst.insert(19)
bst.insert(16)
bst.insert(34)
bst.insert(35)
bst.insert(36)
bst.inOrder(bst.root); // 16 17 19 34 35 36

下圖展示中序遍歷的訪問路徑：

先序遍歷的代碼如下：

function perOrder(node) {
        if(!(node == null)) {
            console.log(node.show());
            this.perOrder(node.left);
            this.perOrder(node.right);
        }
}

var bst = new BST();
bst.insert(17)
bst.insert(19)
bst.insert(16)
bst.insert(34)
bst.insert(35)
bst.insert(36)
console.log("先序遍歷");
bst.perOrder(bst.root); // 17 16 19 34 35 36

下圖展示先序遍歷的訪問路徑：

后序遍歷的代碼：

var bst = new BST();
bst.insert(17)
bst.insert(19)
bst.insert(16)
bst.insert(34)
bst.insert(35)
bst.insert(36)

console.log("后序遍歷");
bst.postOrder(bst.root); // 16 36 35 34 19 17

下圖展示后序遍歷的訪問路徑：

在二叉樹上進(jìn)行查找

對(duì) BST?通常有以下三種類型的查找：

查找給定值

查找最大值

查找最小值

查找最小值和最大值

因?yàn)檩^小的值總在左節(jié)點(diǎn)上，在 BST?上查找最小值，只需要遍歷左子樹，知道找到最后一個(gè)節(jié)點(diǎn)即可。

function getMin() {
        let currentNode = this.root;
        while(currentNode.left != null) {
            currentNode = currentNode.left;
        }
        return currentNode.data;
    }

在BST?上查找最大值，只需要遍歷右子樹，知道找到最后一個(gè)節(jié)點(diǎn)即可。

function getMax() {
        let currentNode = this.root;
        while(currentNode.right != null) {
            currentNode = currentNode.right;
        }
        return currentNode.data;
    }

查找給定值

在 BST?上查找給定的值，需要比較該值和當(dāng)前節(jié)點(diǎn)值的大小。通過比較，就能確定如果給定值不在當(dāng)前節(jié)點(diǎn)上，該向左遍歷還是向右遍歷。

function find(data) {
        var currentNode = this.root;
        while(currentNode != null) {
            if(currentNode.data == data) {
                return currentNode;
            }else if(currentNode.data < data) {
                currentNode = currentNode.right;
            }else {
                currentNode = currentNode.left;
            }
        }
        return null;
    }

如果找到給定值，該方法返回保存該值的方法；如果沒找到，該方法返回?null。

從二叉樹上刪除節(jié)點(diǎn)

從 BST?上刪除節(jié)點(diǎn)的操作最復(fù)雜，其復(fù)雜程度取決于刪除哪個(gè)節(jié)點(diǎn)。如果刪除沒有子節(jié)點(diǎn)的節(jié)點(diǎn)，那么非常簡(jiǎn)單。如果節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，就變得稍微復(fù)雜了。如果節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，是最復(fù)雜的。

分三種情況來處理：

如果要?jiǎng)h除的節(jié)點(diǎn)沒有子節(jié)點(diǎn)，我們只需要將父節(jié)點(diǎn)中，指向要?jiǎng)h除的節(jié)點(diǎn)的指針置為?null。比如圖中刪除節(jié)點(diǎn)55。

如果要?jiǎng)h除的節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)（左子節(jié)點(diǎn)或者右子節(jié)點(diǎn)），我們只需要更新父節(jié)點(diǎn)中，指向要?jiǎng)h除節(jié)點(diǎn)的指針，讓它指向要?jiǎng)h除節(jié)點(diǎn)的子節(jié)點(diǎn)就可以了。比如圖中刪除節(jié)點(diǎn)13。

如果要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，我們需要找到這個(gè)節(jié)點(diǎn)右子樹中的最小節(jié)點(diǎn)，把它替換到要?jiǎng)h除節(jié)點(diǎn)上，然后再刪除這個(gè)最小節(jié)點(diǎn)，因?yàn)樽钚」?jié)點(diǎn)中肯定沒有左子節(jié)點(diǎn)，我們可以用這兩個(gè)規(guī)則來進(jìn)行刪除操作，比如圖中刪除節(jié)點(diǎn)18。

function deleteNode(data) {
        var p = this.root; // p指向刪除的節(jié)點(diǎn)，初始化為根節(jié)點(diǎn)
        var pp = null; // pp記錄P的父節(jié)點(diǎn)
        while(p != null && p.data != data) {
            pp = p;
            if(data > p.data) {
                p = p.right;
            }else {
                p = p.left;
            }
        }
        if(p == null) return; // 沒有找到

        if(p.left != null && p.right != null) { // 要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)
            // 查找右子樹中的最小節(jié)點(diǎn)
            var minP = p.right;
            var minPP = p; // minPP表示minP的父節(jié)點(diǎn)
            while(minP.left != null) {
                pnode = minP;
                minP = p.left;
            }
            p.data = minP.data; // 將minP的數(shù)據(jù)替換到p中
            p = minP; //下面就變成刪除minP了
            pp = minP;

        }
        // 刪除節(jié)點(diǎn)是葉子節(jié)點(diǎn)或者只有一個(gè)子節(jié)點(diǎn)
        var childNode = null;
        if(p.left != null) {
            childNode = p.left;
        }else if(p.right != null) {
            childNode = p.right;
        }else {
            chiildNode = null;
        }
        if(pp == null) {
            p = chiildNode; // 刪除的是根節(jié)點(diǎn)
        }else if(pp.left == p) {
            pp.left = childNode;
        }else {
            pp.right = childNode;
        }
    }

實(shí)際上，關(guān)于二叉樹的刪除操作，還有個(gè)非常簡(jiǎn)單、取巧的方法，就是單純地將已刪除的節(jié)點(diǎn)標(biāo)記為“已刪除”，但并不是真正的刪除。這樣原本要?jiǎng)h除的元素還存儲(chǔ)在內(nèi)存中，比較浪費(fèi)內(nèi)存空間，但是刪除操作簡(jiǎn)單了很多，也沒有增加插入和查找的代碼實(shí)現(xiàn)的難度。

其他

二叉查找樹還有一個(gè)重要的特性，就是中序遍歷二叉查找樹，可以輸入有序的數(shù)據(jù)序列，時(shí)間復(fù)雜度是O(n)，非常高效。因此二叉查找樹也被叫做二叉排序樹。

云服務(wù)器 GPU云服務(wù)器二叉樹遍歷二叉樹創(chuàng)建二叉樹算法二叉樹排序樹規(guī)則

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/109489.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

BaronZhang

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

Windows 11 安全配置基線設(shè)置的最終版本已發(fā)布

閱讀 3258·2021-10-11 10:59
數(shù)據(jù)中心布線管理

閱讀 2812·2021-10-11 10:58
介紹2個(gè)有趣的IoT的項(xiàng)目

閱讀 2244·2021-09-04 16:45
電競(jìng)CSGO數(shù)據(jù)API接口 - 【聯(lián)賽列表】API調(diào)用示例代碼

閱讀 2717·2019-08-30 15:44
好看漂亮的html5網(wǎng)頁(yè)特效學(xué)習(xí)筆記(2)_svg實(shí)現(xiàn)不同投票不同表情

閱讀 671·2019-08-30 15:44
CSS里的BFC和IFC的用法

閱讀 3199·2019-08-30 10:51
自定義confirm提示框

閱讀 1597·2019-08-29 18:46
修改placeholder的樣式

閱讀 2749·2019-08-29 13:57

国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

一篇文章學(xué)會(huì)二叉樹和二叉查找樹

相關(guān)文章

**數(shù)據(jù)結(jié)構(gòu)-二叉樹和二叉查找樹**

**JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（九）二叉樹和二叉搜索樹**

學(xué)習(xí)javascript數(shù)據(jù)結(jié)構(gòu)(四)——樹

**js數(shù)據(jù)結(jié)構(gòu)-二叉樹（二叉搜索樹）**

發(fā)表評(píng)論

0條評(píng)論

BaronZhang

男|高級(jí)講師

TA的文章

Windows 11 安全配置基線設(shè)置的最終版本已發(fā)布

數(shù)據(jù)中心布線管理

介紹2個(gè)有趣的IoT的項(xiàng)目

電競(jìng)CSGO數(shù)據(jù)API接口 - 【聯(lián)賽列表】API調(diào)用示例代碼

好看漂亮的html5網(wǎng)頁(yè)特效學(xué)習(xí)筆記(2)_svg實(shí)現(xiàn)不同投票不同表情

CSS里的BFC和IFC的用法

自定義confirm提示框

修改placeholder的樣式

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

一篇文章學(xué)會(huì)二叉樹和二叉查找樹

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！