又是來自我的好朋友 EvilSay 的投稿，以下是原文：
1、基本定義
- 二分搜尋樹的每個子節點最多有兩個葉子節點
- 二分搜尋樹的每個節點最多有一個根節點
- 存儲的元素必須具有可比較性
- 二分搜尋樹每個子節點的值
- 大于其左子節的所有節點的值
- 小于其右子節點的所有節點的值
- 二分搜尋樹不一定是滿的
2、二分搜尋樹 Java 實作
/**
* @Author: EvilSay
* @Date: 2019/8/6 19:00
*/
public class BSTMain <E extends Comparable<E>> {
private class Node {
public E e;
private Node left, right;
public Node(E e) {
this.e = e;
left = null;
right = null;
}
}
//根節點
private Node root;
private int size;
public BSTMain() {
root = null;
size = 0;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void add(E e){
root = add(this.root, e);
}
// 向node為根的二分搜尋樹中插入元素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;
}
// 看二分搜尋樹中是否包含元素e
public boolean contains(E e){
return contains(root,e);
}
// 看以node為根的二分搜尋樹中是否包含元素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);
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
generateBSTSString(root,0,res);
return res.toString();
}
// 生成以node為根節點，深度為depth的描述二叉樹的字元串
private void generateBSTSString(Node root, int depth, StringBuilder res) {
if (root == null){
res.append(generateDepthString(depth) + "null\n");
return;
}
res.append(generateDepthString(depth) + root.e + "\n");
generateBSTSString(root.left, depth + 1 ,res);
generateBSTSString(root.right, depth + 1, res);
}
private String generateDepthString(int depth) {
StringBuilder res = new StringBuilder();
for (int i = 0; i < depth; i++)
res.append("--");
return res.toString();
}
} 3、圖解二分搜尋樹
從圖上我們看出二分搜尋樹每個節點的值大于其左子節的所有節點的值小于其右子節點的所有節點的值。
4、前序周遊
前序周遊也叫先序周遊，通路順序是根左右，也就是先通路根節點，再到左子樹，最後才到右子樹。是以上圖所示的通路順序是 5、3、2、4、8、7、9。
二分搜尋樹前序周遊遞歸版與非遞歸版
//前序周遊以node為根的二分搜尋樹，遞歸算法
private void preOrder(Node node){
if (node == null)
return;
System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
}
//二分搜尋樹的前序周遊遞歸調用
public void preOrder(){
preOrder(root);
}
//二分搜尋樹的前序周遊非遞歸寫法
public void preOrderNG(){
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);
}
} 了解非遞歸的實作邏輯、推導出前序遞歸的實作
- 建立一個堆棧，我們把根節點 5 推入棧中，接下來我們就要通路 5 這個根節點了，所有把 5 從棧中推出 。
- 推出的元素有 {5}，棧中的元素有 [] 。
- 在推入 5 的子節點就是 3，8，我們先入後出，先推入 8 再推入 3，現在堆棧的元素有 [8，3]，棧頂的 3 就是我們下一次要通路的節點是以把 3 推出 。
- 推出的元素有 {5,3}，棧中的元素有 [8] 。
- 在推入 3 的子節點就是 2，4 繼續先入後出，先推入 4 再推入 2，現在堆棧的元素有 [8,4,2]，棧頂的 2 就是我們下一次要通路的節點是以把 2 推出 。
- 推出的元素有 {5,3,2}，棧中的元素有 [8,4] 。
- 通路棧頂 4，由于 2 和 4 沒有子節點。是以我們直接把棧頂中的 4 推出 。
- 推出的元素有 {5,3,2,4}，棧中的元素有 [8] 。
- 通路棧頂 8 把 8 推出棧堆，再把 8 的子節點 7、9 推入棧中，先推入 9 後推入 7 。
- 推出的元素有 {5,3,2,4,8}，棧中的元素有 [9,7] 。
- 通路 7，沒有子節點，推出。
- 推出的元素有 {5,3,2,4,8,7}，棧中的元素有 [9] 。
- 通路 9，沒有子節點，推出。
- 推出的元素有 {5,3,2,4,8,7,9}，棧中的元素有 [] 。
5、中序周遊
中序周遊，通路順序是左根右，也就是先通路左子樹，再到根節點，最後才到右子樹。是以上圖所示的通路順序是 2、3、4、5、7、8、9。
二分搜尋樹中序周遊遞歸版與非遞歸版
//遞歸調用
public void inOrder(){
inOrder(root);
}
//二分搜尋樹的中序周遊遞歸寫法
private void inOrder(Node root){
if (root == null)
return;
inOrder(root.left);
System.out.println(root.e);
inOrder(root.right);
}
//二分搜尋樹中序周遊給遞歸寫法
public void preInOrderNG(){
// 建立棧,和前序周遊類似
Stack<Node> stack = new Stack<>();
Node node = root;
//添加暫時完畢，開始pop元素
while(node!=null || stack.size()>0 ){
while(node!=null){
stack.push(node);
node = node.left;
}
//一邊pop并且一邊進行判斷，右結點不會null的，右子樹，繼續按照添加方法，将最左結點全部添加進去
if(stack.size()>0){
Node pop = stack.pop();
System.out.print(pop.e+" ");
if(pop.right!=null){
node = pop.right;
}
}
} 了解非遞歸的實作邏輯、推導出中序遞歸的實作
- 首先我們把 5 這個節點推入棧中，再把 5 的左子節點 3 推入，再把 3的 左子節點 2 推入，再把 2 的左子節點推入(此時 2 的左子節點為空，node==null while 循環退出)。
- 推出的元素有 {}，棧中的元素有 [5,3,2]。
- node 為空，但我們棧中還有元素，通路棧頂元素 2，并檢視 2 是否有右子節點。沒有則推出棧并結束循環。
- 推出的元素有 {2}，棧中的元素有 [5,3]。
- 通路棧頂元素 3，把 3 推出棧中，并把 3 的右子節點 4 推入棧中，結束循環。
- 推出的元素有 {2,3}，棧中的元素有 [5]。
- 通路棧頂元素5，把5推出棧中。把5的右子節點8推入棧中，并把8的左子節點7推入棧中,結束循環。
- 推出的元素有 {2,3,5}，棧中的元素有 [8,7]
- 通路棧頂元素 7，并檢視 2 是否有右子節點。沒有則推出棧并結束循環。
- 推出的元素有 {2,3,5,7}，棧中的元素有 [8]。
- 通路棧頂元素 8，把 8 推出棧中。把 8 的右子節點 9 推入棧中
- 推出的元素有 {2,3,5,7,8}，棧中的元素有 [9]。
- 通路棧頂元素 9，并檢視 2 是否有右子節點。沒有則推出棧并結束循環。
- 推出的元素有 {2,3,4,5,7,8,9}，棧中的元素有 []。
6、後序周遊
中序周遊，通路順序是左右根，也就是先通路左子樹，再到右子樹，最後才到根節點。是以上圖所示的通路順序是 2、4、3、7、9、8、5。
二分搜尋樹後序周遊遞歸版與非遞歸版
//遞歸調用
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);
}
public void postOrderNG(){
Stack<Node> stack = new Stack<>();
//利用一個list集合記錄已将被周遊過的根節點，防止産生死循環
ArrayList<Node> list = new ArrayList<>();
Node node = root;
Node proud;
int flag;
//首頁檢查完樹的左子樹，再右子數，最後将根節點輸出
while (node != null || stack.size() > 0){
//将最左子樹添加完畢
while (node != null){
stack.push(node);
node = node.left;
}
//和中序周遊相似，為先輸出左子節點，但是做節點輸出完畢之後，不能直接将根節點彈出，而是必須先将右節點彈出，
//最後再将根節點彈出來，就會牽扯到一個根節點的通路狀态的問題，是否已經被周遊過了
if (stack.size() > 0){
Node peek = stack.peek();
if (peek.right != null){
boolean con = list.contains(peek);
if (con){
Node pop = stack.pop();
System.out.println(pop.e);
}else{
list.add(peek);
node = peek.right;
}
}else {
Node pop = stack.pop();
System.out.println(pop.e);
}
}
}
} 了解非遞歸的實作邏輯、推導出後序遞歸的實作
- 把 5 這個節點推入棧中，再把 5 的左子節點 3 推入，再把 3 的左子節點 2 推入，再把 2 的左子節點推入(此時 2 的左子節點為空，node==null while 循環退出)。
- node 為空但我們棧中還有元素，通路棧頂元素 2，并檢視 2 是否有左子節點。沒有則推出棧并結束循環。
- 通路棧頂元素 3，3 的右子節為 4，判斷 list 中是否有 3，沒有則把 3 放入 list 中并把 node 指派為 4 結束循環。
- node 為 4，把 4 推入棧中，并通路棧頂元素 4，并檢視 4 是否有右子節點。沒有則推出棧并結束循環。
- 推出的元素有 {2,4}，棧中的元素有 [5,3]。
- 通路棧頂元素 3，list 中有 3，把 3 的推出棧中并結束循環。
- 推出的元素有 {2,4,3}，棧中的元素有 [5]。
- 通路棧頂元素 5，5 的右子節為 8，判斷 lis t中是否有 8，沒有則把 5 放入 list 中并把 node 指派為 8 結束循環。
- node 為 8，把 8 推入棧中，并通路棧頂元 素8，8 有左子節點為 7。把 7 推入棧中。
- 推出的元素有 {2,4,3}，棧中的元素有 [5,8,7]。
- 通路棧頂元素 7，并檢視 7 是否有右子節點。沒有則推出棧并結束循環。
- 推出的元素有 {2,4,3,7}，棧中的元素有 [5,8]。
- 通路棧頂元素 8，8 的右子節點為 9。判斷 list 中是否有 9，沒有則把 8 放入 list 中并把 node 并把 node 指派為 9 結束循環。
- node 為 9，把 9 推入棧中，并通路棧頂元素 9，并檢視 9 是否有右子節點。沒有則推出棧并結束循環。
- 推出的元素有 {2,4,3,7,9}，棧中的元素有 [5,8]。
- 通路棧頂元素 8，list 中有 8，把 8 的推出棧中并結束循環。
- 推出的元素有 {2,4,3,7,9,8}，棧中的元素有 [5]。
- node 為空棧中還有元素，通路棧頂元素 5，list 中有 5，把 5 的推出棧中并結束循環。
- 推出的元素有 {2,4,3,7,9,8,5}，棧中的元素有 []。
最後
如果看到這裡，喜歡這篇文章的話，請轉發、點贊。微信搜尋「一個優秀的廢人」，歡迎關注。
回複「1024」送你一套完整的 java、python、c++、go、前端、linux、算法、大資料、人工智能、小程式以及英語教程。