數據結構-二叉樹和二叉查找樹

lindroid 發布于2019-08-23 12:15 / 2050人閱讀

摘要：樹是計算機科學中經常用到的一種數據結構數是一種非線性的數據結構以分層的方式存儲數據數被用來存儲具有層級關系的數據比如文件系統中的文件樹還被用來存儲有序列表本章將研究一種特殊的樹二叉樹選擇樹而不是那些基本的數據結構是因為在二叉樹上進行查找非常

樹是計算機科學中經常用到的一種數據結構. 數是一種非線性的數據結構, 以分層的方式存儲數據. 數被用來存儲具有層級關系的數據, 比如文件系統中的文件; 樹還被用來存儲有序列表. 本章將研究一種特殊的樹: 二叉樹 . 選擇樹而不是那些基本的數據結構, 是因為在二叉樹上進行查找非常快(而在鏈表中查找則不是這樣), 為二叉樹添加或刪除元素也非?？?而對數組執行添加或刪除則不是這樣).

樹的定義

樹是一組以邊連接的節點組成. 這里不做過多贅述. 深入了解點這里)
二叉樹 是一種特殊的樹, 它的子節點個數不超過兩個. 二叉樹具有一些特殊的計算性質, 使得它們之上的一些操作異常高效.

二叉樹和二叉查找樹

正如前面提到的那樣, 二叉樹 每一個節點的子節點不允許超過兩個. 通過將子節點的個數限定為2, 可以寫出高效的程序在樹中插入、查找和刪除數據.

在使用JS構建二叉樹之前, 需要給我們關于樹的詞典里再加兩個新名詞.

左節點: 一組特定的值.

右節點: 另一組特定的值.

當考慮某種特殊的二叉樹, 比如 二叉查找樹 時, 確定子節點非常重要.
二叉查找樹是一種特殊的二叉樹.

相對較小的值保存在左節點中.

較大的值保存在右節點中.

這一特性使得查找效率很高, 對于數值型和非數值型的數據, 比如單詞和字符串, 都是如此.

實現二叉查找樹

二叉查找樹由節點組成, 所以我們要定義的第一個對象就是Node, 該對象和前面介紹鏈表時的對象類似.
Node對象及保存數據, 也保存和其它節點的鏈接(left和right), show()方法用來顯示保存在節點中的數據.

創建BST類用來表示二叉查找樹. 我們讓類只包含一個數據成員: 一個表示二叉查找樹根節點的Node對象. 該類的構造函數將根節點初始化為null, 以此創建一個空節點.

BST先要有一個insert()方法, 用來向樹中加入新節點. 這個方法有點復雜, 需要著重講解. 首先要創建一個Node對象, 將數據傳入該對象保存.

其次檢查BST是否有根節點, 如果沒有, 那么這是棵新樹, 該節點就是根節點, 這個方法到此也就完成了; 否則進入下一步.

如果待插入節點不是根節點, 那么就需要準備遍歷BST, 找到插入的適當位置. 該過程類似于遍歷鏈表. 用一個變量存儲當前節點, 一層層地遍歷BST.

進入BST以后, 下一步就決定將節點放在哪個地方. 找到正確的插入點時, 會跳出循環. 查找正確插入點的算法如下:

設根節點為當前節點.

如果待插入節點保存的數據小于當前節點, 則設新的當前節點為原節點的左節點; 反之, 執行第4步.

如果當前節點的左節點為null, 就將新的節點插入這個位置, 退出循環; 反之, 繼續執行下一次循環.

設新的當前節點為源節點的右節點.

如果當前節點的右節點為null, 就將新的節點插入這個位置, 退出循環; 反之, 繼續執行下一次循環.

有了上面的算法, 就可以開始實現BST類了.

window.log = console.log.bind(console)

class Node {
    constructor(data, left = null, right = null) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
    show() {
        return this.data;
    }
};

class BST {
    constructor() {
        this.root = null;
    }
    insert(data) {
        const n = new Node(data);
        
        if(this.root === null) {
            this.root = n;
        } else {
            let current = this.root;
            let parent;
            while(true) {
                parent = current;
                if(data < current.data) {
                    current = current.left;
                    if(current === null) {
                        parent.left = n;
                        break;
                    }
                } else {
                    current = current.right;
                    if(current === null) {
                        parent.right = n;
                        break
                    }
                }
            }
        }
    }
    
};

