今天給大家開始介紹前端方面的數據結構，剛把vue源碼過完就開始數據結構，可見它的地位有多重要。有人說我一前端又不是后端學這個數據結構干嘛，好吧，只能說你還沒有這個意識，一是面試很多大廠就會考察，我面試別人也會出一些簡單算法題來做，以此考察邏輯能力以及js基礎能力。二是當你寫邏輯方面代碼時候，明明可以一層for循環搞定，非要三層for循環，這里就凸顯巧用數據結構的好處了。閑話不多說，直接上來二分搜索。

一 二分搜索

所謂二分查找，就是在有序表中，每次都讓被查找數據與當前表的中間結點進行比較，根據比較結果“舍棄”掉以中間結點劃分的某一半子表。

總結出來它的基本邏輯: 優先和數組的中間元素比較，如果等于中間元素，則直接返回。如果不等于則取半繼續查找。

適用場景：假設現在有一個數組，數組中的數據按照某個關鍵字排好了序，現在我們希望判斷某個數據是否已存在于數組中，怎么樣做才更快？

總結出來它的適應場景： 數組 有序

基本二分查找有 非遞歸版本 和 遞歸版本

非遞歸版本

遞歸版本

由上的方法我們可以總結出二分查找的幾個特點:

1 每次我們都將表的大小減半，也就是除以二 ;

2 最壞情況下我們要一直“除以2”直到表只剩下一個元素;

3 二分查找花費的時間關鍵點就是比較了多少次，而比較的次數在最壞情況下就是表的大小n不斷除以2直至n為1的次數。這樣以來我們很快就能得出二分查找的時間復雜度：O(log2N) ;

那如果我們想要表的大小能夠動態的變化，并且數據具有層級用什么來表示呢？沒錯，二叉樹。

在樹結構中，每一個結點只有一個前件，稱為父結點，沒有前件的結點只有一個，稱為樹的根結點，簡稱樹的根（root）。每一個結點可以有多個后件，稱為該結點的子結點。沒有后件的結點稱為葉子結點。一個結點所擁有的子結點的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。

同時，我們還可以看到一些基本的樹的特點：

每個節點的鍵值大于左孩子，每個節點的鍵值大于右孩子。以左右孩子為根的子樹仍然為二分搜索樹。

二叉樹是一種特殊的樹，它的子節點個數不超過兩個，且分別稱為該結點的左子樹（left subtree）與右子樹（right subtree），二叉樹常被用作二叉查找樹和二叉堆或是二叉排序樹（BST）。

二 二叉樹的插入

那么現在我們就用javascript來時實現一個簡單的二叉搜索樹。

首先我們創建一個Node類，用于存放樹的節點。首先要添加新的節點，首先需要創建一個Node對象，將數據傳入該對象。 其次要檢查當前的BST樹是否有根節點，如果沒有，那么表示是一棵新數，該節點就為該樹的根節點，那么插入這個過程就結束了；否則，就要繼續進行下一步了。 如果待插入節點不是根節點，那么就必須對BST進行遍歷，找到合適的位置。該過程類似遍歷鏈表，用一個變量存儲當前節點，一層一層遍歷BST，算法如下：

設值當前節點為根節點

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

如果當前節點的左節點為null，就將新節點放到這個位置，退出循環；反之，繼續執行下一次循環

設置新節點為原節點的右節點

如果當前節點的右節點為null，就將新節點放到這個位置，退出循環；反之，繼續執行下一次循環

這樣，就能保證每次添加的新節點能夠放到正確的位置上.

三 二插樹的查找

查找通常分為三種情況 查找最小值 查找最大值 查找定值

1 查找定值：

如果找到就返回該值，未找到就返回null；

2 查找最小值

3 查找最大值

三 二叉樹 的循環遍歷

循環遍歷分為 前序遍歷 中序遍歷 后序遍歷

我們首先構造一個樹

1 前序遍歷

2 中序遍歷

3 后序遍歷

4 廣度優先遍歷

四 二叉樹 刪除節點

刪除節點的思路大致如下：

首先判斷當前節點是否包含待刪除的數據，如果包含，則刪除該節點；如果不包含，則比較當前節點上的數據和待刪除樹的的大小關系。如果待刪除的數據小于當前節點的數據，則移至當前節點的左子節點繼續比較；如果大于，則移至當前節點的右子節點繼續比較。 如果待刪除節點是葉子節點（沒有子節點），那么只需要將從父節點指向它的鏈接指向變為null； 如果待刪除節點含有一個子節點，那么原本指向它的節點需要做調整，使其指向它的子節點； 最后，如果待刪除節點包含兩個子節點，可以選擇查找待刪除節點左子樹上的最大值或者查找其右子樹上的最小值，這里我們選擇后一種。

至此，我們基本操作方法已經分析完了，快來動手實踐下吧。

總結

以上是生活随笔為你收集整理的vue 怎么样不重复往数组里插入数据_前端数据结构与算法(1) -二分查找vs二叉树...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。