ps：最近想學(xué)英語冗美，如果哪位朋友有全英文書籍想要賣（最好難度不大@-@），可以私聊我状答，收購。

----------超長(zhǎng)文預(yù)警刀崖，需要花費(fèi)大量時(shí)間----------

今天整理《數(shù)據(jù)結(jié)構(gòu)與算法-JavaScript描述》中所講的數(shù)據(jù)結(jié)構(gòu)惊科。

1、數(shù)組

數(shù)組.png

2、列表

在日常生活中蜡娶，人們經(jīng)常使用列表:待辦事項(xiàng)列表混卵、購物清單、十佳榜單窖张、最后十名榜單 等幕随。計(jì)算機(jī)程序也在使用列表，尤其是列表中保存的元素不是太多時(shí)宿接。當(dāng)不需要在一個(gè)很 長(zhǎng)的序列中查找元素赘淮，或者對(duì)其進(jìn)行排序時(shí)，列表顯得尤為有用睦霎。反之梢卸，如果數(shù)據(jù)結(jié)構(gòu)非 常復(fù)雜，列表的作用就沒有那么大了碎赢。

不包含任何元素的列表稱為空列表低剔。列表中包含元素的個(gè)數(shù)稱為列表的 length速梗。在內(nèi)部實(shí) 現(xiàn)上肮塞，用一個(gè)變量 listSize 保存列表中元素的個(gè)數(shù)∫鏊可以在列表末尾 append 一個(gè)元素枕赵， 也可以在一個(gè)給定元素后或列表的起始位置 insert 一個(gè)元素。使用 remove 方法從列表中 刪除元素位隶，使用 clear 方法清空列表中所有的元素拷窜。還可以使用 toString() 方法顯示列表中所有的元素，使用 getElement() 方法顯示當(dāng)前元素涧黄。

列表擁有描述元素位置的屬性篮昧。列表有前有后(分別對(duì)應(yīng) front 和 end)。使用 next() 方 法可以從當(dāng)前元素移動(dòng)到下一個(gè)元素笋妥，使用 prev() 方法可以移動(dòng)到當(dāng)前元素的前一個(gè)元 素懊昨。還可以使用 moveTo(n) 方法直接移動(dòng)到指定位置，這里的 n 表示要移動(dòng)到第 n 個(gè)位置春宣。 currPos 屬性表示列表中的當(dāng)前位置酵颁。

JavaScript實(shí)現(xiàn)列表

    // 列表
    function List(){
            this.listSize = 0; // 列表的元素個(gè)數(shù)
            this.pos = 0; //列表的當(dāng)前位置
            this.dataStore = [];//初始化一個(gè)空數(shù)組來保存列表元素
            // length:列表中有多少個(gè)元素
            this.length = function(){
                return this.listSize;
            };
            // clear:清空列表中所有的元素
            this.clear = function(){
                delete this.dataStore;
                this.dataStore = [];
                this.listSize = this.pos = 0;
            };
            // 判斷元素是否在當(dāng)前列表中，如果在返回元素下標(biāo)月帝，不在返回-1
            this.find = function(element){
                for(var i = 0 ; i < this.dataStore.length ; i++){
                    if(this.dataStore[i] == element){
                        return i;
                    }
                }
                return -1;
            };
            // 顯示列表中的元素
            this.toString = function(){
                return this.dataStore;
            };
            // insert:在element元素后面插入after元素
            this.insert = function(element,after){
                var insertPos = this.find(after);
                if(insertPos > -1){
                    this.dataStore.splice(insertPos+1,0,element);
                    this.listSize++;
                    return true;
                }
                return false;
            };
            // append：在列表末尾插入一個(gè)元素
            this.append = function(element){
                this.dataStore[this.listSize++] = element;
            };
            // remove：從列表中刪除元素
            this.remove = function(element){
                var foundAt = this.find(element);
                if (foundAt > -1){
                    this.dataStore.splice(foundAt,1)
                    this.listSize--;
                    return true;
                }
                return false;
            };
            // front：將列表的當(dāng)前位置設(shè)移動(dòng)到第一個(gè)元素
            this.front = function(){
                return this.pos = 0;
            };
            // getElement：返回當(dāng)前位置的元素
            this.getElement = function() {
                return this.dataStore[this.pos]
            };
            // contains:判斷給定值是否在列表中
            this.contains = function(element){
                for (var i = 0 ; i < this.dataStore.length ; i++){
                    if(this.dataStore[i] == element){
                        return true;
                    }
                }
                return false
            };
            // 最后一組方法允許用戶在列表上自由移動(dòng)
            // 將列表的當(dāng)前位置移動(dòng)到最后一個(gè)元素
            this.end = function(){
                return this.pos = this.listSize-1;
            };
            // 將當(dāng)前位置后移一位
            this.prev = function(){
                if(this.pos>0){
                    return this.pos--;
                }
            };
            // 將當(dāng)前位置前移一位
            this.next = function(){
                if(this.pos < this.listSize-1){
                    return ++this.pos;
                }else{
                    return this.pos = this.listSize;
                }
            };
            // 返回列表的當(dāng)前位置
            this.currPos = function(){
                return this.pos;
            };
            // 將當(dāng)前位置移動(dòng)到指定位置
            this.moveTo = function(position){
                return this.pos = position;
            };
        }

