原創(chuàng)作品，轉(zhuǎn)載請標(biāo)明來源。
一、 什么是二叉樹？
editByWpp.png
二叉樹每個節(jié)點最多有兩個孩子
二叉樹每個節(jié)點最多有一個父親
性質(zhì)
- 二叉樹具有天然的遞歸結(jié)構(gòu)
- 每個節(jié)點的左子樹也是二叉樹
- 每個節(jié)點的柚子樹也是二叉樹
- 二叉樹不一定是“滿”的
二、什么是二分搜索樹？
editByWpp.png
- 存儲的元素必須有可比較性（比如節(jié)點存儲的是學(xué)生，我們可以以年齡比較或?qū)W號比較等）
注意：本文的二分搜索樹不包含重復(fù)元素
如果想包含重復(fù)元素的話，只需要定義：左子樹小于等于節(jié)點；或者柚子樹大于節(jié)點即可
二分搜索樹的增刪茶
- 新增節(jié)點
二分搜索樹添加元素的非遞歸寫法，和鏈表很像
本文在二分搜索樹方面的實現(xiàn)，關(guān)注遞歸實現(xiàn)
public class BST<E extends Comparable<E>> {
private class Node{
public E e;
public Noe left, right;
public Node(E e) {
this.e = e;
left = null;
right = null;
}
// 向二分搜索樹中添加新的元素e -- 優(yōu)化前
public void add1(E e) {
if (root == null) {
root = new Node(e);
size++;
} else {
add(root,e);
}
}
// 向以node為根的二分搜索樹中插入元素E,遞歸算法---優(yōu)化前的插入元素部分
private void add1(Node node, E e) {
// 遞歸終止條件
if (e.equals(node.e)) {
return;
} else if (e.compareTo(node.e) < 0 && node.left == null) {
node.left = new Node(e);
size++;
return;
} else if (e.compareTo(node.e) > 0 && node.right == null) {
node.right = new Node(e);
size++;
return;
}
if (e.compareTo(node.e) < 0 && node.left != null) {
add(node.left,e);
} else{ // (e.compareTo(node.e) > 0 && node.right != null)
add(node.right,e);
}
}
// 向二分搜索樹中添加新的元素e -- 優(yōu)化后
public void add(E e) {
root = add(root,e);
}
// 向以node為根的二分搜索樹中插入元素E,遞歸算法---優(yōu)化后的插入元素部分
// null 也是一個二叉樹來考慮
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;
}
}
- 二分搜索樹的查詢操作
// 遞歸算法
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 //e.compareTo(node.e) > 0
return contains(node.right,e);
}
-
遍歷(前序、中序、后序-也叫深度優(yōu)先遍歷)
editByWpp.png
editByWpp.png
editByWpp.png
前序遍歷
public void preOrder() {
System.out.println();
preOrder(root);
}
private void preOrder(Node node) {
if (node == null)
return;
System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
}
// 非遞歸的前序遍歷
public void preOrderNR (){
Stack<Node> stack = new Stack();
stack.push(root);
while (!stack.isEmpty()) {
Node cur = stack.pop();
System.out.println(cur.e);
if (cur.right != null) stack.push(cur.right);
if (cur.left != null) stack.push(cur.left);
}
}
中序遍歷
/**
* 中序遍歷
*/
public void inOrder(){
System.out.println();
inOrder(root);
}
private void inOrder(Node node) {
if (node == null)
return;
inOrder(node.left);
System.out.print(node.e+ " ");
inOrder(node.right);
}
/**
* 后序遍歷
*/
public void postOrder() {
System.out.println();
postOrder(root);
}
private void postOrder(Node node) {
if (node == null) return;
postOrder(node.left);
postOrder(node.right);
System.out.print(node.e+" ");
}
-
層序遍歷(廣度優(yōu)先遍歷)--更快的找到問題的解（常用于算法設(shè)計中-最短路徑）
editByWpp.png
public void levelOrder (){
LinkedListQueue <Node> queue = new LinkedListQueue();
queue.enqueue(root);
while (!queue.isEmpty()) {
Node cur = queue.dequeue();
System.out.println(cur.e);
if (cur.left != null) queue.enqueue(cur.left);
if (cur.right != null) queue.enqueue(cur.right);
}
}
- 刪除操作
刪除二分搜索樹的某一個節(jié)點可能不是很好實現(xiàn)，我們可以先實現(xiàn)刪除最小節(jié)點和最大節(jié)點?？梢园l(fā)現(xiàn)最小節(jié)點就是二分搜索樹最左邊的節(jié)點，最大節(jié)點是二分搜索書最右邊的節(jié)點；代碼如下
// 得到最小節(jié)點值
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;
return miniMum(node.left);
}
// 得到醉倒節(jié)點值
public E maxMum(){
if (size == 0)
throw new IllegalArgumentException("BST is empty");
return maxMum(root).e;
}
private Node maxMum(Node node) {
if (node.right == null)
return node;
return maxMum(node.right);
}
public E removeMin(){
E ret = miniMum();
root = removeMin(root);
return ret;
}
// 刪除掉以node為根的二分搜索樹中的最小節(jié)點
// 返回刪除節(jié)點后新的二分搜索樹的根
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 = maxMum();
root = removeMax(root);
return ret;
}
// 刪除掉以node為根的二分搜索樹中的最大節(jié)點
// 返回刪除節(jié)點后新的二分搜索樹的根
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;
}
當(dāng)我們試圖刪除某一個節(jié)點時，如果這個節(jié)點只有左節(jié)點，沒有右節(jié)點，我們可以以刪除最大節(jié)點的方式去處理（即使該節(jié)點未必是最大節(jié)點），如果只有右節(jié)點沒有左節(jié)點時，我們同樣可以將它以刪除最小節(jié)點的方式去處理，問題是如果這個要刪除的節(jié)點既有左節(jié)點又有右節(jié)點時，怎么處理呢？
我引入一句話，給出了方案
1962年，Hibgard提出- Hibgard Deletion
其實也很簡單，就是找到待刪除節(jié)點的后置最小節(jié)點替代待刪節(jié)點；
比如下圖中，d節(jié)點是待刪節(jié)點，根據(jù)二分搜索樹的性質(zhì)，d節(jié)點的右子葉都比左子葉要打，那么我們只要找到右子葉的最小值替代當(dāng)前待刪節(jié)點就可以了。
editByWpp.png
另一種方案：也可以找到待刪節(jié)點的前驅(qū)最大節(jié)點替代待刪節(jié)點。如上圖其實也可以用53所在的節(jié)點替換d節(jié)點；
寫在后面
好了，現(xiàn)在二分搜索樹的分析暫時可以告一段落了，
