樹(shù)
作業(yè)：
1. 二分搜索樹(shù)一些方法的非遞歸實(shí)現(xiàn)
2**. 層序遍歷茴丰，打印出一個(gè)二叉樹(shù)
將數(shù)據(jù)使用數(shù)結(jié)構(gòu)儲(chǔ)存后贿肩，出奇的高效
二分搜索樹(shù)
平衡二叉樹(shù) AVL 紅黑樹(shù)
堆 并查集
線段樹(shù) Trie(字典樹(shù)汤功，前綴樹(shù))
二叉樹(shù)
二叉樹(shù)具有唯一根節(jié)點(diǎn)
class Node {
E e;
Node left;
Node right
}
二叉樹(shù)每個(gè)節(jié)點(diǎn)最多有兩個(gè)孩子
二叉樹(shù)節(jié)點(diǎn)最多只有一個(gè)父親
二叉樹(shù)具有天然遞歸結(jié)構(gòu)
二叉樹(shù)不一定是‘滿’的
二分搜索樹(shù)
二分搜索樹(shù)是一個(gè)二叉樹(shù)
二分搜索樹(shù)的每個(gè)節(jié)點(diǎn)的值：每個(gè)節(jié)點(diǎn)
* 大于其左子樹(shù)的所有節(jié)點(diǎn)的值
* 限于其右子數(shù)所有節(jié)點(diǎn)的值
二分搜索樹(shù)的每個(gè)子數(shù)也是一個(gè)二分搜索樹(shù)
存儲(chǔ)的元素必須有可比較性
這里的二分搜索樹(shù)不包含重復(fù)的元素
如果想包含重復(fù)的元素滔金，只需要修改定義就可以了
* 左子樹(shù)小于等于節(jié)點(diǎn)鹦蠕；或者右子數(shù)大于等于節(jié)點(diǎn)
前序遍歷：遞歸先訪問(wèn)節(jié)點(diǎn)，然后訪問(wèn)左子樹(shù)，然后訪問(wèn)右子樹(shù)
中序遍歷：遞歸先訪問(wèn)左子樹(shù)朴读，然后訪問(wèn)節(jié)點(diǎn)衅金，然后訪問(wèn)右子樹(shù)
訪問(wèn)的結(jié)果是從小到大的排序結(jié)果５ā！姨伟！順序的
后續(xù)遍歷：遞歸先訪問(wèn)左子樹(shù)惩琉，然后訪問(wèn)右子樹(shù),然后訪問(wèn)節(jié)點(diǎn)
應(yīng)用場(chǎng)景：為二分搜索樹(shù)釋放內(nèi)存空間
反序遍歷：我TM自己創(chuàng)的！,右子夺荒，節(jié)點(diǎn)瞒渠，左子，倒敘訪問(wèn)
二分搜索樹(shù)基本功能實(shí)現(xiàn)
package bannerySearchTree;
import datastructure.array.ArrayStack;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class BST<E extends Comparable<E>> {
/*Comparable接口代表這個(gè)類型必須具有可比較性*/
private class Node{
public E e;
public Node left, right;
public Node(E e){
this.e = e;
this.left = null;
this.right = null;
}
}
private Node root;
private int size;
public BST(){
root = null;
size = 0;
}
public int size(){
return this.size;
}
public boolean isEmpty(){
return this.size == 0;
}
/*
// 添加元素伍玖，根節(jié)點(diǎn)特殊處理
public void add(E e){
if(size == 0) {
this.root = new Node(e);
size++;
}
else
this.add(root, e);
}
// 向以node為根的二分搜索樹(shù)中插入元素e，遞歸算法
private void add(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){
add(node.left, e);
} else {
add(node.right, e);
}
}
*/
// 更加簡(jiǎn)潔的寫(xiě)法,因?yàn)閚ull也可以看做是一個(gè)二分搜索樹(shù)的節(jié)點(diǎn)
public void add(E e){
root = add(root, e);
}
/*將待插入的節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)比較剿吻，如果當(dāng)前節(jié)點(diǎn)為終止條件窍箍，則直接賦值
* 如果當(dāng)前節(jié)點(diǎn)不為空，與當(dāng)前節(jié)點(diǎn)比較，選擇對(duì)應(yīng)的子樹(shù)進(jìn)行遞歸仔燕，最終將當(dāng)前節(jié)點(diǎn)返回并掛載
* 到父節(jié)點(diǎn)對(duì)應(yīng)的分支上造垛。由于要滿足將最終的插入節(jié)點(diǎn)掛載到父節(jié)點(diǎn)上，不得不對(duì)所有深度的遞歸
* 都重新進(jìn)行掛載*/
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;
}
// 查看二分搜索樹(shù)中是否包含元素e
public boolean contains(E e){
return contains(root, e);
}
// 以node為根的二分搜索樹(shù)中是否包含元素e,遞歸算法
private boolean contains(Node node, E e){
if(node.e == 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);
}
// 二分搜索樹(shù)的前序遍歷
public void preOrder(){
this.preOrder(root);
}
// 前序遍歷晰搀，以node為根的二分搜索樹(shù)五辽，遞歸算法
private void preOrder(Node node){
if(node != null){
System.out.print(node.e);
System.out.print(' ');
preOrder(node.left);
preOrder(node.right);
}
}
// 打印帶深度的前序遍歷
@Override
public String toString(){
StringBuilder res = new StringBuilder();
this.generateBTSString(root, 0, res);
return res.toString();
}
private void generateBTSString(Node node, int depth, StringBuilder res){
if(node != null){
res.append(this.generateDepthGangGang(depth) + node.e + '\n');
generateBTSString(node.left, depth + 1, res);
generateBTSString(node.right, depth + 1, res);
} else
res.append(this.generateDepthGangGang(depth) + "NULL\n");
}
private String generateDepthGangGang(int depth){
StringBuilder res = new StringBuilder();
for(int i = 0; i < depth; i ++){
res.append("- ");
}
return res.toString();
}
// 中序遍歷，先遍歷左子樹(shù)外恕，然后節(jié)點(diǎn)杆逗，然后右子樹(shù)。遍歷的順序就是排序的順序
public void inOrder(){
this.inOrder(root);
}
private void inOrder(Node node){
if(node == null)
return;
inOrder(node.left);
System.out.print(node.e);
System.out.print(' ');
inOrder(node.right);
}
// 反中序遍歷鳞疲，我TM自己創(chuàng)的罪郊！,右子，節(jié)點(diǎn)尚洽，左子
public void reverseInOrder(){
this.reverseInOrder(root);
}
private void reverseInOrder(Node node){
if(node == null)
return;
reverseInOrder(node.right);
System.out.print(node.e);
System.out.print(' ');
reverseInOrder(node.left);
}
// 后續(xù)遍歷
public void postOrder(){
this.postOrder(root);
}
private void postOrder(Node node){
if(node == null)
return;
postOrder(node.left);
postOrder(node.right);
System.out.print(node.e);
System.out.print(' ');
}
/*二分搜索樹(shù)的層序遍歷
* 利用隊(duì)列悔橄，廣度優(yōu)先遍歷！
* 現(xiàn)將節(jié)點(diǎn)入隊(duì)腺毫，
* 出隊(duì)癣疟，操作之后，將左右子節(jié)點(diǎn)入隊(duì)
* (每深入一層潮酒，入隊(duì)的規(guī)模平均呈2^n增加)
* 如果不明白畫(huà)個(gè)圖就一目了然了
* 應(yīng)用：跟快的找到問(wèn)題的解答
* 常用于算法設(shè)計(jì)中-最短路徑
* 圖中的深度優(yōu)先于廣度優(yōu)先*/
public void levelOrder(){
// java自帶的Queue是一個(gè)接口
// 必須指定使用隊(duì)列底層使用的類型(Array or LinkedList)
Queue<Node> q = new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
Node cur = q.remove();
System.out.print(cur.e);
System.out.print(' ');
if(cur.left != null)
q.add(cur.left);
if(cur.right != null)
q.add(cur.right);
}
}
// 非遞歸實(shí)現(xiàn)前序遍歷
/*先將節(jié)點(diǎn)入棧睛挚，再出棧打印，在將右子樹(shù)節(jié)點(diǎn)入棧（如果存在）急黎，再將左子樹(shù)節(jié)點(diǎn)入棧（如果存在）扎狱，再出棧*/
public void preOrderNC(){
ArrayStack<Node> stack = new ArrayStack<>();
Node cur = root;
stack.push(cur);
while(!stack.isEmpty()){
// 先出棧
cur = stack.pop();
System.out.print(cur.e);
System.out.print(' ');
if(cur.right != null){
stack.push(cur.right);
}
if(cur.left != null){
stack.push(cur.left);
}
}
}
// 非遞歸實(shí)現(xiàn)中序遍歷
/**
* 使用棧
* 1. 不斷地將當(dāng)前的左子樹(shù)壓如棧中，直到遇見(jiàn)null就不壓入
* 2. 從棧中取出一個(gè)節(jié)點(diǎn)勃教，打印淤击，令當(dāng)前節(jié)點(diǎn)等于右子樹(shù)節(jié)點(diǎn)，重復(fù)步驟1.
* 3. 直到棧為空荣回，當(dāng)前的節(jié)點(diǎn)為null
* (注意：每次操作了的節(jié)點(diǎn)都出棧了遭贸，不會(huì)存在重復(fù)遍歷左子樹(shù)的情況)*/
public void inOrderNC(){
Stack<Node> stack = new Stack<>();
Node node = root;
while(!stack.isEmpty() || node != null){
if(node != null){
stack.push(node);
node = node.left;
} else {
node = stack.pop();
System.out.println(node.e);
node = node.right;
}
}
}
// 非遞歸實(shí)現(xiàn)后續(xù)遍歷
/** 遞歸的思想，類似于漢諾塔問(wèn)題心软，
* 1. 申請(qǐng)一個(gè)棧1壕吹，將節(jié)點(diǎn)壓入棧1中
* 2. 從棧1中取出一個(gè)節(jié)點(diǎn)放入棧2，將左孩子删铃，右孩子依次壓入棧中
* 3. 重復(fù)2.步驟耳贬，直到棧1中為空，讓后從棧2中依次取出節(jié)點(diǎn)并打印猎唁，就是后續(xù)遍歷的順序
* 注意：每顆子樹(shù)的頭結(jié)點(diǎn)都是從棧1中出來(lái)咒劲，放入棧2中，然后對(duì)應(yīng)的右子樹(shù)節(jié)點(diǎn)，左子樹(shù)節(jié)點(diǎn)從棧
* 1出來(lái)腐魂，以中右左的方式存入的棧2帐偎，最后打印的順序又是反著的，左右中蛔屹，這種思路與解決漢諾塔遞歸的思想
* 如出一轍*/
public void postOrderNC(){
Stack<Node> tep1 = new Stack<>();
Stack<Node> tep2 = new Stack<>();
Node node = root;
tep1.push(node);
while(!tep1.isEmpty()){
node = tep1.pop();
tep2.push(node);
if(node.left != null)
tep1.push(node.left);
if(node.right != null)
tep1.push(node.right);
}
while(!tep2.isEmpty()){
System.out.print(tep2.pop().e);
System.out.print(' ');
}
}
/*找到數(shù)中的最小值*/
public E minimum(){
if(this.isEmpty())
throw new IllegalArgumentException("Find failed, the tree is empty");
return minimum(root).e;
}
private Node minimum(Node node){
if(node.left == null)
return node;
else
return minimum(node.left);
}
/*找到數(shù)中的最大值*/
public E maxmum(){
if(this.isEmpty())
throw new IllegalArgumentException("Find failed, the tree is empty");
return maxmum(root).e;
}
private Node maxmum(Node node){
if(node.right == null)
return node;
else
return maxmum(node.right);
}
/**刪除二叉樹(shù)中的最大值與最小值削樊，
最小值在樹(shù)的最左邊，有兩種情況兔毒，
沒(méi)有子樹(shù)漫贞，有右子樹(shù)（最大值以此類推）
* 作業(yè)：使用非遞歸的方式實(shí)現(xiàn)邏輯*/
/* 刪除最小值 */
public E removeMin(){
E ret = this.minimum();
root = removeMin(root);
return ret;
}
/** 每深入一次遞歸，就將當(dāng)前節(jié)點(diǎn)返回給父親育叁。從而不用保留父父節(jié)點(diǎn)進(jìn)行賦值這種迅脐！
* 為了刪除一個(gè)節(jié)點(diǎn)，代價(jià)就是每次遞歸豪嗽，都將子樹(shù)掛載給父親*/
private Node removeMin(Node node){
if(node.left == null){
size--;
// if(node.right != null)
// return node.right;
// return null;
// 另一種方式谴蔑，手動(dòng)回收被刪除的節(jié)點(diǎn)
// 臨時(shí)保存右子樹(shù)
Node rightNode = node.right;
// 將被刪除的節(jié)點(diǎn)與子樹(shù)脫離關(guān)系，這里只考慮右子樹(shù)就可以了
node.right = null;
// 返回原來(lái)的右子樹(shù)龟梦，如果沒(méi)有右子樹(shù)树碱，返回為null也是符合邏輯的
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
/*刪除最大值*/
public E removeMax(){
E res = maxmum();
root = removeMax(root);
return res;
}
private Node removeMax(Node node){
if(node.right == null) {
size--;
// if (node.left != null)
// return node.left;
// return null;
Node leftNode = node.left;
node.left = null;
return leftNode;
}
node.right = removeMax(node.right);
return node;
}
/**刪除任意值
* 一：沒(méi)有子節(jié)點(diǎn)，將當(dāng)前節(jié)點(diǎn)刪除变秦，返回nul
* 二：有一個(gè)左子樹(shù)或者右子樹(shù)，刪除該節(jié)點(diǎn)后將子樹(shù)節(jié)點(diǎn)返回
* 三：同時(shí)存在兩個(gè)子樹(shù)框舔，找到右子樹(shù)找離當(dāng)前值最近的那個(gè)大于節(jié)點(diǎn)的值蹦玫，
* 在右子樹(shù)的最左邊，將此節(jié)點(diǎn)替換為當(dāng)前的節(jié)點(diǎn)待返回刘绣，刪除找到的節(jié)點(diǎn)*/
public void remove(E e){
root = remove(root, e);
}
private Node remove(Node node, E e){
if(e.compareTo(node.e) < 0){
node.left = remove(node.left, e);
return node;
} else if(e.compareTo(node.e) > 0) {
node.right = remove(node.right, e);
return node;
} else {
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
} else if(node.right == null){
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
} else {
/**算法 后繼法：
* 找到右子樹(shù)最小值賦給臨時(shí)節(jié)點(diǎn)
* 將待刪除節(jié)點(diǎn)的左子樹(shù)賦給臨時(shí)節(jié)點(diǎn)對(duì)應(yīng)的子樹(shù)
* 將待刪除節(jié)點(diǎn)的右子樹(shù)刪除最小值并賦值給臨時(shí)節(jié)點(diǎn)
* 返回臨時(shí)節(jié)點(diǎn)
* @@ 直接調(diào)用successor = removeMin(node.right)這種算法要考慮很多情況
* @@ 而先找到右子樹(shù)最小的樱溉，再刪除該節(jié)點(diǎn)會(huì)自動(dòng)處理那些情況*/
Node successor = this.minimum(node.right);
/*調(diào)用了removeMin size自行--*/
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
/**前驅(qū)法
Node successor = this.maxmum(node.left);
successor.left = this.removeMax(node.left);
successor.right = node.right;
node.left = node.right = null;*/
return successor;
}
}
}
/**關(guān)于二分搜索樹(shù)的更多話題+ 作業(yè)(沒(méi)有@的為作業(yè))
* OK打印一棵樹(shù)
* OK非遞歸實(shí)現(xiàn)中序遍歷
* OK非遞歸實(shí)現(xiàn)反序遍歷
* OK某個(gè)值（可以不包含在節(jié)點(diǎn)中）的floor 比此值小的最大的元素
* OK某個(gè)值（可以不包含在節(jié)點(diǎn)中）的ceil 比此值大的最小的那個(gè)元素
*
* OK維護(hù)size的二分搜索樹(shù)，在節(jié)點(diǎn)中保存該節(jié)點(diǎn)包含的總結(jié)點(diǎn)數(shù)纬凤，包含自己福贞，
* rank: 這個(gè)元素在數(shù)中排名第幾？（推薦方式：）
* select: 排名是第幾的元素是誰(shuí)停士？（推薦方式：在節(jié)點(diǎn)中保存該節(jié)點(diǎn)包含的總結(jié)點(diǎn)數(shù)挖帘，包含自己）
*
* @OK維護(hù)depth的二分搜索樹(shù)，每個(gè)節(jié)點(diǎn)保存自己的深度恋技，根節(jié)點(diǎn)的深度為0
* @支持重復(fù)元素的二分搜索樹(shù)(推薦方式拇舀，在內(nèi)部增加一個(gè)成員變量count記錄個(gè)數(shù))
* @leetCode中關(guān)于數(shù)的習(xí)題(將所有課程學(xué)完了，沒(méi)事兒的時(shí)候可以研究leetCode上面的問(wèn)題)
* */
/**某個(gè)值（可以不包含在節(jié)點(diǎn)中）的floor 比此值小的最大的元素*/
public E floor(E e){
return floor(root, e, e);
}
// temp 保存遍歷過(guò)的比次數(shù)小的值,初試值為自己蜻底，到終止條件可以根據(jù)此判斷是否遍歷過(guò)小于自己的值
private E floor(Node node, E e, E temp){
/**注意：
* 當(dāng)遍歷當(dāng)前節(jié)點(diǎn)的時(shí)候骄崩，如果當(dāng)前節(jié)點(diǎn)的值大于等于自己，需要在左子樹(shù)中尋找合適的節(jié)點(diǎn)，
* 如果左子樹(shù)存在要拂，就繼續(xù)遍歷抠璃，如果不存在左子樹(shù)，判斷之前是否遍歷過(guò)比自己小的節(jié)點(diǎn)脱惰，有則返回搏嗡，
* 沒(méi)有沒(méi)有，說(shuō)明此樹(shù)中不存在這樣的floor枪芒，拋出異常彻况！
*
* 當(dāng)遍歷當(dāng)前節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)的值小于自己舅踪，需要在當(dāng)前節(jié)點(diǎn)的右子樹(shù)去尋找答案纽甘，同時(shí)將temp置為當(dāng)前節(jié)點(diǎn)
* (當(dāng)前節(jié)點(diǎn)可能就是那個(gè)floor),如果存在右子樹(shù)，繼續(xù)遍歷抽碌，如果不存在悍赢，則返回當(dāng)前temp;
* */
if(e.compareTo(node.e) <= 0){
if(node.left != null){
return floor(node.left, e, temp);
} else {
if(temp.compareTo(e) < 0)
return temp;
else
throw new IllegalArgumentException("Seek failed, no such floor!");
}
} else {
temp = node.e;
if(node.right != null){
return floor(node.right, e, temp);
} else {
return temp;
}
}
}
/**某個(gè)值（可以不包含在節(jié)點(diǎn)中）的ceil 比此值大的最小的那個(gè)元素
* 原理與floor相反*/
public E ceil(E e){
return ceil(root, e, e);
}
private E ceil(Node node, E e, E temp){
if(e.compareTo(node.e) < 0){
temp = node.e;
if(node.left != null){
return ceil(node.left, e, temp);
} else {
return temp;
}
} else {
if(node.right != null){
return ceil(node.right , e , temp);
} else {
if(temp.compareTo(e) > 0)
return temp;
else
throw new IllegalArgumentException("Seek failed, no such ceil");
}
}
}
}
打印一顆二分搜索樹(shù)
package bannerySearchTree;
import java.util.LinkedList;
import java.util.Queue;
/**打印一棵樹(shù)，為了滿足打印需求而設(shè)計(jì)的樹(shù)货徙，訓(xùn)練而已左权！提供的功能只與打印相關(guān)。
* 假設(shè)所有節(jié)點(diǎn)的數(shù)都小于10痴颊，大于0赏迟，整型；
* 如果數(shù)中的位數(shù)不確定蠢棱，打印十分困難锌杀，得找到最大數(shù)的位數(shù)，
* 然后以此寬度為基數(shù)進(jìn)行設(shè)計(jì)....總之泻仙，先做最簡(jiǎn)單的８庠佟！玉转！
* 以所有節(jié)點(diǎn)的數(shù)為一個(gè)一位數(shù)突想，最深度n(深度從0開(kāi)始)的一層之間的空隙為基準(zhǔn)，
* 按照每一深度最左邊的空格數(shù)為2^(n-1)-1, 每層元素與元素之間的空格數(shù)為(2^(n-1)-1)*2+1,
* 每層元素的個(gè)數(shù)為2^n(遇到特殊節(jié)點(diǎn)的值打印一個(gè)空白)進(jìn)行循環(huán)打印*/
public class BSTPrint<E extends Comparable<E>>{
private class Node {
E e;
Node left, right;
int deep; // 記錄深度,從0開(kāi)始
boolean printAble; // 記錄當(dāng)前節(jié)點(diǎn)是否允許打印究抓，默認(rèn)允許打印
public Node(E e){
this.e = e;
this.left = this.right = null;
this.printAble = true;
}
}
//
public Node root; // 根節(jié)點(diǎn)
public int deepest; // 記錄最深的深度
public int size; // 記錄數(shù)據(jù)個(gè)數(shù)
public BSTPrint(){
this.root = null;
this.deepest = 0;
this.size = 0;
}
public void add(E e){
root = this.add(root, -1, e);
}
private Node add(Node node, int deep, E e){
if(node == null){
Node newNode = new Node(e);
newNode.deep = deep + 1;
this.deepest = newNode.deep > this.deepest? newNode.deep: this.deepest;
size ++;
return newNode;
}
if(e.compareTo(node.e) < 0){
node.left = add(node.left, node.deep, e);
return node;
} else {
node.right = add(node.right, node.deep, e);
return node;
}
}
/**打印節(jié)點(diǎn)*/
public void printTree(){
/**將樹(shù)補(bǔ)全, 在父節(jié)點(diǎn)操作子節(jié)點(diǎn)*/
if(root != null && this.deepest != 0)
addFullTree(root);
/** 對(duì)樹(shù)進(jìn)行層序遍歷猾担，是完整二叉樹(shù)*/
Queue<Node> q = new LinkedList<>();
q.add(root);
int currentLayer = root.deep - 1; // 保存當(dāng)前所打印的深度,初始化為一個(gè)不存在的層
char line = '|';
String nextLine = ""; // 保存待打印的值
while (!q.isEmpty()){
Node node = q.remove();
if(node.deep != currentLayer){
// 轉(zhuǎn)換到下一行
currentLayer = node.deep;
// 打印上次保存的一行信息
System.out.println(nextLine);
nextLine = "\n";
// 打印每一行前面的空白并將空白賦值給緩存
String leftSpace = "";
for(int i = 0; i < Math.pow(2, this.deepest - node.deep) - 1; i++)
leftSpace += ' ';
System.out.print(leftSpace);
nextLine += leftSpace;
// 判斷是否能夠打印，打印連接線并將該值加入緩存
if(node.printAble){
System.out.print(line);
nextLine += node.e;
} else {
System.out.print(' ');
nextLine += ' ';
}
} else {
// 打印每個(gè)元素之間的間隔空格
String betweenSpace = "";
for(int i = 0; i < (Math.pow(2, this.deepest - node.deep) - 1) * 2 + 1; i++)
betweenSpace += ' ';
System.out.print(betweenSpace);
nextLine += betweenSpace;
// 判斷是否能夠打印刺下，打印連接線并將該值加入緩存
if(node.printAble){
System.out.print(line);
nextLine += node.e;
} else {
System.out.print(' ');
nextLine += ' ';
}
}
if(node.left != null)
q.add(node.left);
if(node.right != null)
q.add(node.right);
}
System.out.println(nextLine);
}
private void addFullTree(Node pre){
if(pre.deep + 1 <= this.deepest && pre.left == null){
pre.left = new Node(pre.e);
pre.left.deep = pre.deep + 1;
pre.left.printAble = false;
size ++;
}
if(pre.deep + 1 <= this.deepest && pre.right == null){
pre.right = new Node(pre.e);
pre.right.deep = pre.deep + 1;
pre.right.printAble = false;
size ++;
}
if(pre.deep < this.deepest) {
addFullTree(pre.left);
addFullTree(pre.right);
}
}
public static void main(String[] args) {
BSTPrint<Integer> bst = new BSTPrint<>();
int[] numbers = {8, 10, 5, 4, 12, 7, 9, 13, 6, 3, 11};
for (int i = 0; i < numbers.length; i++) {
bst.add(numbers[i]);
}
bst.printTree();
}
}
帶有size的二分搜索樹(shù)垒探，并且可以查詢排行的元素與元素的排行
package bannerySearchTree;
public class BSTSize<E extends Comparable<E>> {
/**
維護(hù)size的二分搜索樹(shù)，在節(jié)點(diǎn)中保存該節(jié)點(diǎn)包含的總結(jié)點(diǎn)數(shù)怠李，包含自己圾叼，
rank: 這個(gè)元素在數(shù)中排名第幾蛤克？（推薦方式：）
select: 排名是第幾的元素是誰(shuí)？（推薦方式：在節(jié)點(diǎn)中保存該節(jié)點(diǎn)包含的總結(jié)點(diǎn)數(shù)夷蚊，包含自己）
只包含添加功能构挤，目前不包含刪除元素的功能(如果做刪除功能，需要先做出刪除最大值惕鼓，最小值筋现，然后再做
刪除任意值復(fù)用刪除最小值的方法<后繼></>)*/
private class Node{
E e;
Node left, right;
int size;
public Node(E e){
this.e = e;
this.left = this.right = null;
this.size = 1;
}
}
private Node root;
private int totalSize;
public BSTSize(){
this.root = null;
this.totalSize = 0;
}
/**添加一個(gè)元素，添加成功之后箱歧，將所有的父節(jié)點(diǎn)自增1
* 注意：目前不支持添加已經(jīng)存在的元素*/
public void add(E e){
root = this.add(root, e);
}
private Node add(Node node, E e){
if(node == null){
this.totalSize ++;
return new Node(e);
}
if(e.compareTo(node.e) < 0){
node.left = this.add(node.left, e);
node.size ++;
return node;
} else if(e.compareTo(node.e) > 0){
node.right = this.add(node.right, e);
node.size ++;
return node;
} else {
throw new IllegalArgumentException("Add failed, can not add same element");
}
}
/**rank: 這個(gè)元素在數(shù)中排名第幾
* 算法簡(jiǎn)介：
* 從根節(jié)點(diǎn)開(kāi)始矾飞，與當(dāng)前節(jié)點(diǎn)比較，如果當(dāng)前節(jié)點(diǎn)與自己相等呀邢，返回減去右子樹(shù)個(gè)數(shù)的當(dāng)前size
* 如果當(dāng)前節(jié)點(diǎn)大于自己洒沦，遍歷左子節(jié)點(diǎn)，返回遍歷的左節(jié)點(diǎn)的返回值
* 如果當(dāng)前節(jié)點(diǎn)小于自己价淌，遍歷右子節(jié)點(diǎn)申眼，返回當(dāng) 前節(jié)點(diǎn)減去右節(jié)點(diǎn)的size在加上遍歷的右子樹(shù)的返回值*/
public int rank(E e){
return this.rank(root, e);
}
private int rank(Node node, E e){
if(node == null){
throw new IllegalArgumentException("Seek failed, no such element");
} else
if(e.compareTo(node.e) == 0){
if(node.right == null){
return node.size;
} else {
return node.size - node.right.size;
}
} else if(e.compareTo(node.e) < 0){
return this.rank(node.left, e);
} else {
if(node.right != null)
return node.size - node.right.size + this.rank(node.right, e);
else
throw new IllegalArgumentException("Seek failed, no such element");
}
}
/**select: 排名是第幾的元素是誰(shuí)？*/
public E select(int n){
if(n < 1)
throw new IllegalArgumentException("Fained failed, order is too small!");
if(n > this.totalSize)
throw new IllegalArgumentException("Fained failed, order is too large!");
return select(root, 0, n);
}
/**node為當(dāng)前節(jié)點(diǎn)蝉衣， position遍歷過(guò)的節(jié)點(diǎn)的位置括尸，初始化為0，n為需要尋找的位置
* 調(diào)用遞歸之前已經(jīng)處理了異常值病毡，在這里面就可以不用處理了濒翻！*/
private E select(Node node, int position, int n){
/**計(jì)算當(dāng)前節(jié)點(diǎn)所處的位置*/
int tempPosition = position;
if(node.right != null)
tempPosition = position + node.size - node.right.size;
else
tempPosition = position + node.size;
/**判斷當(dāng)前的位置并分配操作！*/
if(tempPosition == n)
return node.e;
else if(tempPosition < n)
return select(node.right, tempPosition, n);
else
return select(node.left, position, n);
}
public static void main(String[] args){
BSTSize<Integer> bst = new BSTSize<>();
int[] numbers = {8, 10, 5, 4, 12, 7, 9, 13, 6, 3, 11};
for(int i = 0; i < numbers.length; i ++){
bst.add(numbers[i]);
}
System.out.println(bst.rank(7));
System.out.println(bst.select(4));
}
}
