資料結構之二叉樹
本文是資料結構和演算法之美學習筆記
樹
樹這種資料結構跟現實中的樹很像,裡面的每個元素叫做結點,用連線把相鄰的結點連線起來,相鄰結點之間的關係叫父子關係。
比如下圖中,A結點是B的父節點,B是A的子結點,B,C,D是兄弟結點,E沒有父節點稱為根節點,沒有子節點的結點是葉子結點,G,H,I,H,K,L都是葉子結點。
樹一般用三個概念可以描述,高度,深度,層
高度:結點到葉子結點的最長路徑(邊數)
深度:根結點到這個結點所經歷的邊的個數
層數:結點的深度加1
樹的高度:根結點的高度
高度是從下往上度量,就像數樓層。深度從上往下度量,就像往水下看,層數是跟深度類似,不過是以1為起點。
二叉樹
顧名思義,就是每個結點最多有兩個叉,也就是兩個葉子結點,左子節點和右子節點,左右子節點只要存在一個就行。
如果除了葉子結點外的每個結點都有左右兩個子節點,這種二叉樹叫“滿二叉樹”
如果葉子結點都在最底下兩層,最後一層的葉子結點都靠左排列,並且除了最後一層,其他的結點個數都要達到最大,這種二叉樹叫做“完全二叉樹”
如何儲存一個二叉樹?
可以使用基於指標的或者引用的二叉鏈式儲存法,或者基於陣列的順序儲存法。
鏈式儲存法:
每個結點有三個欄位,其中一個快取資料,剩下的兩個分別是指向左右子節點的指標。我們只要找到根節點就能通過左右指標找到所有資料。
順序儲存法:
把根節點儲存在下標為i=1的位置,左子節點儲存在下標為2 i=2的位置,右子節點儲存在2 i+1=3的位置,以此類推。
對於順序儲存法來說,完全二叉樹更能節省記憶體。
二叉樹的遍歷
經典的方法有三種:前序遍歷,中序遍歷,後序遍歷。前中後表示的是結點本身列印的順序。
- 前序遍歷是對於樹種的任意結點來說,先列印這個結點,然後在列印它的左子樹,最後列印它的右子樹
- 中序遍歷是對於樹種任意結點來說,先列印它的左子樹,在列印它本身,最後列印它的右子樹
- 後序遍歷是先對於樹種任意結點來說,先列印左子樹,在列印右子樹,最後列印結點本身。
其實二叉樹的前中後遍歷就是一個遞迴的過程。比如前序遍歷,就是先列印跟結點,然後遞迴列印左子樹,在遞迴列印右子樹。
遍歷方法:
void preOrder(Node* root) { if (root == null) return; System.out.print(root.data); preOrder(root->left); preOrder(root->right); } void inOrder(Node* root) { if (root == null) return; inOrder(root->left); System.out.print(root.data); inOrder(root->right); } void postOrder(Node* root) { if (root == null) return; postOrder(root->left); postOrder(root->right); System.out.print(root.data); }
還有一種按層遍歷,這個需要用到佇列
public void levelOrder(BinaryTree tree) { // 利用佇列先入先出的特點來實現按層遍歷 LinkedList<BinaryTree> linkedList = new LinkedList<>(); // 記錄當前遍歷到哪個結點 BinaryTree currentNode = tree; // 根節點入隊 linkedList.add(currentNode); // 從佇列中彈出各結點資料,直到佇列為空,遍歷完畢 while (linkedList.size()>0){ // 彈出隊首元素(當前結點),列印其資料,並依次將其左右子節點入隊 currentNode = linkedList.poll(); System.out.print(currentNode.data+" -> "); if (currentNode.left!=null) { linkedList.add(currentNode.left); } if (currentNode.right!=null) { linkedList.add(currentNode.right); } } }
二叉樹最大的特點就是支援動態資料集合的快速插入、刪除、查詢操作。
二叉查詢樹(Binary Search Tree)
二叉查詢樹也叫二叉搜尋樹,是為了實現快速查詢而生的,不過它不僅支援快速查詢還支援快速插入刪除。
二叉查詢樹規定:在樹中的任意一個節點,其左子樹的每個值都小於這個節點的值,右子樹的每個值都大於這個節點的值。
1.二叉查詢樹的查詢
先取根節點,如果它等於我們要查詢的資料,那就返回,如果要查詢的資料小於根節點的值,那就在左子樹中查詢,反之就在右子樹中查詢。
程式碼:
public class BinarySearchTree { private Node tree; public Node find(int data) { Node p = tree; while (p != null) { if (data < p.data) p = p.left; else if (data > p.data) p = p.right; else return p; } return null; } public static class Node { private int data; private Node left; private Node right; public Node(int data) { this.data = data; } } }
2.二叉查詢樹的插入
新插入的資料一般都是在葉子節點,我們需要從根節點開始依次比較要插入的資料和節點的大小關係。如果要插入的資料比節點的資料大,並且節點的右子樹為空,就把資料插到右子節點的位置,如果不為空就在遞迴遍歷右子樹,直到找到插入的位置。如果要插入的資料比節點數值小並且節點的左子樹為空,就插入,不為空,遞迴遍歷左子樹直到找到插入位置。
程式碼:
public void insert(int data) { if (tree == null) { tree = new Node(data); return; } Node p = tree; while (p != null) { if (data > p.data) { if (p.right == null) { p.right = new Node(data); return; } p = p.right; } else { // data < p.data if (p.left == null) { p.left = new Node(data); return; } p = p.left; } } }
3.二叉查詢樹的刪除
刪除操作比插入和查詢操作麻煩一點
(1)如果要刪除的節點是葉子節點,我們只需更新父節點指向刪除節點的指標為null
(2)如果要刪除的節點只有一個子節點,我們只需要更新其父節點中指向要刪除節點的指標,讓它指向要刪除的節點的子節點就好了
(3)如果要刪除的節點有兩個子節點,我們需要找到這個節點的右子樹中的最小節點,或者這個節點的左子樹的最大節點,把它替換到要刪除的節點上。因為父節點的指標一定比所有左子樹的節點值大,比右子樹的節點的值
程式碼:
public void delete(int data) { Node p = tree; // p 指向要刪除的節點,初始化指向根節點 Node pp = null; // pp 記錄的是 p 的父節點 while (p != null && p.data != data) { pp = p; if (data > p.data) p = p.right; else p = p.left; } if (p == null) return; // 沒有找到 // 要刪除的節點有兩個子節點 if (p.left != null && p.right != null) { // 查詢右子樹中最小節點 Node minP = p.right; Node minPP = p; // minPP 表示 minP 的父節點 while (minP.left != null) { minPP = minP; minP = minP.left; } p.data = minP.data; // 將 minP 的資料替換到 p 中 p = minP; // 下面就變成了刪除 minP 了 pp = minPP; } // 刪除節點是葉子節點或者僅有一個子節點 Node child; // p 的子節點 if (p.left != null) child = p.left; else if (p.right != null) child = p.right; else child = null; if (pp == null) tree = child; // 刪除的是根節點 else if (pp.left == p) pp.left = child; else pp.right = child; }
中序遍歷二叉樹可以輸出有序的資料序列,並且非常高效。因此二叉查詢樹也叫做二叉排序樹。
如果資料中有重複的資料怎麼辦?
(1)二叉查詢樹中不僅會儲存一個數據,我們可以通過連結串列和支援動態擴容的陣列,把相同的值儲存在同一個節點上。
(2)插入資料的時候,如果碰到一個節點的值與要插入的資料的值相同,就將這個要插入的資料放到這個節點的右子樹,也就是把它當成大於這個節點的值來處理。
當要查詢資料的時候,遇到值相同的節點,不停止查詢操作,而是繼續在右子樹中查詢,直到遇到葉子節點停止。
刪除資料的時候,先找到每個要刪除的節點,然後按照前面的刪除方法依次刪除。