// 測(cè)試
    var names = new List();
    names.append("Clayton");
    names.append("Raymond");
    names.append("Cynthia");
    names.append("Jennifer");
    names.append("Bryan");
    names.append("Danny");

    console.log(names.toString()) 
    //["Clayton", "Raymond", "Cynthia", "Jennifer", "Bryan", "Danny"]   
    console.log(names.listSize) //6 
    console.log(names.find('Danny')) // 5
    console.log(names.insert('Luckfine','Jennifer')) // true
    console.log(names.toString()) 
    //["Clayton", "Raymond", "Cynthia", "Jennifer", "Luckfine", "Bryan", "Danny"]
    console.log(names.listSize) //7
    console.log(names.remove('Luckfine')) //true
    console.log(names.toString()) 
    //["Clayton", "Raymond", "Cynthia", "Jennifer", "Bryan", "Danny"]
    console.log(names.listSize) //6

    console.log(names.front()) // 0
    console.log(names.getElement()) // Clayton    
    console.log(names.next())// 1
    console.log(names.getElement()) //Raymond

    console.log(names.moveTo(4))
    console.log(names.getElement())//Bryan
    console.log(names.currPos()) //4

    console.log(names.end()) //5
    console.log(names.getElement()) //Danny

小案例：使用列表管理實(shí)現(xiàn)影碟租賃

// 使用列表管理影碟租賃
var movies = ['《肖申克的救贖》','《教父》','《低俗小說》','《黃金三鏢客','《十二怒漢》','《辛德勒名單》','《黑暗騎士》','《指環(huán)王:王者歸來》','《搏擊俱樂部》','《星球大戰(zhàn) 5:帝國(guó)反擊戰(zhàn)》','《飛越瘋?cè)嗽骸?,'《指環(huán)王:護(hù)戒使者》','《盜夢(mèng)空間》','《好家伙》','《星球大戰(zhàn)》','《黑客帝國(guó)》','《阿甘正傳》','《上帝之城》']

var movieList = new List();
var customers = new List();

for (var i = 0; i < movies.length; ++i) {
    movieList.append(movies[i]);
}

// displayList函數(shù)來顯示影碟店里現(xiàn)有的影碟清單
function displayList(list) {
    for (list.front(); list.currPos() < list.length(); list.next()) {
        // 如果傳進(jìn)來的是顧客借閱的書躏惋，那就顯示借閱者和借閱的影碟
        if (list.getElement() instanceof Customer) {
            console.log(list.getElement()["name"] + ", " +
                list.getElement()["movie"]);
        } else {
            console.log(list.getElement());
        }
    }
}
// 用來存已經(jīng)借閱的客戶和影碟
function Customer(name, movie) {
    this.name = name;
    this.movie = movie;
}
// 借閱影碟
function checkOut(name, movie, filmList, customerList) {
    if (movieList.contains(movie)) {
        var c = new Customer(name, movie); 
        customerList.append(c); 
        filmList.remove(movie);
    } else {
        console.log(movie + " is not available.");
    }
}
// 歸還影碟
function checkIn(name, movie, filmList, customerList) {
    // console.log([name, movie])
    for (customers.front(); customers.currPos() < customers.length(); customers.next()) {
        // 在借閱列表中判斷有無歸還的影碟，如果有嚷辅，將其移除
        if(customers.getElement()["name"]==name && customers.getElement()["movie"]==movie){
            customers.remove(customers.getElement())
            filmList.append(movie);
        }else{
            console.log(movie + " is not available.");
        }
    }
}

console.log(checkOut('Luckfine','《星球大戰(zhàn)》',movieList,customers))
console.log(checkOut('Luckfine','《肖申克的救贖》',movieList,customers))
console.log(checkIn('Luckfine','《肖申克的救贖》',movieList,customers))
console.log(customers.toString())
console.log(displayList(customers))

3簿姨、棧

棧是一種特殊的列表，棧內(nèi)的元素只能通過列表的一端訪問簸搞，這一端稱為棧頂扁位∩盍龋咖啡廳內(nèi) 的一摞盤子是現(xiàn)實(shí)世界中常見的棧的例子。只能從最上面取盤子贤牛，盤子洗凈后惋鹅，也只能摞 在這一摞盤子的最上面。棧被稱為一種后入先出(LIFO殉簸，last-in-first-out)的數(shù)據(jù)結(jié)構(gòu)闰集。

由于棧具有后入先出的特點(diǎn)，所以任何不在棧頂?shù)脑囟紵o法訪問般卑。為了得到棧底的元 素武鲁，必須先拿掉上面的元素。

JavaScript實(shí)現(xiàn)棧

    function Stack() {
        this.dataStore = []; // 保存棧內(nèi)元素
        this.top = 0; //變量top記錄棧頂位置 初始化為0
        //向棧內(nèi)壓入新元素
        this.push = function(element){
            return this.dataStore[this.top++] = element;
        }; 
        //它返回棧頂元素蝠检，同時(shí)將變量 top 的值減 1
        this.pop = function(){
            return this.dataStore[--this.top];
        };
        //返回?cái)?shù)組的第 top-1 個(gè)位置的元素沐鼠，即棧頂元素
        this.peek = function(){
            return this.dataStore[this.top-1];
        }; 
        //clear() 方法 清除棧內(nèi)所有元素
        this.clear = function(){
            return this.top = 0;
        };
        //length 屬性記錄棧內(nèi)元素的個(gè)數(shù)
        this.length = function(){
            return this.top;
        };
    }

    // 測(cè)試stack類的實(shí)現(xiàn)
    var s = new Stack();
    s.push("David");
    s.push("Raymond");
    s.push("Bryan");
    console.log(s.length())
    console.log(s.peek());
    console.log(s.pop())
    console.log(s.length())
    s.clear();
    console.log(s.length());


    // 判定給定的字符串是否是回文
    function isPalindrome(word) {
        var s = new Stack();
        for (var i = 0; i < word.length; ++i) {
            s.push(word[i]);
        }
        var rword = "";
        while (s.length() > 0) {
            rword += s.pop();
        }
        if (word == rword) {
            return true;
        }else {
            return false;
        }
    }

    console.log(isPalindrome('hello')); //false 
    console.log(isPalindrome('helleh')); //true

4、隊(duì)列

