一、樹狀結構
1、陣列與連結串列
陣列結構
陣列儲存是透過下標方式訪問元素,查詢速度快,如果陣列元素是有序的,還可使用二分查詢提高檢索速度;如果新增新元素可能會導致多個下標移動,效率較低;
連結串列結構
連結串列儲存元素,對於元素新增和刪除效率高,但是遍歷元素每次都需要從頭結點開始,效率特別低;
樹形結構能同時相對提高資料儲存和讀取的效率。
2、樹結構概念
根節點:樹的根源,沒有父節點的節點,如上圖A節點;
兄弟節點:擁有同一父節點的子節點。如圖B與C點;
葉子節點:沒有子節點的節點。如圖DEFG節點;
樹的高度:最大層數,如圖為3層;
路徑:從root根節點找到指定節點的路線;
樹形結構是一層次的巢狀結構。一個樹形結構的外層和內層有相似的結構,所以這種結構多可以遞迴的表示。經典資料結構中的各種樹狀圖是一種典型的樹形結構:一顆樹可以簡單的表示為根,左子樹,右子樹。 左子樹和右子樹又有自己的子樹。
二、二叉樹模型
樹的種類有很多,二叉樹(BinaryTree)是樹形結構的一個重要型別,每個節點最多隻能有兩個子節點的一種形式稱為二叉樹,二叉樹的子節點分為左節點和右節點,許多實際問題抽象出來的資料結構往往是二叉樹形式。
完全二叉樹
二叉樹的所有葉子節點都在最後一層或者倒數第二層,而且最後一層的葉子節點在左邊連續,倒數第二 層的葉子節點在右邊連續,我們稱為完全二叉樹
滿二叉樹
當二叉樹的所有葉子節點都在最後一層,並且結點總數= 2^n -1 , n 為層數,則稱為滿二叉樹。
平衡二叉樹
平衡二叉樹指的是,任意節點的子樹的高度差的絕對值都小於等於1,並且左右兩個子樹都是一棵平衡二叉樹,常見的符合平衡樹的有,B樹(多路平衡搜尋樹)、AVL樹(二叉平衡搜尋樹)等。
二叉查詢樹
二叉查詢樹(BinarySearchTree)不但二叉樹,同時滿足一定的有序性:節點的左子節點比自己小,節點的右子節點比自己大。
三、多叉樹
多叉樹是指一個父節點可以有多個子節點,但是一個子節點依舊遵循一個父節點定律,通常情況下,二叉樹的實際應用高度太高,可以透過多叉樹來簡化對資料關係的描述。
例如:Linux檔案系統,組織架構關係,角色選單許可權管理系統等,通常都基於多叉樹來描述。