Java實現二叉搜索樹的插入、刪除功能
二叉樹的結構
public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() { } TreeNode(int val) { this.val = val; } }
中序遍歷
- 中序遍歷:從根節點開始遍歷,遍歷順序是:左子樹->當前節點->右子樹,在中序遍歷中,對每個節點來說:
隻有當它的左子樹都被遍歷過瞭(或者沒有左子樹),它才會被遍歷到。
在遍歷右子樹之前,一定會先遍歷當前節點。
- 中序遍歷得到的第一個節點是沒有左子樹的(也許是葉子節點,也許有右子樹)
- 同理,中序遍歷的最後一個節點沒有右子樹
代碼遞歸實現
List<TreeNode> list = new ArrayList<>(); public void inorder_traversal(TreeNode root) { if (root == null) { return; } if (root.left != null) { inorder_traversal(root.left); } list.add(root); if (root.right != null) { inorder_traversal(root.right); } }
二叉搜索樹的定義
- 對每一個節點而言,左子樹的所有節點小於它,右子樹的所有節點大於它
- 二叉樹中每一個節點的值都不相同
- 中序遍歷的結果是升序的
這些定義決定瞭它的優點:查找效率快,因為二叉搜索樹查找一個值時,可以通過二分查找的方式,平均時間復雜度為log2(n),n是二叉樹的層樹
下圖就是一個標準的二叉搜索樹,右子樹比根節點大,左子樹比根節點小
查找節點
給定一個值,使用循環在二叉搜索樹中查找,找到該節點為止
- 從根節點開始,不斷循環進行比較
- 給定值大於當前節點,就找右子樹,小於就找左子樹,值相等就是找到瞭節點
代碼實現如下
public TreeNode search(TreeNode root, int val) { // 節點不為空,且不等於特定值 while(root != null && root.val != val){ if(root.val > val){ root = root.left; }else{ root = root.right; } } return root; }
添加節點
設要添加的節點為b, 二叉搜索樹的添加是將b作為葉子節點加入到其中,因為葉子節點的增加比較簡單。
- 跟搜索過程類似,從根節點開始,不斷循環找,找到一個適合新節點的位置
b值比當前節點大(小),並且當前節點的右(左)子樹為空,將b插入到當前節點的右(左)子樹中
如果當前節點的子樹不為空,繼續往下尋找
- 使用一個隨著搜索過程,不斷更新的pre節點作為b的父節點,由pre節點添加b
- 有可能要插入節點的二叉樹是一顆空樹,創建一個新的二叉樹
- 如果二叉搜索樹中已經有跟b相等的值,不需要進行添加
public TreeNode insertInto(TreeNode root, int val) { if (root == null) { // 樹為空樹的情況 return new TreeNode(val); } // 一個臨時節點指向根節點,用於返回值 TreeNode tmp = root; TreeNode pre = root; while (root != null && root.val != val) { // 保存父節點 pre = root; if (val > root.val) { root = root.right; } else { root = root.left; } } // 通過父節點添加 if (val > pre.val) { pre.right = new TreeNode(val); } else { pre.left = new TreeNode(val); } return tmp; }
刪除節點
刪除過程比較復雜,先設二叉搜索樹要刪除的節點為a,a有以下三種情況
- a為葉子節點
- a有一個子節點
- a有兩個子節點刪除葉子節點
過程類似搜索節點,找到到a後,通過它的父節點刪除,並且葉子節點的刪除不影響樹的性質
有一個子節點的節點
要將a刪除,並且保留a的子節點,讓它的父節點連接它的子節點即可,因為a的子節點 與 a的父節點 關系 == a與 a的父節點 關系,所以不改變樹的性質
- 二叉搜索樹的定義決定瞭:對於每一個節點而言,它 大於(小於) 它的父節點,那麼它的子節點 大於(小於) 它的父節點
過程像這張圖一樣
刪除有兩個子節點的節點
我們可以通過交換節點的方式,讓a 和 隻有一個子節點的節點 交換,刪除a的操作就變成瞭上面第二種情況。
我們知道中序遍歷二叉搜索樹的結果是升序的,如果要交換,肯定要找中序遍歷在a左右兩邊的節點(因為值交換之後也滿足二叉搜索樹的定義)
- 中序遍歷的後(前)一個節點是右(左)子樹中序遍歷的第一個(最後一個)節點,而且它們都隻有一個子節點
過程跟下面這張圖類似(a的值與中序遍歷的後一個節點交換,並刪除這個節點)
代碼實現
public TreeNode deleteNode(TreeNode root, int key) { TreeNode tmp = root; TreeNode pre = root; // 尋找要刪除的節點 while (root != null && root.val != key) { pre = root; if (key > root.val) { root = root.right; } else { root = root.left; } } // 找不到符合的節點值 if (root == null) { return tmp; } // 隻有一個子節點或者沒有子節點的情況 if (root.left == null || root.right == null) { if (root.left == null) { // 要刪除的是根節點,返回它的子節點 if (root == tmp) { return root.right; } // 使用父節點連接子節點,實現刪除當前節點 if (pre.left == root) { pre.left = root.right; } else { pre.right = root.right; } } else { if (root == tmp) { return root.left; } if (pre.left == root) { pre.left = root.left; } else { pre.right = root.left; } } return tmp; } // 第一種方式 // 尋找中序遍歷的後一個節點,也就是右子樹進行中序遍歷的第一個節點,右子樹的最左節點 pre = root; TreeNode rootRight = root.right; while (rootRight.left != null) { pre = rootRight; rootRight = rootRight.left; } // 節點的值進行交換 int tmpVal = rootRight.val; rootRight.val = root.val; root.val = tmpVal; // 中序遍歷的第一個節點肯定是沒有左子樹的,但是可能有右子樹,將右子樹連接到父節點上(相當於刪除有一個子節點的節點) if (pre.left == rootRight) { pre.left = rootRight.right; }else { pre.right = rootRight.right; } // 第二種方式 // 尋找中序遍歷的前一個節點,也就是左子樹進行中序遍歷的最後一個節點,左子樹的最右節點 // pre = root; // TreeNode rootLeft = root.left; // while (rootLeft.right != null){ // pre = rootLeft; // rootLeft = rootLeft.right; // } // // int tmpVal = rootLeft.val; // rootLeft.val = root.val; // root.val = tmpVal; // // // 中序遍歷的最後一個節點肯定是沒有右子樹的,但是可能有左子樹,將左子樹連接到父節點上(相當於刪除有一個子節點的節點) // if (pre.left == rootLeft) { // pre.left = rootLeft.left; // }else { // pre.right = rootLeft.left; // } return tmp; }
到此這篇關於Java實現二叉搜索樹的插入、刪除的文章就介紹到這瞭,更多相關Java二叉搜索樹內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- C++實現LeetCode(99.復原二叉搜索樹)
- C++實現LeetCode(98.驗證二叉搜索樹)
- java基礎二叉搜索樹圖文詳解
- Java數據結構之樹和二叉樹的相關資料
- C++實現LeetCode(106.由中序和後序遍歷建立二叉樹)