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

lindroid 發(fā)布于2019-08-23 12:15 / 2043人閱讀

摘要：樹是計(jì)算機(jī)科學(xué)中經(jīng)常用到的一種數(shù)據(jù)結(jié)構(gòu)數(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu)以分層的方式存儲(chǔ)數(shù)據(jù)數(shù)被用來(lái)存儲(chǔ)具有層級(jí)關(guān)系的數(shù)據(jù)比如文件系統(tǒng)中的文件樹還被用來(lái)存儲(chǔ)有序列表本章將研究一種特殊的樹二叉樹選擇樹而不是那些基本的數(shù)據(jù)結(jié)構(gòu)是因?yàn)樵诙鏄渖线M(jìn)行查找非常

樹是計(jì)算機(jī)科學(xué)中經(jīng)常用到的一種數(shù)據(jù)結(jié)構(gòu). 數(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu), 以分層的方式存儲(chǔ)數(shù)據(jù). 數(shù)被用來(lái)存儲(chǔ)具有層級(jí)關(guān)系的數(shù)據(jù), 比如文件系統(tǒng)中的文件; 樹還被用來(lái)存儲(chǔ)有序列表. 本章將研究一種特殊的樹: 二叉樹 . 選擇樹而不是那些基本的數(shù)據(jù)結(jié)構(gòu), 是因?yàn)樵诙鏄渖线M(jìn)行查找非常快(而在鏈表中查找則不是這樣), 為二叉樹添加或刪除元素也非常快(而對(duì)數(shù)組執(zhí)行添加或刪除則不是這樣).

樹的定義

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

二叉樹和二叉查找樹

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

在使用JS構(gòu)建二叉樹之前, 需要給我們關(guān)于樹的詞典里再加兩個(gè)新名詞.

左節(jié)點(diǎn): 一組特定的值.

右節(jié)點(diǎn): 另一組特定的值.

當(dāng)考慮某種特殊的二叉樹, 比如 二叉查找樹 時(shí), 確定子節(jié)點(diǎn)非常重要.
二叉查找樹是一種特殊的二叉樹.

相對(duì)較小的值保存在左節(jié)點(diǎn)中.

較大的值保存在右節(jié)點(diǎn)中.

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

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

二叉查找樹由節(jié)點(diǎn)組成, 所以我們要定義的第一個(gè)對(duì)象就是Node, 該對(duì)象和前面介紹鏈表時(shí)的對(duì)象類似.
Node對(duì)象及保存數(shù)據(jù), 也保存和其它節(jié)點(diǎn)的鏈接(left和right), show()方法用來(lái)顯示保存在節(jié)點(diǎn)中的數(shù)據(jù).

創(chuàng)建BST類用來(lái)表示二叉查找樹. 我們讓類只包含一個(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()方法, 用來(lái)向樹中加入新節(jié)點(diǎn). 這個(gè)方法有點(diǎn)復(fù)雜, 需要著重講解. 首先要?jiǎng)?chuàng)建一個(gè)Node對(duì)象, 將數(shù)據(jù)傳入該對(duì)象保存.

其次檢查BST是否有根節(jié)點(diǎn), 如果沒有, 那么這是棵新樹, 該節(jié)點(diǎn)就是根節(jié)點(diǎn), 這個(gè)方法到此也就完成了; 否則進(jìn)入下一步.

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

進(jìn)入BST以后, 下一步就決定將節(jié)點(diǎn)放在哪個(gè)地方. 找到正確的插入點(diǎn)時(shí), 會(huì)跳出循環(huán). 查找正確插入點(diǎn)的算法如下:

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

如果待插入節(jié)點(diǎn)保存的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn), 則設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的左節(jié)點(diǎn); 反之, 執(zhí)行第4步.

如果當(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)插入這個(gè)位置, 退出循環(huán); 反之, 繼續(xù)執(zhí)行下一次循環(huán).

有了上面的算法, 就可以開始實(shí)現(xiàn)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
                    }
                }
            }
        }
    }
    
};

遍歷二叉查找樹

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

有三種遍歷BST的方式:

中序: 按照節(jié)點(diǎn)上的鍵值, 以升序訪問BST上的所有節(jié)點(diǎn).

先序: 先訪問根節(jié)點(diǎn), 然后以同樣方式訪問左子樹和右子樹.

后序: 先訪問葉子節(jié)點(diǎn), 從左子樹到右子樹, 再到根節(jié)點(diǎn).

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

中序遍歷使用遞歸方式最容易實(shí)現(xiàn). 該方法需要以升序訪問樹中所有節(jié)點(diǎn), 先訪問左子樹, 再訪問根節(jié)點(diǎn), 最后訪問右子樹.

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())方法的唯一區(qū)別, 就是if語(yǔ)句中代碼的順序.
在inOrder()方法中, show()函數(shù)像三明治一樣夾在兩個(gè)遞歸調(diào)用之間;
在preOrder()方法中, show()函數(shù)放在兩個(gè)遞歸調(diào)用之前.

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() + " ");
    }
}

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

對(duì)BST通常有下列三種類型的查找:

查找給定值.

查找最小值.

查找最大值.

