資料結構學習，遞歸、二分搜尋樹（java語言）
- 1.遞歸
-
- 1.1遞歸的宏觀涵義
- 1.2連結清單中的遞歸
- 2.二分搜尋樹（Binary Search Tree）
-
- 2.1二分搜尋樹的基礎
- 2.2向二分搜尋樹中添加元素
- 2.3二分搜尋樹的查詢操作
- 2.4二分搜尋樹的三種深度優先的周遊方式
-
- 2.4.1前序周遊
- 2.4.2中序周遊
- 2.4.3後序周遊
- 2.5二分搜尋樹的層序周遊
- 2.6删除二分搜尋樹中的元素
-
- 2.6.1删除最大最小元素
- 2.6.2删除任意元素
- 3.總結
1.遞歸
1.1遞歸的宏觀涵義
遞歸是一種将複雜的問題，不斷分解成簡單的問題的一種程式設計思想，例如對一個數組進行求和，這個數組有10項int arr[10]，我們設計一個函數sum(int arr[],int index);我們隻要帶入sum(arr,0)這樣就能求出整個數組的和，然後将sum函數不斷拆分，sum(arr,0)=sum(arr,1)+arr[0]，這樣我們就将一個求十項和的函數拆分成了一個求九項和的函數，不斷拆分下去，直到最後一個sum(arr,9)+arr[8]；由于sum(arr,9)已經是最小問題了，此時隻要算出arr[9]傳回就好了，我們就得到了遞歸函數的終止條件。
public class Sum {
public int sum(int[] arr){
return sum(arr,0);
}
public int sum(int[] arr, int index){
if(arr.length == 0){
return 0;
}
if(index == arr.length){
return 0;
}
return arr[index]+sum(arr,index+1);
}
public static void main(String[] args){
int[] arr = {1,2,3,4,5,6,7};
Sum sum = new Sum();
System.out.println(sum.sum(arr));
}
}
從宏觀來看，我們的一個遞歸函數中，包含了遞歸頭（規定遞歸的終止條件）和遞歸體（遞歸的主要表現），在遞歸體中，不斷将原問題的更小問題向下遞去，當原問題被不斷分解，變成最小問題之後又不斷傳回來（return回來），就解決了原問題。
1.2連結清單中的遞歸
連結清單有天然的遞歸結構，一個連結清單可以看成一個頭節點與一個子連結清單的組合。在leetcode的第203題中，删除連結清單中的元素的問題，就可以用這種遞歸解決，寫法十分簡潔。
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head == null){
return null;
}
head.next = removeElements(head.next,val);
return head.val == val ? head.next : head;
}
}
2.二分搜尋樹（Binary Search Tree）
二分搜尋樹可以看成一顆有序的二叉樹，它是一顆對于這棵樹的所有節點來說，左子樹中所有的節點都小于該節點且右子樹中所有元素都大于該節點的二叉樹。當我們使用中序周遊時，就能夠獲得一顆按順序排好的樹。
2.1二分搜尋樹的基礎
二分搜尋樹中的基本結構跟連結清單相似，也是用了一個内部類，聲明了樹的節點，不同的是，連結清單中的每個節點都儲存了目前節點元素和下一個節點“next”，而二分搜尋樹的節點中儲存的是目前節點元素和“左孩子”left 和“右孩子”right ，且樹中儲存一個root根節點就可以表示這整顆樹。
public class BST<E extends Comparable<E>> {
private class Node{
public E e;
public Node left;
public Node right;
public Node(E e){
this.e = e;
left = null;
right = null;
}
}
private Node root;
private int size;
public BST(){
root = null;
size = 0;
}
}
2.2向二分搜尋樹中添加元素
向二分搜尋樹中添加元素主要是判斷新添加元素與各節點的大小關系。若比目前節點大，則應該放在right中，比目前節點小則放在left中，若一樣大，由于本次的二分搜尋樹不存儲相同元素，就不進行處理，同樣的，我們使用遞歸對二分搜尋樹進行添加元素十分友善
public void add(E e){
root = add(root,e);
}
private Node add(Node node , E e){
if(node == null){
size ++;
return new Node(e);
}
if(e.compareTo(node.e)<0){
node.left = add(node.left,e);
}else if(e.compareTo((node.e))>0){
node.right = add(node.right,e);
}
return node;
}
2.3二分搜尋樹的查詢操作
與添加操作大緻相同，通過不斷比對目前元素與節點元素的大小進行左子樹或者右子樹搜尋。
public boolean contains(E e){
return contains(root,e);
}
private boolean contains(Node node , E e){
if(node == null){
return false;
}
if(e.compareTo(node.e)==0){
return true;
}else if(e.compareTo(node.e)<0){
return contains(node.left,e);
}else{
return contains(node.right,e);
}
}
若要查詢最大最小的元素，即一直找到這棵樹的最左節點與最右節點即可
public E minimum(){
if(size==0){
throw new IllegalArgumentException("BST is empty");
}
return minimum(root).e;
}
private Node minimum(Node node){
if(node.left == null)
return node;
else
return minimum(node.left);
}
public E maximum(){
if(size==0){
throw new IllegalArgumentException("BST is empty");
}
return maximum(root).e;
}
private Node maximum(Node node){
if(node.right == null)
return node;
else
return maximum(node.left);
}
2.4二分搜尋樹的三種深度優先的周遊方式
二分搜尋樹的深度優先周遊有前序周遊、中序周遊和後序周遊。差別是通路根節點的時間。前序周遊先通路根節點，再通路左子樹，再通路右子樹；中序周遊先通路左子樹再通路根節點再通路右子樹；後序周遊先通路左子樹，再通路右子樹，最後通路根節點。同樣的，周遊二分搜尋樹我們也采用遞歸的方式。
2.4.1前序周遊
遞歸的終止條件是傳入的節點為空，就意味着不需要遞進，應該傳回了。在遞歸體中，修改通路目前節點的位置就可以調整周遊的順序。
public void preOrder(){
preOrder(root);
}
private void preOrder(Node node){
if(node == null)
return;
System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
}
2.4.2中序周遊
中序周遊可以将二分搜尋樹中的節點從大到小排列
public void inOrder(){
inOrder(root);
}
private void inOrder(Node node){
if(node == null){
return;
}
inOrder(node.left);
System.out.println(node.e);
inOrder(node.right);
}
2.4.3後序周遊
public void postOrder(){
postOrder(root);
}
private void postOrder(Node node){
if(node == null){
return ;
}
postOrder(node.left);
postOrder(node.right);
System.out.println(node.e);
}
2.5二分搜尋樹的層序周遊
層序周遊又稱廣度優先周遊，即先周遊完一個層級的所有節點再周遊下一層級的所有節點。我們通過隊列，可以很輕易的實作。先将根節點入隊，循環判斷隊列中是否為空，不為空就出隊隊首元素并對隊首進行操作，之後将隊首節點的左孩子入隊，右孩子入隊。這樣循環結束之後就是這種廣度優先的周遊。
public void levelOrder(){
Queue<Node> q = new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
Node cur = q.remove();
System.out.println(cur.e);
if(cur.left!=null)
q.add(cur.left);
if(cur.right!=null)
q.add(cur.right);
}
}
2.6删除二分搜尋樹中的元素
2.6.1删除最大最小元素
在删除最大元素或最小元素時，如果删除的是葉子節點那麼進行的操作就比較簡單，直接将葉子節點傳回為空就好了，如果該節點還有左/右子樹，就需要建立一個節點先将該子樹儲存下來，然後傳回給上一節點就可以了
public E removeMin(){
E ret = minimum();
root = removeMin(root);
return ret;
}
private Node removeMin(Node node){
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
public E removeMax(){
E ret = maximum();
root = removeMax(root);
return ret;
}
private Node removeMax(Node node){
if(node.right == null){
Node leftNode = node.left;
node.left = null;
size --;
return leftNode;
}
node.right = removeMax(node.right);
return node;
}
2.6.2删除任意元素
private Node remove(Node node , E e){
if(node == null)
return null;
if(e.compareTo(node.e)<0){
node.left = remove(node.left,e);
return node;
}
else if(e.compareTo(node.e)>0) {
node.right = remove(node.right, e);
return node;
}else{
//待删除節點左子樹為空
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
}
//待删除節點右子樹為空
if(node.right == null){
Node leftNode = node.right;
node.left = null;
size --;
return leftNode;
}
//待删除節點左右子樹均不為空的情況
//找到比待删除節點大的最小節點，即帶删除節點右子樹的最小節點
//用這個節點代替待删除節點的位置
Node successor = minimum(node.right);
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right =null;
return successor;
}
}
3.總結
- 遞歸對代碼的精簡有着十分重大的作用，但并不是遞歸算法就是最快的算法，由于遞歸需要不斷對函數進行壓棧操作，當遞歸次數過多的時候，就會出現棧溢出的情況，導緻算法運作失敗。
- 二分搜尋樹也是一種非常适合使用遞歸的資料結構。
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)