# 基本數據結構與算法(樹)

MarlonBrando1998 2022-01-08 04:57:04 阅读数:256

基本 算法

基本數據結構與算法(樹)

樹的前中後序遍曆

  • 定義樹的數據結構
class TreeNode {

/** * 節點存放的值 */
int val;
/** * 左節點 */
TreeNode left;
/** * 右節點 */
TreeNode right;
TreeNode(int val) {

this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {

this.val = val;
this.left = left;
this.right = right;
}
}
前序:根 左 右
  • 遞歸方式
public List<Integer> preorderTraversal(TreeNode root) {

if (root != null) {

list.add(root.val);
if (root.left != null) {

preorderTraversal(root.left);
}
if (root.right != null) {

preorderTraversal(root.right);
}
}
return list;
}
  • 用棧操作
public List<Integer> preorderTraversal(TreeNode root) {

Stack<TreeNode> treeNodes = new Stack<>();
List<Integer> list = new ArrayList<>();
if (Objects.nonNull(root)) {

treeNodes.push(root);
}
while (!treeNodes.isEmpty()) {

// 獲取節點並且出棧
TreeNode head = treeNodes.pop();
list.add(head.val);
if (Objects.nonNull(head.left)) {

treeNodes.push(head.left);
}
if (Objects.nonNull(head.right)) {

treeNodes.push(head.right);
}
}
return list;
}
中序:左 根 右
List<Integer> list = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {

if (root != null) {

if (root.left != null) {

inorderTraversal(root.left);
}
list.add(root.val);
if (root.right != null) {

inorderTraversal(root.right);
}
}
return list;
}
  • 用棧操作
public List<Integer> inorderTraversal(TreeNode root) {

Stack<TreeNode> treeNodes = new Stack<>();
List<Integer> list = new ArrayList<>();
while (root!=null || !treeNodes.isEmpty()) {

// 當節點不為空的時候,當前節點入棧,當前節點為左節點
while (root!=null){

treeNodes.push(root);
root = root.left;
}
// 獲取節點並且出棧
root = treeNodes.pop();
list.add(root.val);
root = root.right;
}
return list;
}
  • 測試樹組裝
@Test
public void test() {

// 左節點
TreeNode left = null;
TreeNode node2 = new TreeNode(3, null, null);
// 右節點
TreeNode node1 = new TreeNode(2, node2, null);
TreeNode treeNode = new TreeNode(1, left, node1);
List<Integer> list = inorderTraversal(treeNode);
System.out.println(list);
}
後序:左 右 根
public List<Integer> postorderTraversal(TreeNode root) {

if (root != null) {

if (root.left != null) {

preorderTraversal(root.left);
}
if (root.right != null) {

preorderTraversal(root.right);
}
list.add(root.val);
}
return list;
}

二叉樹

​ 每個節點至多擁有兩棵子樹的樹結構。二叉樹中不存在度大於二的節點。

存儲結構
struct node{

int data; //數據域
struct node *left; // 樹的左節點
struct node *right; // 樹的右節點
}

滿二叉樹

​ 所有的非葉子節點都有2個葉子節點,深度為k且有2^(k+1)-1個節點的二叉樹。滿二叉樹一定是完全二叉樹,但是完全二叉樹不一定是滿二叉樹。

完全二叉樹

​ 完全二叉樹從根結點到倒數第二層滿足完美二叉樹,最後一層可以不完全填充,其葉子結點都靠左對齊。

二叉排序樹

​ 是數據結構中的一類。在一般情况下,查詢效率比鏈錶結構要高。

特點
  • 若左子樹不為空,則左子樹的所有節點都小於根節點。
  • 若右子樹不為空,則右子樹的所有節點都大於根節點。
  • 左右子樹也分別為二叉排序樹。
  • 沒有鍵值相等的節點。
建立二叉排序樹
public TreeNode doOne(int[] arr){

// 假設數組中的第一個元素為根節點
TreeNode node = new TreeNode(arr[0]);
for (int num : arr) {

insertNode(node,num);
}
return node;
}
private TreeNode insertNode(TreeNode node, int num) {

// 判斷 node.left 或者 node.right 是否為空 , 如果是空節點則新建節點
if(Objects.isNull(node)){

node = new TreeNode(num);
}else {

int val = node.val;
// 處理左邊的所有節點
if (num < val) {

node.left = insertNode(node.left, num);
} else {

node.right = insertNode(node.right, num);
}
}
return node;
}

紅黑樹

​ 紅黑樹是一種特殊的平衡二叉樹,插入和删除操作的時候保持二叉樹平衡,從而獲得更高的查找性能。紅黑樹查找的時間複雜度是O(logn)。

圖片來自:https://www.toutiao.com/a6584714397543825927/?channel=&source=search_tab

在這裏插入圖片描述

紅黑樹特點
  • 節點是紅色或者黑色。
  • 根節點是黑色。
  • 每個紅色節點必須有兩個黑色的子節點;(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點。)
  • 如果一個節點是紅色的,則它的子節點必須是黑色的。
  • 從任一節結點其每個葉子的所有路徑都包含相同數目的黑色結點。

哈夫曼樹(最優二叉樹)

​ 給定N個權值作為N個葉子結點,構造一棵二叉樹,若該樹的帶權路徑長度達到最小,稱這樣的二叉樹為最優二叉樹,也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權路徑長度最短的樹,權值較大的結點離根較近。

圖片來自:百度搜索

在這裏插入圖片描述


B樹

​ B樹(B-tree)是一種自平衡的樹,能够保持數據有序。這種數據結構能够讓查找數據、順序訪問、插入數據及删除的動作,都在對數時間內完成。B樹,概括來說是一個一般化的二叉查找樹,可以擁有多於2個子節點。與自平衡二叉查找樹不同,B樹為系統大塊數據的讀寫操作做了優化。B樹减少定比特記錄時所經曆的中間過程,從而加快存取速度。B樹這種數據結構可以用來描述外部存儲。這種數據結構常被應用在數據庫和文件系統的實現上。

圖片來自:https://zhuanlan.zhihu.com/p/157590524
在這裏插入圖片描述

特點
  • 根節點至少有兩個子女。
  • 節點的分支數等於關鍵字數+1,最大的分支數就是B-樹的階數。
  • 下層結點內的關鍵字取值總是落在由上層結點關鍵字所劃分的區間內。

B+樹

​ B+樹是一種樹數據結構,通常用於數據庫的文件系統中。B+樹的特點是能够保持數據穩定有序,其插入與修改擁有較穩定的對數時間複雜度。B+樹元素自底向上插入,這與二叉樹恰好相反。

圖片來自:https://www.toutiao.com/a6681524631871947275/?channel=&source=search_tab
在這裏插入圖片描述

特點
  • 非葉子節點的子樹指針與關鍵字個數相同。
  • 所有葉結點在樹結構的同一層,並且不含任何信息(可看成是外部結點或查找失敗的結點),因此,樹結構總是樹高平衡的。
應用(數據庫的索引)

​ 數據都在葉子節點上,並且增加了順序訪問指針,每個葉子節點都指向相鄰的葉子節點的地址。相比B-Tree來說,進行範圍查找時只需要查找兩個節點,進行遍曆即可。

  • 數據項在葉子節點上面,非葉子節點不存儲真實的數據,只存儲指引搜索方向的數據項。

  • 內部節點存放key以及維持樹形結構的指針,葉子節點存放key對應的數據。
    特點

  • 非葉子節點的子樹指針與關鍵字個數相同。

  • 所有葉結點在樹結構的同一層,並且不含任何信息(可看成是外部結點或查找失敗的結點),因此,樹結構總是樹高平衡的。

版权声明:本文为[MarlonBrando1998]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201080457039174.html