隊(duì)列是一種列表叹谁，不同的是隊(duì)列只能在隊(duì)尾插入元素饲梭，在隊(duì)首刪除元素。隊(duì)列用于存儲(chǔ)按 順序排列的數(shù)據(jù)焰檩，先進(jìn)先出憔涉，這點(diǎn)和棧不一樣，在棧中析苫，最后入棧的元素反而被優(yōu)先處 理兜叨。可以將隊(duì)列想象成在銀行前排隊(duì)的人群衩侥，排在最前面的人第一個(gè)辦理業(yè)務(wù)国旷，新來的人 只能在后面排隊(duì)，直到輪到他們?yōu)橹埂?/p>

隊(duì)列是一種先進(jìn)先出(First-In-First-Out茫死，F(xiàn)IFO)的數(shù)據(jù)結(jié)構(gòu)跪但。隊(duì)列被用在很多地方，比如 提交操作系統(tǒng)執(zhí)行的一系列進(jìn)程璧榄、打印任務(wù)池等特漩，一些仿真系統(tǒng)用隊(duì)列來模擬銀行或雜貨 店里排隊(duì)的顧客。

JavaScript實(shí)現(xiàn)隊(duì)列

    // 使用數(shù)組來實(shí)現(xiàn)隊(duì)列看起來順理成章骨杂。JavaScript 中的數(shù)組具有其他編程語言中沒有的優(yōu)點(diǎn)涂身， 數(shù)組的 push() 方法可以在數(shù)組末尾加入元素，shift() 方法則可刪除數(shù)組的第一個(gè)元素搓蚪。

    function Queue() {
        this.dataStore = [];
        // enqueue() 方法向隊(duì)尾添加一個(gè)元素:
        this.enqueue = function(element){
            return this.dataStore.push(element);
        };
        // dequeue() 方法刪除隊(duì)首的元素
        this.dequeue = function(){
            return this.dataStore.shift();
        };
        // 讀取隊(duì)首
        this.front = function(){
            return this.dataStore[0];
        };
        // 讀取隊(duì)尾
        this.back = function(){
            return this.dataStore[this.dataStore.length-1];
        };
        // toString() 方法顯示隊(duì)列內(nèi)的所有元素
        this.toString = function(){
            var retStr = "";
            for (var i = 0; i < this.dataStore.length; ++i) {
                retStr += this.dataStore[i] + "\n";
            }
            return retStr;
        };
        // 判斷隊(duì)列是否為空:
        this.empty = function(){
            if (this.dataStore.length == 0) {
                return true;
            } else {
                return false;
            }
        };
    }   
    var q = new Queue();
    q.enqueue("Meredith");
    q.enqueue("Cynthia");
    q.enqueue("Jennifer");
    console.log(q.toString())//Meredith Cynthia Jennifer
    q.dequeue();
    console.log(q.toString())//Cynthia Jennifer
    console.log(q.front())//Cynthia
    console.log(q.back())//Jennifer
    console.log(q.enqueue('Luckfine'))
    console.log(q.toString()) //Cynthia Jennifer Luckfine

5蛤售、鏈表

鏈表是由一組節(jié)點(diǎn)組成的集合。每個(gè)節(jié)點(diǎn)都使用一個(gè)對(duì)象的引用指向它的后繼。指向另一 個(gè)節(jié)點(diǎn)的引用叫做鏈悴能。

數(shù)組元素靠它們的位置進(jìn)行引用揣钦，鏈表元素則是靠相互之間的關(guān)系進(jìn)行引用。在圖 6-1 中漠酿， 我們說 bread 跟在 milk 后面冯凹，而不說 bread 是鏈表中的第二個(gè)元素。遍歷鏈表炒嘲，就是跟著 鏈接宇姚，從鏈表的首元素一直走到尾元素(但這不包含鏈表的頭節(jié)點(diǎn)，頭節(jié)點(diǎn)常常用來作為 鏈表的接入點(diǎn))夫凸。圖中另外一個(gè)值得注意的地方是浑劳，鏈表的尾元素指向一個(gè) null 節(jié)點(diǎn)。

鏈表中插入一個(gè)節(jié)點(diǎn)的效率很高夭拌。向鏈表中插入一個(gè)節(jié)點(diǎn)魔熏，需要修改它前面的節(jié)點(diǎn)(前 驅(qū))，使其指向新加入的節(jié)點(diǎn)鸽扁，而新加入的節(jié)點(diǎn)則指向原來前驅(qū)指向的節(jié)點(diǎn)蒜绽。圖 6-3 演示了 如何在 eggs 后加入 cookies。

從鏈表中刪除一個(gè)元素也很簡(jiǎn)單献烦。將待刪除元素的前驅(qū)節(jié)點(diǎn)指向待刪除元素的后繼節(jié)點(diǎn)滓窍，同時(shí)
將待刪除元素指向 null卖词，元素就刪除成功了巩那。圖 6-4 演示了從鏈表中刪除“bacon”的過程。

