減治法在查找算法中的應(yīng)用

二叉查找樹的查找與插入：

二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：

（1）若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于或等于它的根節(jié)點(diǎn)的值；

（2）若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值；

（3）左、右子樹也分別為二叉排序樹。

對于二叉查找樹這里我們介紹查找、插入和刪除操作：

這些操作會(huì)將問題的規(guī)模變成一個(gè)更小的二叉樹，也運(yùn)用到了減治法的思想。

查找思路：如果樹為空，直接返回，查找失敗。反之，將查找值key與根root的值比較，如果相等，則root即為所找；若key < root.v，則繼續(xù)在左子樹查找；若key > root.v，則繼續(xù)在右子樹查找。

public static Node find(int key) {if (root == null) {System.out.println("The tree is empty!");return null;}Node cur = root;while (cur.v != key) {if (key < cur.v) {cur = cur.l;}else {cur = cur.r;}if (cur == null) {return null;}}return cur;

插入思路：基本思想和查找操作類似，如果為空樹，直接返回，插入節(jié)點(diǎn)即為根節(jié)點(diǎn)；否則，比較根節(jié)點(diǎn)的值與插入節(jié)點(diǎn)的值。注意用parent記錄遍歷到最后的cur值。

public static Node find(int key) {if (root == null) {System.out.println("The tree is empty!");return null;}Node cur = root;while (cur.v != key) {if (key < cur.v) {cur = cur.l;}else {cur = cur.r;}if (cur == null) {return null;}}return cur; } 刪除思路：刪除操作是二叉樹操作中最復(fù)雜的問題。對于二叉樹的刪除有一下三種情況：

（1）刪除葉子結(jié)點(diǎn)。可直接刪除，不會(huì)影響其他

（2）刪除結(jié)點(diǎn)有且只有一側(cè)孩子結(jié)點(diǎn)。孩子結(jié)點(diǎn)覆蓋待刪除結(jié)點(diǎn)，刪除孩子結(jié)點(diǎn)

（3）刪除結(jié)點(diǎn)下既有左孩子，又有右孩子。在待刪除結(jié)點(diǎn)的右孩子下，找到v值最小的，用這個(gè)結(jié)點(diǎn)覆蓋要?jiǎng)h除的結(jié)點(diǎn)。（這里是因?yàn)橹行虮闅v結(jié)點(diǎn)的后繼結(jié)點(diǎn)一定是在右子樹中v值最小的結(jié)點(diǎn)）

