|
1. 是什么？ 數(shù)組和鏈表在增刪改查數(shù)據(jù)時(shí)，都有各自的缺點(diǎn)，比如數(shù)組要在中間插入數(shù)據(jù)，就要讓后面的數(shù)據(jù)整體都移動，而鏈表檢索數(shù)據(jù)很慢。之前說二叉樹時(shí)，說到樹這種結(jié)構(gòu)就是就是為了彌補(bǔ)數(shù)組和鏈表的缺點(diǎn)而誕生的，二叉排序樹(Binary search tree，簡稱BST)，更是體現(xiàn)了這一點(diǎn)。二叉排序樹有以下特點(diǎn)： - 左子節(jié)點(diǎn)的值比父節(jié)點(diǎn)??；
- 右子節(jié)點(diǎn)的值比父節(jié)點(diǎn)大；
2. 構(gòu)建過程： 假如現(xiàn)有數(shù)列：7,3,10,12,5,1,9，構(gòu)建二叉排序樹的過程如下： - 7當(dāng)成父節(jié)點(diǎn)，3比7小，放到7的左邊；
 二叉排序樹3. 二叉排序樹的刪除： 二叉排序樹的刪除有三種情況，如下： (1)：刪除的是葉子節(jié)點(diǎn)：比如上面這棵二叉排序樹中的1,5,9,12： 首先找到這個(gè)節(jié)點(diǎn)targetNode，如果不存在，直接刪除失?。?/p> 然后找到targetNode節(jié)點(diǎn)的父節(jié)點(diǎn)parent； 然后判斷targetNode是它的左節(jié)點(diǎn)還是右節(jié)點(diǎn)，直接讓對應(yīng)的左/右節(jié)點(diǎn)置空就行了(為什么不能直接targetNode == null？因?yàn)檫@個(gè)時(shí)候targetNode其實(shí)只是一個(gè)臨時(shí)指針，并不是原二叉樹的節(jié)點(diǎn)，targetNode == null對原二叉樹是沒有影響的)。
