一、線性結(jié)構(gòu)

順序存儲線性表：將元素依次存儲在地址連續(xù)的存儲單元中，物理上相鄰；

鏈?zhǔn)酱鎯€性表：將元素按照邏輯順序鏈接在依次，不要求地址連續(xù)；

棧:僅在表的一端進(jìn)行插入、刪除操作的線性表，“后進(jìn)先出”；

隊列:僅在表的一端進(jìn)行插入，另一端進(jìn)行刪除的線性表，“先進(jìn)先出”

棧和隊列有時候筆試會針對”FIFO“這些特性出問題，不過一般理解了，就比較簡單。

二、樹

2.1概念

二叉樹是每個節(jié)點最多有兩個子樹（“左子樹”和“右子樹”）的樹結(jié)構(gòu)。

滿二叉樹：二叉樹的每一層節(jié)點個數(shù)都達(dá)到最大（即深度為k，且有2^k-1個節(jié)點）；

完全二叉樹：只有最下面兩層節(jié)點的度數(shù)可以小于2，并且最下一層的節(jié)點都集中在左邊（深度為k，有n個節(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個節(jié)點都與深度為k的滿二叉樹中，序號為1至n的節(jié)點對應(yīng)）。

滿二叉樹是完全二叉樹的特例，如下圖：

平衡二叉樹：又被稱為AVL樹，它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹（完全二叉樹是平衡二叉樹），如下圖

2.2二叉樹性質(zhì)：

• a.二叉樹的第i層至多有2^{i-1}個結(jié)點；
  

• b.深度為k的二叉樹至多有2^k-1個結(jié)點;
  

• c.具有n個節(jié)點的完全二叉樹的深度k=log2n+1；
  

• d.對任何一棵二叉樹T，若終端結(jié)點的個數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1。
  

2.3二叉樹遍歷

二叉樹遍歷記住一點就行了，即遍歷的順序都是針對根節(jié)點而言的。例如先序即先訪問根節(jié)點，再遍歷左子樹，最后遍歷右子樹。結(jié)合實例來講，如下圖：

先序遍歷結(jié)果：abdgcefh

中序遍歷結(jié)果：dgbaechf

后序遍歷結(jié)果：gdbehfca

三、圖

無向完全圖：任意兩個頂點都有一條直接邊相連接；在含有n個頂點的無向完全圖中，有n(n-1)/2條邊；

有向完全圖：任意兩個頂點都有方向互為相反的兩條弧相連接；在含有n個頂點的有向完全圖中，有n(n-1)條邊。

圖的深度優(yōu)先遍歷：類似于樹的先序遍歷，下圖顯示了深度優(yōu)先搜索頂點被訪問的順序：

圖的廣度優(yōu)先遍歷：類似于樹的按層次遍歷，下圖顯示了廣度優(yōu)先搜索頂點被訪問的順序：

總結(jié)

以上是生活随笔為你收集整理的基本数据结构概念的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。