public static boolean delete(int key) {Node cur = root;Node parent = root;boolean hasLeft = true;while (cur != null && cur.v != key) {parent = cur;if (key < cur.v) {cur = cur.l;hasLeft = true;} else {cur = cur.r;hasLeft = false;}}if (cur == null) {return false;}if (cur.l == null && cur.r == null) {/*** 要?jiǎng)h除的節(jié)點(diǎn)為葉子節(jié)點(diǎn)，直接刪除* */if (cur == root) {root = null;}if (hasLeft) {parent.l = null;} else {parent.r = null;}} else if (cur.r == null) {/*** 要?jiǎng)h除的節(jié)點(diǎn)只有左孩子* */if (cur == root) {root = cur.l;}if (hasLeft) {parent.l = cur.l;} else {parent.r = cur.l;}} else if (cur.l == null) {/*** 要?jiǎng)h除的節(jié)點(diǎn)只有右孩子* */if (cur == root) {root = cur.r;}if (hasLeft) {parent.l = cur.r;}else {parent.r = cur.r;}} else {/*** 要?jiǎng)h除的節(jié)點(diǎn)既有左孩子又有右孩子* 思路：用待刪除節(jié)點(diǎn)右子樹中的v值最小的結(jié)點(diǎn)來替代要?jiǎng)h除的節(jié)點(diǎn),然后刪除右子樹中結(jié)點(diǎn)* 右子樹中v值最小的節(jié)點(diǎn)一定沒有左子樹,所以刪除的這個(gè)結(jié)點(diǎn)一定是屬于葉子節(jié)點(diǎn)或只有右子樹的節(jié)點(diǎn)* */Node directPostNode = getPost(cur);cur.v = directPostNode.v;}return true; } private static Node getPost(Node delNode) {Node parent = delNode;Node dir = delNode;Node cur = delNode.r;while (cur != null) {parent = dir;dir = cur;cur = cur.l;}if (dir != delNode.r) {//從樹中刪除此直接后繼節(jié)點(diǎn)parent.l = dir.r;dir.r = null;}return dir; }完整代碼如下：

class Node {int v;Node l;Node r;public Node(int v) {this.v = v;} } public class Main {public static Node root;public static Node find(int key) {if (root == null) {System.out.println("The tree is empty!");return null;}Node cur = root;while (cur.v != key) {if (key < cur.v) {cur = cur.l;}else {cur = cur.r;}if (cur == null) {return null;}}return cur;}public static void insert(Node node) {if (root == null) {root = node;return;}Node cur = root;Node parent = root;boolean hasLeft = true;while (cur != null) {parent = cur;if (node.v > cur.v) {cur = cur.r;hasLeft = true;} else {cur = cur.l;hasLeft = false;}}if (hasLeft) {parent.l = node;} else {parent.r = node;}}public static boolean delete(int key) {Node cur = root;Node parent = root;boolean hasLeft = true;while (cur != null && cur.v != key) {parent = cur;if (key < cur.v) {cur = cur.l;hasLeft = true;} else {cur = cur.r;hasLeft = false;}}if (cur == null) {return false;}if (cur.l == null && cur.r == null) {/*** 要?jiǎng)h除的節(jié)點(diǎn)為葉子節(jié)點(diǎn)，直接刪除* */if (cur == root) {root = null;}if (hasLeft) {parent.l = null;} else {parent.r = null;}} else if (cur.r == null) {/*** 要?jiǎng)h除的節(jié)點(diǎn)只有左孩子* */if (cur == root) {root = cur.l;}if (hasLeft) {parent.l = cur.l;} else {parent.r = cur.l;}} else if (cur.l == null) {/*** 要?jiǎng)h除的節(jié)點(diǎn)只有右孩子* */if (cur == root) {root = cur.r;}if (hasLeft) {parent.l = cur.r;}else {parent.r = cur.r;}} else {/*** 要?jiǎng)h除的節(jié)點(diǎn)既有左孩子又有右孩子* 思路：用待刪除節(jié)點(diǎn)右子樹中的v值最小的結(jié)點(diǎn)來替代要?jiǎng)h除的節(jié)點(diǎn),然后刪除右子樹中結(jié)點(diǎn)* 右子樹中v值最小的節(jié)點(diǎn)一定沒有左子樹,所以刪除的這個(gè)結(jié)點(diǎn)一定是屬于葉子節(jié)點(diǎn)或只有右子樹的節(jié)點(diǎn)* */Node directPostNode = getPost(cur);cur.v = directPostNode.v;}return true;}private static Node getPost(Node delNode) {Node parent = delNode;Node dir = delNode;Node cur = delNode.r;while (cur != null) {parent = dir;dir = cur;cur = cur.l;}if (dir != delNode.r) {//從樹中刪除此直接后繼節(jié)點(diǎn)parent.l = dir.r;dir.r = null;}return dir;}public static void preorder(Node node) {System.out.print(node.v + " ");if (node.l != null)preorder(node.l);if (node.r != null)preorder(node.r);}public static void main(String[] args) {/*** 插入* */insert(new Node(20));insert(new Node(10));insert(new Node(30));/*** 查找* */System.out.println(find(20));/*** 刪除* */delete(20);/*** 前序遍歷* */preorder(root);} }

總結(jié)

以上是生活随笔為你收集整理的减治法在查找算法中的应用（JAVA）--二叉查找树的查找、插入、删除的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。