JavaScript實(shí)現(xiàn)鏈表

    function Node(element) {
        this.element = element;//element 用來保存節(jié)點(diǎn)上的數(shù)據(jù)
        this.next = null;//next 用來保存指向下一個(gè)節(jié)點(diǎn)的鏈接
    }
    function LList() {
        this.head = new Node("head"); 
        // 遍歷鏈表此蜈，查找給定數(shù)據(jù)即横。如果找到數(shù)據(jù)，該方法就返回保存該數(shù)據(jù)的節(jié)點(diǎn)裆赵。
        // find() 方法演示了如何在鏈表上進(jìn)行移動(dòng)东囚。首先，創(chuàng)建一個(gè)新節(jié)點(diǎn)战授，并將鏈表的頭節(jié)點(diǎn)賦 給這個(gè)新創(chuàng)建的節(jié)點(diǎn)页藻。然后在鏈表上進(jìn)行循環(huán)，如果當(dāng)前節(jié)點(diǎn)的 element 屬性和我們要找 的信息不符植兰，就從當(dāng)前節(jié)點(diǎn)移動(dòng)到下一個(gè)節(jié)點(diǎn)份帐。如果查找成功，該方法返回包含該數(shù)據(jù)的 節(jié)點(diǎn);否則楣导，返回 null废境。
        this.find = function(item){
            var currNode = this.head;
            while (currNode.element != item) {
               currNode = currNode.next;
            }
            return currNode;
        };
        //  insert():向鏈表中插入一個(gè)節(jié)點(diǎn)
        // 該方法向鏈表中插入一個(gè)節(jié)點(diǎn)。向鏈表中插入新節(jié)點(diǎn) 時(shí)，需要明確指出要在哪個(gè)節(jié)點(diǎn)前面或后面插入噩凹。一旦找到“后面”的節(jié)點(diǎn)巴元，就可以將新節(jié)點(diǎn)插入鏈表了。首先驮宴，將新節(jié)點(diǎn)的 next 屬性設(shè) 置為“后面”節(jié)點(diǎn)的 next 屬性對(duì)應(yīng)的值逮刨。然后設(shè)置“后面”節(jié)點(diǎn)的 next 屬性指向新節(jié)點(diǎn)。
        this.insert = function(newElement, item){
            var newNode = new Node(newElement); 
            var current = this.find(item); 
            newNode.next = current.next; 
            current.next = newNode;
        }; 
        // 從鏈表中刪除節(jié)點(diǎn)時(shí)堵泽，需要先找到待刪除節(jié)點(diǎn)前面的節(jié)點(diǎn)禀忆。找到這個(gè)節(jié)點(diǎn)后，修改它的 next 屬性落恼，使其不再指向待刪除節(jié)點(diǎn)箩退，而是指向待刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。
        this.remove = function(item){
            var prevNode = this.findPrevious(item);
            if (!(prevNode.next == null)) {
                prevNode.next = prevNode.next.next;
            }
        }; 
        this.display = function(){
            var currNode = this.head;
            while (!(currNode.next == null)) {
               console.log(currNode.next.element);
               currNode = currNode.next;
            }
        };
        this.findPrevious = function(item){
            var currNode = this.head;
            while (!(currNode.next == null) && (currNode.next.element != item)) {
                currNode = currNode.next;
            }
            return currNode;        
        }
    }
    var cities = new LList();
    cities.insert("Conway", "head");
    cities.insert("Russellville", "Conway");
    cities.insert("Alma", "Russellville");
    cities.display()//Conway  Russellville  Alma
    cities.remove("Carlisle")
    cities.display();//Russellville  Alma

雙向鏈表

盡管從鏈表的頭節(jié)點(diǎn)遍歷到尾節(jié)點(diǎn)很簡(jiǎn)單佳谦，但反過來干发，從后向前遍歷則沒那么簡(jiǎn)單破婆。通過 給 Node 對(duì)象增加一個(gè)屬性，該屬性存儲(chǔ)指向前驅(qū)節(jié)點(diǎn)的鏈接，這樣就容易多了掩幢。此時(shí)向鏈 表插入一個(gè)節(jié)點(diǎn)需要更多的工作，我們需要指出該節(jié)點(diǎn)正確的前驅(qū)和后繼唧席。但是在從鏈表 中刪除節(jié)點(diǎn)時(shí)钾军，效率提高了，不需要再查找待刪除節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)了窗怒。圖 6-5 演示了雙向 鏈表的工作原理映跟。

雙向鏈表的 remove() 方法比單向鏈表的效率更高，因?yàn)椴恍枰俨檎仪膀?qū)節(jié)點(diǎn)了扬虚。首先需 要在鏈表中找出存儲(chǔ)待刪除數(shù)據(jù)的節(jié)點(diǎn)努隙，然后設(shè)置該節(jié)點(diǎn)前驅(qū)的 next 屬性，使其指向待刪 除節(jié)點(diǎn)的后繼;設(shè)置該節(jié)點(diǎn)后繼的 previous 屬性辜昵，使其指向待刪除節(jié)點(diǎn)的前驅(qū)荸镊。

JavaScript實(shí)現(xiàn)雙向鏈表

function Node(element) {
    this.element = element;
    this.next = null;
    this.previous = null;
 }
 function LList() {
    this.head = new Node("head"); 
    this.find = function(item){
        var currNode = this.head;
        while (currNode.element != item) {
            currNode = currNode.next;
        }
        return currNode;
    };
    //雙向鏈表的 insert() 方法和單向鏈表的類似，但是需要設(shè)置新節(jié)點(diǎn)的 previous 屬性堪置，使 其指向該節(jié)點(diǎn)的前驅(qū)躬存。
    this.insert = function(newElement,item){
        var newNode = new Node(newElement); 
        var current = this.find(item); 
        newNode.next = current.next; 
        newNode.previous = current; 
        current.next = newNode;
    }; 
    this.display = function(){
        var currNode = this.head;
        while (!(currNode.next == null)) {
            console.log(currNode.next.element);
            currNode = currNode.next;
        }
    };
    this.dispReverse = function(){
        var currNode = this.head;
        currNode = this.findLast();
        while (!(currNode.previous == null)) {
            console.log(currNode.element);
            currNode = currNode.previous;
        }
    }; 
    this.findLast = function(){
        var currNode = this.head;
        while (!(currNode.next == null)) {
            currNode = currNode.next;
        }
        return currNode;
    }
    this.remove = function(item){
        var currNode = this.find(item); 
        if (!(currNode.next == null)) {
            currNode.previous.next = currNode.next;
            currNode.next.previous = currNode.previous;
            currNode.next = null;
            currNode.previous = null;
        }
    };
 }