查找最小值和最大值

查找BST上的最小值和最大值非常簡(jiǎn)單.
getMin()查找最小值, 因?yàn)檩^小的值總是在左子節(jié)點(diǎn)上, 只需要遍歷左子樹, 直到找到最后一個(gè)節(jié)點(diǎn).

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

    return current.data;
}

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

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

    return current.data;
}

測(cè)試:

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

這兩個(gè)方法返回最小值和最大值, 但有時(shí), 我們希望方法返回存儲(chǔ)最小值和最大值的節(jié)點(diǎn). 這很好實(shí)現(xiàn), 只需要修改方法, 讓它返回當(dāng)前節(jié)點(diǎn), 而不是節(jié)點(diǎn)中存儲(chǔ)的數(shù)據(jù)即可.

查找給定值

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

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;
}

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

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

刪除節(jié)點(diǎn)的第一步是判斷當(dāng)前節(jié)點(diǎn)是否包含帶刪除的數(shù)據(jù).
如果包含, 則刪除節(jié)點(diǎn);
如果不包含, 則比較當(dāng)前節(jié)點(diǎn)上的數(shù)據(jù)和待刪除的數(shù)據(jù)

如果待刪除數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)上的數(shù)據(jù), 則移至當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)繼續(xù)比較;
如果待刪除數(shù)據(jù)大于當(dāng)前節(jié)點(diǎn)上的數(shù)據(jù), 則移至當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)繼續(xù)比較;

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

如果待刪除節(jié)點(diǎn)只包含一個(gè)子節(jié)點(diǎn), 那么原本指向它的節(jié)點(diǎn)就得做些調(diào)整, 使其指向它的子節(jié)點(diǎn).

最后, 如果待刪除節(jié)點(diǎn)包含兩個(gè)子節(jié)點(diǎn), 正確的做法有兩種:

查找待刪除節(jié)點(diǎn)左子樹上的最大值.

查找待刪除節(jié)點(diǎn)右子樹的最小值.

這里我們選擇后一種方式

我們需要一個(gè)查找子樹最小值的方法getSmallest(), 后面會(huì)用它找到最小值創(chuàng)建一個(gè)臨時(shí)節(jié)點(diǎn). 將臨時(shí)節(jié)點(diǎn)上的值復(fù)制到待刪除節(jié)點(diǎn), 然后再刪除臨時(shí)節(jié)點(diǎn).

整個(gè)刪除過程由兩個(gè)方法完成. remove()方法只是簡(jiǎn)單地接受待刪除數(shù)據(jù), 調(diào)用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) {
        // 沒有子節(jié)點(diǎn)的節(jié)點(diǎn)
        if (node.left === null && node.right === null) {
            return null;
        };
        // 沒有左子節(jié)點(diǎn)的節(jié)點(diǎn)
        if (node.left === null) {
            return node.right;
        };
        // 沒有右子節(jié)點(diǎn)的節(jié)點(diǎn)
        if (node.right === null) {
            return node.left;
        };
        // 有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
        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;
    }
}

計(jì)數(shù)

BST的一個(gè)用途是記錄一組數(shù)據(jù)集中數(shù)據(jù)出現(xiàn)的次數(shù). 比如, 可以使用BST記錄考試成績(jī)的分布. 給定一組考試成績(jī), 可以寫一段程序?qū)⑺鼈兗尤胍粋€(gè)BST, 如果某成績(jī)尚未在BST中出現(xiàn), 就將其加入BST; 如果已經(jīng)出現(xiàn), 就將出現(xiàn)的次數(shù)加1;

為了解決該問題, 我們來(lái)修改Node對(duì)象, 為其增加一個(gè)記錄成績(jī)出現(xiàn)頻次的成員, 同時(shí)我們還需要一個(gè)方法, 當(dāng)在BST中發(fā)現(xiàn)某成績(jī)時(shí), 需要將出現(xiàn)的次數(shù)加1, 并且更新該節(jié)點(diǎn).

先修改Node對(duì)象的定義, 為其增加記錄成績(jī)出現(xiàn)次數(shù)的成員:

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

當(dāng)向BST插入一條成績(jī)(Node對(duì)象)時(shí), 將出現(xiàn)頻次設(shè)為1. 此時(shí)BST的insert()方法還能正常工作, 但是, 當(dāng)次數(shù)增加時(shí), 我們就需要一個(gè)新方法來(lái)更新BST中的節(jié)點(diǎn). 這個(gè)方法就是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) {
        // 沒有子節(jié)點(diǎn)的節(jié)點(diǎn)
        if (node.left === null && node.right === null) {
            return null;
        };
        // 沒有左子節(jié)點(diǎn)的節(jié)點(diǎn)
        if (node.left === null) {
            return node.right;
        };
        // 沒有右子節(jié)點(diǎn)的節(jié)點(diǎn)
        if (node.right === null) {
            return node.left;
        };
        // 有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
        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;
    }
};

// 產(chǎn)生隨機(jī)成績(jī)
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出現(xiàn)的次數(shù)為: ${aGrade.count}`)
} else {
    log(`未出現(xiàn)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出現(xiàn)的次數(shù)為: 1