(2)：刪除的是只有一棵子樹的節(jié)點(diǎn)：假如上面這棵二叉排序樹節(jié)點(diǎn)1右邊再掛個(gè)2，那么1就是只有一棵子樹： 前面的邏輯都一樣，找到targetNode的parentNode后，要判斷targetNode的子節(jié)點(diǎn)sonNode是在targetNode的左邊還是右邊，同時(shí)要判斷targetNode在parent的左邊還是右邊。 如果targetNode是parentNode的左子節(jié)點(diǎn)，那么直接將sonNode掛在parentNode左邊即可； 如果targetNode是parentNode的右子節(jié)點(diǎn)，那么直接將sonNode掛在parentNode右邊即可； 如果parentNode為空，說明要?jiǎng)h除的是根節(jié)點(diǎn)，并且根節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，那么直接把這個(gè)子節(jié)點(diǎn)的值賦給根節(jié)點(diǎn)，然后再置空子節(jié)點(diǎn)即可。
(3)：刪除的是有兩棵子樹的節(jié)點(diǎn)：比如上面這棵二叉排序樹中的7，3，10: 前面的邏輯也一樣，找到targetNode和parentNode； 從targetNode的右子樹找到最小的節(jié)點(diǎn)，用臨時(shí)變量temp保存起來； 刪除上一步找到的那個(gè)右子樹的最小節(jié)點(diǎn)；
4. 代碼實(shí)現(xiàn)： 按照上面的思路，用代碼實(shí)現(xiàn)二叉排序樹的構(gòu)建和刪除功能： public class BinarySearchTree {
/** 根節(jié)點(diǎn) */
private Node root;
/**
* 添加節(jié)點(diǎn)
* @param value
*/
public void add(int value){
if (root == null){
root = new Node(value);
} else {
root.add(new Node(value));
}
}
/**
* 查找值為value的節(jié)點(diǎn)
* @param value
* @return
*/
public Node findNode(int value){
if (root == null){
return null;
} else {
return root.findNode(value);
}
}
/**
* 查找值為value的節(jié)點(diǎn)的父節(jié)點(diǎn)
* @param value
* @return
*/
public Node findParentNode(int value){
if (root == null){
return null;
} else {
return root.findParentNode(value);
}
}
/**
* 刪除值為value的節(jié)點(diǎn)
* @param value
*/
public void deleteNode(int value){
if (root == null){
return;
}
// 找到要?jiǎng)h除的節(jié)點(diǎn)和要?jiǎng)h除節(jié)點(diǎn)的父節(jié)點(diǎn)
Node targetNode = findNode(value);
Node parentNode = findParentNode(value);
if (targetNode == null){
return;
}
if (targetNode.left == null && targetNode.right == null){
// 要?jiǎng)h除的是葉子節(jié)點(diǎn)
deleteLeafNode(targetNode, parentNode);
} else if(targetNode.left != null && targetNode.right != null){
// 要?jiǎng)h除的是有兩棵子樹的節(jié)點(diǎn)
deleteDoubleSonNode(targetNode);
} else {
// 要?jiǎng)h除的是只有一棵子樹的節(jié)點(diǎn)
deleteSingleSonNode(targetNode, parentNode);
}
}
/**
* 要?jiǎng)h除的節(jié)點(diǎn)是葉子節(jié)點(diǎn)
* @param targetNode
* @param parentNode
*/
private void deleteLeafNode(Node targetNode, Node parentNode){
if (parentNode == null){
// parentNode為空，說明整棵二叉樹只有一個(gè)節(jié)點(diǎn)，直接置空root即可
root = null;
} else {
// parentNode不為空，那就看targetNode是parentNode的左孩子還是右孩子
if (parentNode.left != null && parentNode.left.value == targetNode.value){
parentNode.left = null;
} else {
parentNode.right = null;
}
}
}
/**
* 要?jiǎng)h除的是有兩棵子樹的節(jié)點(diǎn)
* @param targetNode
*/
private void deleteDoubleSonNode(Node targetNode){
// 從targetNode的右子樹找到值最小的節(jié)點(diǎn)
Node rightMinNode = findMinNode(targetNode.right);
// 刪除找到的最小的節(jié)點(diǎn)，此時(shí)的rightMinNode一定是葉子節(jié)點(diǎn)
deleteNode(rightMinNode.value);
// 將rightMinNode的值賦給targetNode
targetNode.value = rightMinNode.value;
}
/**
* 要?jiǎng)h除的是只有一棵子樹的節(jié)點(diǎn)
* @param targetNode
* @param parentNode
*/
private void deleteSingleSonNode(Node targetNode, Node parentNode){
if (parentNode == null){
// 要?jiǎng)h除的是根節(jié)點(diǎn)，且根節(jié)點(diǎn)有一棵子樹
Node sonNode = root.left == null ? root.right : root.left;
root.value = sonNode.value;
root.left = null;
root.right = null;
} else {
Node sonNode = targetNode.left == null ? targetNode.right : targetNode.left;
// 要?jiǎng)h除的節(jié)點(diǎn)有一棵子樹且不是根節(jié)點(diǎn)
if (parentNode.left != null && parentNode.left.value == targetNode.value){
parentNode.left = sonNode;
} else {
parentNode.right = sonNode;
}
}
}
/**
* 查找node子樹中值最小的節(jié)點(diǎn)
* @param node
* @return
*/
private Node findMinNode(Node node){
Node rightMinNode = node;
while (rightMinNode.left != null){
rightMinNode = rightMinNode.left;
}
return rightMinNode;
}
/**
* 中序遍歷
*/
public void middleOrder(){
if (root == null){
return;
} else {
root.middleOrder();
}
}
/**
* 層序遍歷
*/
public void sequenceOrder(){
if (root == null){
return;
} else {
root.sequenceOrder();
}
}
/**
* 節(jié)點(diǎn)
*/
class Node{
/** 值 */
int value;
/** 左子樹 */
Node left;
/** 右子樹 */
Node right;
Node(int value){
this.value = value;
}
/**
* 添加節(jié)點(diǎn)
* @param node
*/
public void add(Node node){
if (node == null){
return;
}
if (node.value < this.value){
// 值比當(dāng)前節(jié)點(diǎn)小，往左添加
if (this.left == null){
this.left = node;
} else {
this.left.add(node);
}
} else {
// 值比當(dāng)前節(jié)點(diǎn)大，往右添加
if (this.right == null){
this.right = node;
} else {
this.right.add(node);
}
}
}
/**
* 查找值為value的節(jié)點(diǎn)
* @param value
* @return
*/
public Node findNode(int value){
if (this.value == value){
return this;
} else if (value < this.value && this.left != null){
return this.left.findNode(value);
} else if (value >= this.value && this.right != null){
return this.right.findNode(value);
} else {
return null;
}
}
/**
* 查找值為value的節(jié)點(diǎn)的父節(jié)點(diǎn)
* @param value
* @return
*/
public Node findParentNode(int value){
if ((this.left != null && this.left.value == value)
|| (this.right != null && this.right.value == value)){
return this;
} else {
if (this.left != null && value < this.value){
return this.left.findParentNode(value);
} else if (this.right != null && value >= this.value){
return this.right.findParentNode(value);
} else {
return null;
}
}
}
/**
* 中序遍歷
*/
public void middleOrder(){
if (this.left != null){
this.left.middleOrder();
}
System.out.println(this.value);
if (this.right != null){
this.right.middleOrder();
}
}
/**
* 層序遍歷
*/
public void sequenceOrder(){
Queue<Node> queue = new LinkedList<>();
Node currentNode = this;
while(currentNode != null){
System.out.println(currentNode.value);
if (currentNode.left != null){
queue.add(currentNode.left);
}
if (currentNode.right != null){
queue.add(currentNode.right);
}
currentNode = queue.poll();
}
}
}
}
測試代碼： public class BinarySearchTreeTest {
public static void main(String[] args) {
int[] arr = {7,3,10,12,5,1,9};
BinarySearchTree binarySearchTree = new BinarySearchTree();
for (int i = 0; i < arr.length; i++) {
binarySearchTree.add(arr[i]);
}
binarySearchTree.middleOrder();
binarySearchTree.deleteNode(5);
System.out.println("刪除之后：");
binarySearchTree.middleOrder();
}
}
不知各位發(fā)現(xiàn)沒有，二叉排序樹中序遍歷就是一個(gè)升序序列。
|