var cities = new LList();
cities.insert("Conway", "head");
cities.insert("Russellville", "Conway");
cities.insert("Carlisle", "Russellville");
cities.insert("Alma", "Carlisle");
cities.display();//Conway  Russellville  Carlisle Alma

循環(huán)鏈表

如果你希望可以從后向前遍歷鏈表，但是又不想付出額外代價(jià)來創(chuàng)建一個(gè)雙向鏈表舀锨，那么
就需要使用循環(huán)鏈表岭洲。從循環(huán)鏈表的尾節(jié)點(diǎn)向后移動(dòng)，就等于從后向前遍歷鏈表雁竞。

循環(huán)鏈表和單向鏈表相似钦椭，節(jié)點(diǎn)類型都是一樣的拧额。唯一的區(qū)別是，在創(chuàng)建循環(huán)鏈表時(shí)彪腔，讓
其頭節(jié)點(diǎn)的 next 屬性指向它本身侥锦，即: head.next = head

只需要修改一處，就將單向鏈表變成了循環(huán)鏈表德挣。但是其他一些方法需要修改才能工作正 常恭垦。比如，display() 就需要修改格嗅，原來的方式在循環(huán)鏈表里會(huì)陷入死循環(huán)番挺。while 循環(huán)的 循環(huán)條件需要修改，需要檢查頭節(jié)點(diǎn)屯掖，當(dāng)循環(huán)到頭節(jié)點(diǎn)時(shí)退出循環(huán)玄柏。

循環(huán)鏈表的 display() 方法如下所示:

     function display() {
        var currNode = this.head;
        while (!(currNode.next == null) &&
               !(currNode.next.element == "head")) {
           print(currNode.next.element);
           currNode = currNode.next;
} }

知道了怎么修改 display() 方法，就應(yīng)該會(huì)修改其他方法了贴铜。

6粪摘、字典

字典是一種以鍵 - 值對(duì)形式存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，就像電話號(hào)碼簿里的名字和電話號(hào)碼一 樣绍坝。要找一個(gè)電話時(shí)徘意，先找名字，名字找到了轩褐，緊挨著它的電話號(hào)碼也就找到了椎咧。這里的 鍵是指你用來查找的東西，值是查找得到的結(jié)果把介。

JavaScript實(shí)現(xiàn)字典

    function Dictionary() {
        this.datastore = new Array();
        // add()：該方法接受兩個(gè)參數(shù):鍵和值勤讽。鍵是值在字典中的索引。
        this.add = function(key, value){
            this.datastore[key] = value;
            this.datastore.length++;
            console.log(this.datastore)
        };
        // find()：該方法以鍵作為參數(shù)劳澄，返回和其關(guān)聯(lián)的值地技。
        this.find = function(key){
            return this.datastore[key];
        };
        // remove():刪除一組鍵值對(duì)
        this.remove = function(key){
            delete this.datastore[key];
            this.datastore.length--;
        };
        // 顯示字典中所有的鍵 - 值對(duì)
        this.showAll = function(){
            for(var key in this.datastore) {
                console.log(key,this.datastore[key]);
            }
        };
        // 字典中的元素個(gè)數(shù)
        this.count = function(){
            return this.datastore.length;
        };
        // 清空字典
        this.clear = function(){
            for(var key in this.datastore) {
                delete this.datastore[key];
                this.datastore.length--;
            }
        }
    }
    var pbook = new Dictionary(); 
    pbook.add("Mike","123");
    pbook.add("David", "345");
    pbook.add("Cynthia", "456");
    pbook.showAll();
    pbook.remove("Cynthia");
    console.log(pbook.count());//2
    pbook.clear();
    console.log(pbook.count());//0

7、散列

散列是一種常用的數(shù)據(jù)存儲(chǔ)技術(shù)秒拔，散列后的數(shù)據(jù)可以快速地插入或取用。散列使用的數(shù)據(jù) 結(jié)構(gòu)叫做散列表飒硅。在散列表上插入砂缩、刪除和取用數(shù)據(jù)都非常快三娩，但是對(duì)于查找操作來說卻 效率低下庵芭，比如查找一組數(shù)據(jù)中的最大值和最小值。

我們的散列表是基于數(shù)組進(jìn)行設(shè)計(jì)的雀监。數(shù)組的長(zhǎng)度是預(yù)先設(shè)定的双吆，如有需要眨唬，可以隨時(shí)增 加。所有元素根據(jù)和該元素對(duì)應(yīng)的鍵好乐，保存在數(shù)組的特定位置匾竿，該鍵和我們前面講到的字 典中的鍵是類似的概念。使用散列表存儲(chǔ)數(shù)據(jù)時(shí)蔚万，通過一個(gè)散列函數(shù)將鍵映射為一個(gè)數(shù) 字岭妖，這個(gè)數(shù)字的范圍是 0 到散列表的長(zhǎng)度。

理想情況下反璃，散列函數(shù)會(huì)將每個(gè)鍵值映射為一個(gè)唯一的數(shù)組索引昵慌。然而，鍵的數(shù)量是無限 的淮蜈，數(shù)組的長(zhǎng)度是有限的(理論上斋攀，在 JavaScript 中是這樣)，一個(gè)更現(xiàn)實(shí)的目標(biāo)是讓散列 函數(shù)盡量將鍵均勻地映射到數(shù)組中梧田。

即使使用一個(gè)高效的散列函數(shù)蜻韭，仍然存在將兩個(gè)鍵映射成同一個(gè)值的可能，這種現(xiàn)象稱為 碰撞(collision)柿扣，當(dāng)碰撞發(fā)生時(shí)肖方，我們需要有方案去解決。

要確定的最后一個(gè)問題是:散列表中的數(shù)組究竟應(yīng)該有多大?這是編寫散列函數(shù)時(shí)必須要 考慮的未状。對(duì)數(shù)組大小常見的限制是:數(shù)組長(zhǎng)度應(yīng)該是一個(gè)質(zhì)數(shù)俯画。

