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

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

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

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

樹的定義

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

二叉樹和二叉查找樹

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

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

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

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

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

相對較小的值保存在左節(jié)點中.

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

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

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

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

創(chuàng)建BST類用來表示二叉查找樹. 我們讓類只包含一個數(shù)據(jù)成員: 一個表示二叉查找樹根節(jié)點的Node對象. 該類的構(gòu)造函數(shù)將根節(jié)點初始化為null, 以此創(chuàng)建一個空節(jié)點.

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

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

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

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

設(shè)根節(jié)點為當前節(jié)點.

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

如果當前節(jié)點的左節(jié)點為null, 就將新的節(jié)點插入這個位置, 退出循環(huán); 反之, 繼續(xù)執(zhí)行下一次循環(huán).

設(shè)新的當前節(jié)點為源節(jié)點的右節(jié)點.

如果當前節(jié)點的右節(jié)點為null, 就將新的節(jié)點插入這個位置, 退出循環(huán); 反之, 繼續(xù)執(zhí)行下一次循環(huán).

有了上面的算法, 就可以開始實現(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é)點, 我們需要有能力遍歷BST, 這樣就可以按照不同順序, 比如按照數(shù)字大小或字母先后, 顯示節(jié)點上的數(shù)據(jù).

有三種遍歷BST的方式:

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

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

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

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

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

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語句中代碼的順序.
在inOrder()方法中, show()函數(shù)像三明治一樣夾在兩個遞歸調(diào)用之間;
在preOrder()方法中, show()函數(shù)放在兩個遞歸調(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() + " ");
    }
}

在二叉查找樹上進行查找

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

查找給定值.

查找最小值.

查找最大值.

查找最小值和最大值

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

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

    return current.data;
}

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

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

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

查找給定值

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

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é)點

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

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

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

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

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

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

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

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

這里我們選擇后一種方式

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

整個刪除過程由兩個方法完成. remove()方法只是簡單地接受待刪除數(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é)點的節(jié)點
        if (node.left === null && node.right === null) {
            return null;
        };
        // 沒有左子節(jié)點的節(jié)點
        if (node.left === null) {
            return node.right;
        };
        // 沒有右子節(jié)點的節(jié)點
        if (node.right === null) {
            return node.left;
        };
        // 有兩個子節(jié)點的節(jié)點
        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;
    }
}

計數(shù)

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

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

先修改Node對象的定義, 為其增加記錄成績出現(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;
    }
};

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

GPU云服務(wù)器云服務(wù)器 c語言二叉樹輸入數(shù)據(jù) 二叉樹遍歷二叉樹創(chuàng)建二叉樹算法

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/98181.html

發(fā)表評論

登陸后可評論

0條評論

lindroid

男|高級講師

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

TA的文章

tensorflow鏡像下載

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

閱讀 3463·2021-11-19 09:40
MySQL-Front設(shè)置中文

閱讀 2840·2021-11-17 09:33
Python基礎(chǔ)（四）：數(shù)據(jù)類型

閱讀 2960·2021-11-12 10:36
Python3，68個內(nèi)置庫函數(shù)詳解，進階必備，必須收藏！！!

閱讀 2843·2021-09-26 09:55
SpinServers：美國服務(wù)器促銷/2*e5-2630Lv2/64g內(nèi)存/1.6T ssd/10

閱讀 2666·2021-08-05 10:03
HTML&&CSS基礎(chǔ)知識點整理

閱讀 2530·2019-08-30 15:54
CSS 圖像拼合技術(shù)（雪碧圖）

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

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

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

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

相關(guān)文章

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

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

**每周一練之數(shù)據(jù)結(jié)構(gòu)與算法（Tree）**

**每周一練之數(shù)據(jù)結(jié)構(gòu)與算法（Tree）**

發(fā)表評論

0條評論

lindroid

男|高級講師

TA的文章

tensorflow鏡像下載

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

MySQL-Front設(shè)置中文

Python基礎(chǔ)（四）：數(shù)據(jù)類型

Python3，68個內(nèi)置庫函數(shù)詳解，進階必備，必須收藏！！!

SpinServers：美國服務(wù)器促銷/2*e5-2630Lv2/64g內(nèi)存/1.6T ssd/10

HTML&&CSS基礎(chǔ)知識點整理

CSS 圖像拼合技術(shù)（雪碧圖）

最新活動

資訊專欄INFORMATION COLUMN

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

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

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

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