遍歷二叉查找樹

現在BST類已經初步成型, 但是操作上還只能插入節點, 我們需要有能力遍歷BST, 這樣就可以按照不同順序, 比如按照數字大小或字母先后, 顯示節點上的數據.

有三種遍歷BST的方式:

中序: 按照節點上的鍵值, 以升序訪問BST上的所有節點.

先序: 先訪問根節點, 然后以同樣方式訪問左子樹和右子樹.

后序: 先訪問葉子節點, 從左子樹到右子樹, 再到根節點.

需要中序遍歷的原因顯而易見, 但為什么需要先序遍歷和后序遍歷就不是那么明顯了. 我們先來實現這三種遍歷方式, 在后序再解釋它們的用途.

中序遍歷使用遞歸方式最容易實現. 該方法需要以升序訪問樹中所有節點, 先訪問左子樹, 再訪問根節點, 最后訪問右子樹.

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

const bst = new BST();
bst.insert(4);
bst.insert(34);
bst.insert(43);
bst.insert(98);
bst.insert(71);
bst.insert(1);
inOrder(bst.root);

先序遍歷(preOrder())和中序遍歷(inOrder())方法的唯一區別, 就是if語句中代碼的順序.
在inOrder()方法中, show()函數像三明治一樣夾在兩個遞歸調用之間;
在preOrder()方法中, show()函數放在兩個遞歸調用之前.