先說針對(duì)字符串的散列，乍一看司草，將字符串中每個(gè)字符的 ASCII 碼值相加似乎是一個(gè)不錯(cuò)的散列函數(shù)艰垂。這樣散列值就是 ASCII 碼值的和除以數(shù)組長(zhǎng)度的余數(shù)。

為了避免碰撞埋虹，首先要確保散列表中用來存儲(chǔ)數(shù)據(jù)的數(shù)組其大小是個(gè)質(zhì)數(shù)猜憎。這一點(diǎn)很關(guān) 鍵，這和計(jì)算散列值時(shí)使用的取余運(yùn)算有關(guān)搔课。數(shù)組的長(zhǎng)度應(yīng)該在 100 以上胰柑，這是為了讓數(shù) 據(jù)在散列表中分布得更加均勻。通過試驗(yàn)我們發(fā)現(xiàn)爬泥，比 100 大且不會(huì)讓例 8-1 中的數(shù)據(jù)產(chǎn) 生碰撞的第一個(gè)質(zhì)數(shù)是 137柬讨。使用其他更接近 100 的質(zhì)數(shù)，在該數(shù)據(jù)集上依然會(huì)產(chǎn)生碰撞袍啡。

為了避免碰撞踩官，在給散列表一個(gè)合適的大小后，接下來要有一個(gè)計(jì)算散列值的更好方法境输。 霍納算法很好地解決了這個(gè)問題蔗牡。本書不會(huì)過多深入該算法的數(shù)學(xué)細(xì)節(jié)颖系，在此算法中，新 的散列函數(shù)仍然先計(jì)算字符串中各字符的 ASCII 碼值辩越，不過求和時(shí)每次要乘以一個(gè)質(zhì)數(shù)嘁扼。 大多數(shù)算法書建議使用一個(gè)較小的質(zhì)數(shù)，比如 31区匣，但是對(duì)于我們的數(shù)據(jù)集偷拔，31 不起作用， 我們使用 37亏钩，這樣剛好不會(huì)產(chǎn)生碰撞莲绰。

綜上，用JavaScript實(shí)現(xiàn)字符串的散列

function HashTable(){
    // 創(chuàng)建一個(gè)長(zhǎng)度為137的數(shù)組
    this.table = new Array(137);
    // 為了避免碰撞姑丑，在給散列表一個(gè)合適的大小后蛤签，接下來要有一個(gè)計(jì)算散列值的更好方法。 霍納算法很好地解決了這個(gè)問題栅哀。本書不會(huì)過多深入該算法的數(shù)學(xué)細(xì)節(jié)震肮，在此算法中，新 的散列函數(shù)仍然先計(jì)算字符串中各字符的 ASCII 碼值留拾，不過求和時(shí)每次要乘以一個(gè)質(zhì)數(shù)戳晌。 大多數(shù)算法書建議使用一個(gè)較小的質(zhì)數(shù)，比如 31痴柔，但是對(duì)于我們的數(shù)據(jù)集沦偎，31 不起作用， 我們使用 37咳蔚，這樣剛好不會(huì)產(chǎn)生碰撞豪嚎。
    this.betterHash = function(string){
        const H = 37;
        var total = 0;
        for (var i = 0; i < string.length; ++i) {
            total += H * total + string.charCodeAt(i);
        }
        total = total % this.table.length;
        if (total < 0) {
            total += this.table.length-1;
        }
        return parseInt(total);
    };
    // 顯示散列中的所有數(shù)據(jù)
    this.showDistro = function(){
        var n = 0;
        for (var i = 0; i < this.table.length; ++i) { 
            if (this.table[i] != undefined) {
                console.log(i + ": " + this.table[i]);
            }
        }
    };
    // 向散列中添加數(shù)據(jù)
    this.put = function(data){
        var pos = this.betterHash(data);
        this.table[pos] = data;
    };

}

    var someNames = ["David", "Jennifer", "Donnie", "Raymond",
    "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
    var hTable = new HashTable();
    for (var i = 0; i < someNames.length; ++i) {
        hTable.put(someNames[i]);
    }
    hTable.showDistro();

結(jié)果：

碰撞處理：
當(dāng)散列函數(shù)對(duì)于多個(gè)輸入產(chǎn)生同樣的輸出時(shí)，就產(chǎn)生了碰撞谈火。

1侈询、開鏈法：當(dāng)碰撞發(fā)生時(shí)，我們?nèi)匀幌Ｍ麑㈡I存儲(chǔ)到通過散列算法產(chǎn)生的索引位置上糯耍，但實(shí)際上扔字，不 可能將多份數(shù)據(jù)存儲(chǔ)到一個(gè)數(shù)組單元中。開鏈法是指實(shí)現(xiàn)散列表的底層數(shù)組中谍肤，每個(gè)數(shù)組 元素又是一個(gè)新的數(shù)據(jù)結(jié)構(gòu)啦租，比如另一個(gè)數(shù)組，這樣就能存儲(chǔ)多個(gè)鍵了荒揣。使用這種技術(shù)， 即使兩個(gè)鍵散列后的值相同焊刹，依然被保存在同樣的位置系任，只不過它們?cè)诘诙€(gè)數(shù)組中的位 置不一樣罷了恳蹲。

2、線性探測(cè)法：線性探測(cè)法隸屬于一種更一般化的散列技術(shù):開放 尋址散列俩滥。當(dāng)發(fā)生碰撞時(shí)嘉蕾，線性探測(cè)法檢查散列表中的下一個(gè)位置是否為空。如果為空霜旧， 就將數(shù)據(jù)存入該位置;如果不為空错忱，則繼續(xù)檢查下一個(gè)位置，直到找到一個(gè)空的位置為 止挂据。該技術(shù)是基于這樣一個(gè)事實(shí):每個(gè)散列表都會(huì)有很多空的單元格以清，可以使用它們來存 儲(chǔ)數(shù)據(jù)。