function preOrder(node) {
    if (node !== null) {
        log(node.show() + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
};

后序遍歷postOrder():

function postOrder(node) {
    if (node !== null) {
        postOrder(node.left);
        postOrder(node.right);
        log(node.show() + " ");
    }
}

在二叉查找樹上進行查找

對BST通常有下列三種類型的查找:

查找給定值.

查找最小值.

查找最大值.

查找最小值和最大值

查找BST上的最小值和最大值非常簡單.
getMin()查找最小值, 因為較小的值總是在左子節點上, 只需要遍歷左子樹, 直到找到最后一個節點.

getMin() {
    let current = this.root;
    while (current.left !== null) {
        current = current.left;
    };

    return current.data;
}

getMax()查找最大值, 只需要遍歷右子樹, 直到找到最后一個節點, 該節點上保存的值即為最大值.

getMax() {
    let current = this.root;
    while (current.right !== null) {
        current = current.right;
    };

    return current.data;
}

測試:

const bst = new BST();
bst.insert(4);
bst.insert(34);
bst.insert(43);
bst.insert(98);
bst.insert(71);
bst.insert(1);
log("最小值: " + bst.getMin());
log("最大值: " + bst.getMax());

// 輸出:
// 最小值: 1
// 最大值: 98

這兩個方法返回最小值和最大值, 但有時, 我們希望方法返回存儲最小值和最大值的節點. 這很好實現, 只需要修改方法, 讓它返回當前節點, 而不是節點中存儲的數據即可.

查找給定值

在BST上查找給定值, 需要比較該值和當前節點上的值的大小. 通過比較, 就能確定如果給定值不在當前節點時, 該向左遍歷還是右遍歷.

find(data) {
    let current = this.root;
    while (current !== null) {
        if (current.data === data) {
            return current;
        } else if (data < current.data) {
            current = current.left;
        } else if (data > current.data) {
            current = current.right;
        }
    };

    return null;
}

從二叉查找樹上刪除節點

刪除節點的操作最復雜, 其復雜程度取決于刪除哪個節點. 如果刪除沒有子節點的節點, 那么非常簡單. 如果節點只有一個子節點, 不管是左子節點還是右子節點, 就變得稍微有點復雜了. 刪除包含兩個子節點的節點最復雜. 為了管理刪除操作的復雜度, 我們使用遞歸操作, 同時定義兩個方法: remove()和removeNode().

刪除節點的第一步是判斷當前節點是否包含帶刪除的數據.
如果包含, 則刪除節點;
如果不包含, 則比較當前節點上的數據和待刪除的數據

如果待刪除數據小于當前節點上的數據, 則移至當前節點的左子節點繼續比較;
如果待刪除數據大于當前節點上的數據, 則移至當前節點的右子節點繼續比較;

如果待刪除節點是葉子節點(沒有子節點的節點), 那么只需要將從父節點指向它的鏈接指向null.

如果待刪除節點只包含一個子節點, 那么原本指向它的節點就得做些調整, 使其指向它的子節點.

最后, 如果待刪除節點包含兩個子節點, 正確的做法有兩種:

查找待刪除節點左子樹上的最大值.

查找待刪除節點右子樹的最小值.

這里我們選擇后一種方式

我們需要一個查找子樹最小值的方法getSmallest(), 后面會用它找到最小值創建一個臨時節點. 將臨時節點上的值復制到待刪除節點, 然后再刪除臨時節點.

整個刪除過程由兩個方法完成. remove()方法只是簡單地接受待刪除數據, 調用removeNode()刪除它, 后者才是完成主要工作的方法.

window.log = console.log.bind(console)

class Node {
    constructor(data, left = null, right = null) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
    show() {
        return this.data;
    }
};

class BST {
    constructor() {
        this.root = null;
    }
    getMin() {
        let current = this.root;
        while (current.left !== null) {
            current = current.left;
        };

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

        return current.data;
    }
    find(data) {
        let current = this.root;
        while (current !== null) {
            if (current.data === data) {
                return current;
            } else if (data < current.data) {
                current = current.left;
            } else if (data > current.data) {
                current = current.right;
            }
        };

        return null;
    }
    remove(data) {
        this.root = removeNode(this.root, data);
    }
    insert(data) {
        const n = new Node(data);
        
        if(this.root === null) {
            this.root = n;
        } else {
            let current = this.root;
            let parent;
            while(true) {
                parent = current;
                if(data < current.data) {
                    current = current.left;
                    if(current === null) {
                        parent.left = n;
                        break;
                    }
                } else {
                    current = current.right;
                    if(current === null) {
                        parent.right = n;
                        break
                    }
                }
            }
        }
    }
    
};

function inOrder(node) {
    if (node !== null) {
        inOrder(node.left);
        log(node.show() + " ")
        inOrder(node.right)
    }
};
function preOrder(node) {
    if (node !== null) {
        log(node.show() + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
};
function postOrder(node) {
    if (node !== null) {
        postOrder(node.left);
        postOrder(node.right);
        log(node.show() + " ");
    }
};
function removeNode(node, data) {
    if (node === null) {
        return null;
    };
    if (data === node.data) {
        // 沒有子節點的節點
        if (node.left === null && node.right === null) {
            return null;
        };
        // 沒有左子節點的節點
        if (node.left === null) {
            return node.right;
        };
        // 沒有右子節點的節點
        if (node.right === null) {
            return node.left;
        };
        // 有兩個子節點的節點
        const tempNode = getSmallest(node.right);
        node.data = tempNode.data;
        node.right = removeNode(node.right, tempNode.data);
        return node;
    } else if (data < node.data) {
        node.left = removeNode(node.left, data);
        return node;
    } else {
        node.right = removeNode(node.right, data);
        return node;
    }
}

計數

BST的一個用途是記錄一組數據集中數據出現的次數. 比如, 可以使用BST記錄考試成績的分布. 給定一組考試成績, 可以寫一段程序將它們加入一個BST, 如果某成績尚未在BST中出現, 就將其加入BST; 如果已經出現, 就將出現的次數加1;

為了解決該問題, 我們來修改Node對象, 為其增加一個記錄成績出現頻次的成員, 同時我們還需要一個方法, 當在BST中發現某成績時, 需要將出現的次數加1, 并且更新該節點.

先修改Node對象的定義, 為其增加記錄成績出現次數的成員:

class Node {
    constructor(data, left = null, right = null) {
        this.data = data;
        this.count = 1;
        this.left = left;
        this.right = right;
    }
    show() {
        return this.data;
    }
};

當向BST插入一條成績(Node對象)時, 將出現頻次設為1. 此時BST的insert()方法還能正常工作, 但是, 當次數增加時, 我們就需要一個新方法來更新BST中的節點. 這個方法就是update().

完整程序:

window.log = console.log.bind(console)

class Node {
    constructor(data, left = null, right = null) {
        this.data = data;
        this.count = 1;
        this.left = left;
        this.right = right;
    }
    show() {
        return this.data;
    }
};

class BST {
    constructor() {
        this.root = null;
    }
    getMin() {
        let current = this.root;
        while (current.left !== null) {
            current = current.left;
        };

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

        return current.data;
    }
    find(data) {
        let current = this.root;
        while (current !== null) {
            if (current.data === data) {
                return current;
            } else if (data < current.data) {
                current = current.left;
            } else if (data > current.data) {
                current = current.right;
            }
        };

        return null;
    }
    update(data) {
        const grade = this.find(data);
        grade.count++;

        return grade;
    }
    remove(data) {
        this.root = removeNode(this.root, data);
    }
    insert(data) {
        const n = new Node(data);
        
        if(this.root === null) {
            this.root = n;
        } else {
            let current = this.root;
            let parent;
            while(true) {
                parent = current;
                if(data < current.data) {
                    current = current.left;
                    if(current === null) {
                        parent.left = n;
                        break;
                    }
                } else {
                    current = current.right;
                    if(current === null) {
                        parent.right = n;
                        break
                    }
                }
            }
        }
    }
    
};

function inOrder(node) {
    if (node !== null) {
        inOrder(node.left);
        log(node.show() + " ")
        inOrder(node.right)
    }
};
function preOrder(node) {
    if (node !== null) {
        log(node.show() + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
};
function postOrder(node) {
    if (node !== null) {
        postOrder(node.left);
        postOrder(node.right);
        log(node.show() + " ");
    }
};
function removeNode(node, data) {
    if (node === null) {
        return null;
    };
    if (data === node.data) {
        // 沒有子節點的節點
        if (node.left === null && node.right === null) {
            return null;
        };
        // 沒有左子節點的節點
        if (node.left === null) {
            return node.right;
        };
        // 沒有右子節點的節點
        if (node.right === null) {
            return node.left;
        };
        // 有兩個子節點的節點
        const tempNode = getSmallest(node.right);
        node.data = tempNode.data;
        node.right = removeNode(node.right, tempNode.data);
        return node;
    } else if (data < node.data) {
        node.left = removeNode(node.left, data);
        return node;
    } else {
        node.right = removeNode(node.right, data);
        return node;
    }
};

// 產生隨機成績
function genArray(length) {
    const arr = [];
    for(let i = 0; i < length; i++) {
        arr[i] = Math.floor(Math.random() * 101);
    };
    return arr;
};

const grades = genArray(100);
log(grades);

const bst = new BST();
grades.forEach(i => {
    const grade = bst.find(i);
    if (grade) {
        bst.update(i)
    } else {
        bst.insert(i)
    }
});

const aGrade = bst.find(33);
if (aGrade) {
    log(`33出現的次數為: ${aGrade.count}`)
} else {
    log(`未出現33`)
}

輸出:

(100)?[19, 85, 71, 52, 80, 3, 84, 13, 32, 20, 35, 10, 61, 54, 11, 49, 17, 6, 52, 66, 28, 7, 83, 71, 69, 84, 3, 2, 61, 12, 38, 97, 94, 10, 44, 14, 4, 69, 17, 10, 0, 28, 46, 74, 74, 18, 69, 70, 33, 32, 75, 81, 75, 52, 51, 34, 74, 75, 74, 0, 89, 71, 21, 28, 71, 42, 37, 92, 24, 39, 64, 75, 87, 46, 66, 37, 85, 55, 85, 21, 44, 16, 8, 81, 92, 72, 16, 4, 69, 32, 37, 48, 54, 91, 80, 57, 70, 88, 55, 32]
33出現的次數為: 1

GPU云服務器云服務器 c語言二叉樹輸入數據二叉樹遍歷二叉樹創建二叉樹算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/98181.html

一篇文章學會二叉樹和二叉查找樹

摘要：二叉樹和二叉查找樹一個父節點的兩個子節點分別稱為左節點和右節點。下圖展示了一顆二叉樹當考慮某種特殊的二叉樹，比如二叉查找樹時，確定子節點非常重要。實現二叉查找樹定義對象?，F在可以創建一個類來表示二叉查找樹。因此二叉查找樹也被叫做二叉排序樹。樹是計算機科學中經常用到的一種數據結構。樹是一種非線性的數據結構，以分層的方式存儲數據。樹被用來存儲具有層級關系的數據，比如文件系統中的文件。 ...

BaronZhang 2019-08-26 13:46 評論0 收藏0
JavaScript數據結構與算法（九）二叉樹和二叉搜索樹

摘要：二叉樹和二叉搜索樹二叉樹的節點最多只能有兩個節點，而二叉搜索樹只允許在左側的節點處存儲比父節點小的值，在右側節點存儲比父節點大的值。接收回調函數作為參數先序遍歷先序遍歷是以優先于后代節點的順序訪問沒和節點的。樹是一種非順序數據結構，對于存儲需要快速查找的數據非常有用。樹是一種分層數據的抽象模型，現實生活中最常見的例子就是家譜，或者是公司的組織架構圖。樹樹的相關術語 showImg...

zhaofeihao 2019-08-26 14:06 評論0 收藏0
每周一練之 數據結構與算法（Tree）

摘要：假設一個二叉搜索樹具有如下特征節點的左子樹只包含小于當前節點的數。所有左子樹和右子樹自身必須也是二叉搜索樹。代碼實現二叉樹節點定義來源驗證二叉搜索樹解析 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第六周的練習題，最近加班比較多，上周主要完成一篇 GraphQL入門教程，有興趣的小伙伴可以看下哈。 ...

zhonghanwen 2019-08-26 13:51 評論0 收藏0
每周一練之 數據結構與算法（Tree）

摘要：假設一個二叉搜索樹具有如下特征節點的左子樹只包含小于當前節點的數。所有左子樹和右子樹自身必須也是二叉搜索樹。代碼實現二叉樹節點定義來源驗證二叉搜索樹解析這是第六周的練習題，最近加班比較多，上周主要完成一篇 GraphQL入門教程，有興趣的小伙伴可以看下哈。下面是之前分享的鏈接： 1.每周一練之數據結構與算法（Stack） 2.每周一練之數據結構與算法（LinkedList） 3...

fizz 2019-05-22 11:25 評論0 收藏0

發表評論

登陸后可評論

0條評論

lindroid

男|高級講師

我要關注我要私信

TA的文章

tensorflow鏡像下載

閱讀 1392·2023-04-25 18:34
關于程序員的「年齡歧視」問題，程序員的年齡天花板難道是35歲嗎？

閱讀 3446·2021-11-19 09:40
MySQL-Front設置中文

閱讀 2832·2021-11-17 09:33
Python基礎（四）：數據類型

閱讀 2945·2021-11-12 10:36
Python3，68個內置庫函數詳解，進階必備，必須收藏！！!

閱讀 2836·2021-09-26 09:55
SpinServers：美國服務器促銷/2*e5-2630Lv2/64g內存/1.6T ssd/10

閱讀 2662·2021-08-05 10:03
HTML&&CSS基礎知識點整理

閱讀 2523·2019-08-30 15:54
CSS 圖像拼合技術（雪碧圖）

閱讀 2870·2019-08-30 15:54

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

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優惠，快來選購！

數據結構-二叉樹和二叉查找樹

相關文章

**一篇文章學會二叉樹和二叉查找樹**

**JavaScript數據結構與算法（九）二叉樹和二叉搜索樹**

**每周一練之數據結構與算法（Tree）**

**每周一練之數據結構與算法（Tree）**

發表評論

0條評論

lindroid

男|高級講師

TA的文章

tensorflow鏡像下載

關于程序員的「年齡歧視」問題，程序員的年齡天花板難道是35歲嗎？

MySQL-Front設置中文

Python基礎（四）：數據類型

Python3，68個內置庫函數詳解，進階必備，必須收藏！！!

SpinServers：美國服務器促銷/2*e5-2630Lv2/64g內存/1.6T ssd/10

HTML&&CSS基礎知識點整理

CSS 圖像拼合技術（雪碧圖）

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優惠，快來選購！

數據結構-二叉樹和二叉查找樹

相關文章

發表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務器低至59元/年，更有多臺、長期優惠，快來選購！