當(dāng)存儲(chǔ)數(shù)據(jù)使用的數(shù)組特別大時(shí)崎逃，選擇線性探測(cè)法要比開鏈法好掷倔。這里有一個(gè)公式，常常 可以幫助我們選擇使用哪種碰撞解決辦法:如果數(shù)組的大小是待存儲(chǔ)數(shù)據(jù)個(gè)數(shù)的 1.5 倍个绍， 那么使用開鏈法;如果數(shù)組的大小是待存儲(chǔ)數(shù)據(jù)的兩倍及兩倍以上時(shí)勒葱，那么使用線性探 測(cè)法。

8巴柿、集合

集合(set)是一種包含不同元素的數(shù)據(jù)結(jié)構(gòu)凛虽。集合中的元素稱為成員。集合的兩個(gè)最重 要特性是:首先广恢，集合中的成員是無序的;其次凯旋，集合中不允許相同成員存在。

下面是一些使用集合時(shí)必須了解的定義袁波。
? 不包含任何成員的集合稱為空集瓦阐，全集則是包含一切可能成員的集合。
? 如果兩個(gè)集合的成員完全相同篷牌，則稱兩個(gè)集合相等睡蟋。
? 如果一個(gè)集合中所有的成員都屬于另外一個(gè)集合，則前一集合稱為后一集合的子集枷颊。

對(duì)集合的基本操作有下面幾種戳杀。
? 并集 將兩個(gè)集合中的成員進(jìn)行合并，得到一個(gè)新集合夭苗。
? 交集 兩個(gè)集合中共同存在的成員組成一個(gè)新的集合信卡。
? 補(bǔ)集 屬于一個(gè)集合而不屬于另一個(gè)集合的成員組成的集合。

JavaScript實(shí)現(xiàn)集合

    function Set() {
        // 用數(shù)組去保存集合
        this.dataStore = [];
        // 向集合中添加數(shù)據(jù)
        this.add = function(data){
            if (this.dataStore.indexOf(data) < 0) {
                this.dataStore.push(data);
                return true;
            } else {
                return false;
            }
        };
        // 從集合中刪除數(shù)據(jù)
        this.remove = function(){
            var pos = this.dataStore.indexOf(data);
            if (pos > -1) {
                this.dataStore.splice(pos,1);
                return true;
            } else {
                return false;
            }
        };
        // 集合長(zhǎng)度
        this.size = function(){
            return this.dataStore.length;
        };
        // 并集
        this.union = function(set){
            var tempSet = new Set();
            for (var i = 0; i < this.dataStore.length; ++i) {
                tempSet.add(this.dataStore[i]);
            }
            for (var i = 0; i < set.dataStore.length; ++i) {
                if (!tempSet.contains(set.dataStore[i])) {
                    tempSet.dataStore.push(set.dataStore[i]);
                }
            }
            return tempSet
        };
        // 交集
        this.intersect = function(set){
            var tempSet = new Set();
            for (var i = 0; i < this.dataStore.length; ++i) {
                if (set.contains(this.dataStore[i])) {
                    tempSet.add(this.dataStore[i]);
                } 
            }
            return tempSet;
        };
        // 子集
        this.subset = function(set){
            if (this.size() > set.size()) {
                return false;
            } else {
                for (var i = 0 ; i < this.dataStore.length; i++){
                    if (!set.contains(this.dataStore[i])) {
                        return false;
                    } 
                }
            }
            return true
        };
        // 補(bǔ)集
        this.difference = function(set){
            var tempSet = new Set();
            for (var i = 0; i < this.dataStore.length; ++i) {
                if (!set.contains(this.dataStore[i])) {
                    tempSet.add(this.dataStore[i]);
                } 
            }
            return tempSet;
        };
        // 顯示集合中的所有數(shù)據(jù)
        this.show = function(){
            return this.dataStore;
        };
        // 判斷集合中是否包含某個(gè)元素
        this.contains = function (data){
            if (this.dataStore.indexOf(data) > -1) {
                return true;
            }
            else {
                return false;
            }
        }
    }
    var cis = new Set(); 
    cis.add("Raymond");
    cis.add("Cynthia"); 
    var dmp = new Set(); 
    dmp.add("Raymond"); 
    dmp.add("Cynthia"); 
    dmp.add("Bryan");
    console.log(cis.subset(dmp)); //true

9题造、二叉樹和二叉查找樹

樹是計(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ǔ) 有序列表牵触。本章將研究一種特殊的樹:二叉樹。選擇樹而不是那些基本的數(shù)據(jù)結(jié)構(gòu)咐低，是因 為在二叉樹上進(jìn)行查找非忱克迹快(而在鏈表上查找則不是這樣)，為二叉樹添加或刪除元素 也非臣粒快(而對(duì)數(shù)組執(zhí)行添加或刪除操作則不是這樣)

一棵樹最上面的節(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)徐钠。

二叉樹是一種特殊的樹，它的子節(jié)點(diǎn)個(gè)數(shù)不超過兩個(gè)役首。

從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的這一組邊稱為路徑尝丐，在圖中用虛線表示。以某種特定順序 訪問樹中所有的節(jié)點(diǎn)稱為樹的遍歷衡奥。

二叉查找樹是一種 特殊的二叉樹爹袁，相對(duì)較小的值保存在左節(jié)點(diǎn)中，較大的值保存在右節(jié)點(diǎn)中矮固。這一特性使得 查找的效率很高失息，對(duì)于數(shù)值型和非數(shù)值型的數(shù)據(jù)，比如單詞和字符串档址，都是如此盹兢。

JavaScript實(shí)現(xiàn)二叉查找樹(注意看注釋)

// Node 對(duì)象既保存數(shù)據(jù)，也保存和其他節(jié)點(diǎn)的鏈接(left 和 right)守伸，show() 方法用來顯示 保存在節(jié)點(diǎn)中的數(shù)據(jù)绎秒。
function Node(data,left,right){
    this.data = data;
    this.count = 1;
    this.left = left;
    this.right = right;
    this.show = function(){
        return console.log(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)蠢涝。
function BST(){
    this.root = null;
    // 用來向樹中加入新節(jié)點(diǎn)
    // 檢查 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钳宪。
    // (1) 設(shè)根節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)揭北。
    // (2) 如果待插入節(jié)點(diǎn)保存的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)，則設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的左節(jié)點(diǎn);反
    // 之吏颖，執(zhí)行第 4 步搔体。
    // (3) 如果當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)為 null，就將新的節(jié)點(diǎn)插入這個(gè)位置半醉，退出循環(huán);反之疚俱，繼續(xù)
    // 執(zhí)行下一次循環(huán)。
    // (4) 設(shè)新的當(dāng)前節(jié)點(diǎn)為原節(jié)點(diǎn)的右節(jié)點(diǎn)缩多。
    // (5) 如果當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)為 null呆奕，就將新的節(jié)點(diǎn)插入這個(gè)位置，退出循環(huán);反之衬吆，繼續(xù)
    // 執(zhí)行下一次循環(huán)梁钾。
    this.insert = function(data){
        var n = new Node(data, null, null);
        if (this.root == null) {
            this.root = n;
        } else {
            var current = this.root;
            var 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; 
                    }
                } 
            }
        }
    };
    // 中序遍歷的訪問路徑
    // 中序遍歷按照節(jié)點(diǎn)上的鍵值，以升序訪問 BST 上的所有節(jié)點(diǎn)逊抡。先序遍歷先訪問根節(jié)點(diǎn)姆泻，然后以同樣方式訪問左子樹和右子樹。后序 遍歷先訪問葉子節(jié)點(diǎn)冒嫡，從左子樹到右子樹拇勃，再到根節(jié)點(diǎn)。
    this.inOrder = function(node){
        if(!(node == null)){
            this.inOrder(node.left);
            node.show();
            this.inOrder(node.right);
        }
    };
    // 先序遍歷
    // 注意 inOrder() 和 preOrder() 方法的唯一區(qū)別孝凌，就是 if 語句中代碼的順序方咆。在 inOrder() 方法中，show() 函數(shù)像三明治一樣夾在兩個(gè)遞歸調(diào)用之間;在 preOrder() 方法中胎许，show() 函數(shù)放在兩個(gè)遞歸調(diào)用之前峻呛。
    this.preOrder = function(node){
        if(!(node == null)){
            node.show();
            this.inOrder(node.left);
            this.inOrder(node.right);
        }
    }
    // 后序遍歷
    this.postOrder = function(node){
        if(!(node == null)){
            this.inOrder(node.left);
            this.inOrder(node.right);
            node.show();
        }
    }
    // 查找最小值
    // 查找 BST 上的最小值和最大值非常簡(jiǎn)單。因?yàn)檩^小的值總是在左子節(jié)點(diǎn)上辜窑，在 BST 上查找最小值钩述，只需要遍歷左子樹，直到找到最后一個(gè)節(jié)點(diǎn)穆碎。
    this.getMin = function(){
        var current = this.root;
        while (!(current.left == null)) {
            current = current.left;
        }
        return current.data;
    }
    // 查找最大值
    // 在 BST 上查找最大值牙勘，只需要遍歷右子樹，直到找到最后一個(gè)節(jié)點(diǎn)，該節(jié)點(diǎn)上保存的值即 為最大值方面。
    this.getMax = function(){
        var current = this.root;
        while (!(current.right == null)) {
            current = current.right;
        }
        return current.data;
    }
    // 查找給定值
    // 在 BST 上查找給定值放钦，需要比較該值和當(dāng)前節(jié)點(diǎn)上的值的大小。通過比較恭金，就能確定如果給定值不在當(dāng)前節(jié)點(diǎn)時(shí)操禀，該向左遍歷還是向右遍歷。
    this.find = function(data){
        var current = this.root;
        while (current != null) {
            if (current.data == data) {
                return current;
            } else if (data < current.data) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return null;
    }
    // 從二叉查找樹上刪除節(jié)點(diǎn)
    // 從 BST 中刪除節(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)左子樹 上的最大值，要么查找其右子樹上的最小值垂睬。
    this.remove = function(data){
        root = this.removeNode(this.root,data)
    }
    this.removeNode = function(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)
            var 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。
    // 為了解決該問題蝌借，我們來修改 Node 對(duì)象昔瞧，為其增加一個(gè)記錄成績(jī)出現(xiàn)頻次的成員，同時(shí)我 們還需要一個(gè)方法菩佑，當(dāng)在 BST 中發(fā)現(xiàn)某成績(jī)時(shí)自晰，需要將出現(xiàn)的次數(shù)加 1，并且更新該節(jié)點(diǎn)稍坯。
    this.update = function update(data){
        var grade = this.find(data); 
        grade.count++;
        return grade;
    }
}
    var nums = new BST();
    nums.insert(23);
    nums.insert(45);
    nums.insert(16);
    nums.insert(37);
    nums.insert(3);
    nums.insert(99);
    nums.insert(99);
    nums.insert(22);
    // console.log("Inorder traversal: ");
    // nums.inOrder(nums.root);
    // nums.preOrder(nums.root)
    nums.postOrder(nums.root);
    console.log(nums.getMin());
    console.log(nums.getMax());
    console.log(nums.find(23));
    console.log(nums.update(99))
    console.log(nums.removeNode(99))
    console.log(nums.update(99))

10酬荞、圖和圖算法

后續(xù)。

整理不易，且看且珍惜混巧。