引出
1.樹的出現(xiàn)：解決鏈表線性訪問時間太慢，樹的時間復(fù)雜度O(logN)；
2.二叉樹的定義，最多兩個兒子節(jié)點(diǎn)；
3.二叉查找樹，左小，右大，中居中；remove方法，兩種，只有一個兒子節(jié)點(diǎn)，有兩個兒子節(jié)點(diǎn)；
4.AVL樹，在二叉查找樹基礎(chǔ)上加平衡條件，旋轉(zhuǎn)方法，單旋轉(zhuǎn)，雙旋轉(zhuǎn)；
5.樹的遍歷方式，中序遍歷，左根右；后續(xù)遍歷，左右根；先序遍歷，根左右；
什么是樹Tree？
對于大量的輸入數(shù)據(jù)，鏈表的線性訪問時間太慢，不宜使用。本章討論一種簡單的數(shù)據(jù)結(jié)構(gòu)，其大部分操作的運(yùn)行時間平均為O(logN)。
這種數(shù)據(jù)結(jié)構(gòu)叫作二叉查找樹(binary search tree)。二又查找樹是兩種庫集合類TreeSet和TreeMap實(shí)現(xiàn)的基礎(chǔ)，它們用于許多應(yīng)用之中。在計算機(jī)科學(xué)中樹(tree)是非常有用的抽象概念，因此，我們將討論樹在其他更一般的應(yīng)用中的使用。
- 看到樹是如何用于實(shí)現(xiàn)幾個流行的操作系統(tǒng)中的文件系統(tǒng)的。
- 看到樹如何能夠用來計算算術(shù)表達(dá)式的值。
- 指出如何利用樹支持以O(shè)(logN)平均時間進(jìn)行的各種搜索操作，以及如何細(xì)化以得到最
壞情況時間界O(logN)。我們還將討論當(dāng)數(shù)據(jù)被存放在磁盤上時如何來實(shí)現(xiàn)這些操作。 - 討論并使用TreeSet類和TreeMap類。
樹(Tree)可以用幾種方式定義。定義樹的一種自然的方式是遞歸的方式。一棵樹是一些節(jié)點(diǎn)的集合。這個集合可以是空集；若不是空集，則樹由稱作根 (root) 的節(jié)點(diǎn) r 以及0個或多個非空的（子）樹 T1,T2,…,Tk 組成，這些子樹中每一棵的根都被來自根r的一條有向的邊(edge)所連結(jié)。
每一棵子樹的根叫作根r的兒子(child),而r是每一棵子樹的根的父親(parent)。
樹的實(shí)現(xiàn)
實(shí)現(xiàn)樹的一種方法可以是在每一個節(jié)點(diǎn)除數(shù)據(jù)外還要有一些鏈，使得該節(jié)點(diǎn)的每一個兒子都有一個鏈指向它。然而，由于每個節(jié)點(diǎn)的兒子數(shù)可以變化很大并且事先不知道，因此在數(shù)據(jù)結(jié)構(gòu)中建立到各（兒）子節(jié)點(diǎn)直接的鏈接是不可行的，因?yàn)檫@樣會產(chǎn)生太多浪費(fèi)的空間。實(shí)際上解決方法很簡單：將每個節(jié)點(diǎn)的所有兒子都放在樹節(jié)點(diǎn)的鏈表中。
下圖指出一棵樹如何用這種實(shí)現(xiàn)方法表示出來。圖中向下的箭頭是指向firstChild(第一兒子)的鏈，而水平箭頭是指向nextSibling(下一兄弟)的鏈。因?yàn)閚ull鏈太多了，所以沒有把它們畫出。
樹的深度是指從根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的路徑上的節(jié)點(diǎn)數(shù)。換句話說，樹的深度表示樹中最長路徑的長度。
在一棵樹中，根節(jié)點(diǎn)位于第一層，它沒有父節(jié)點(diǎn)。每個非葉子節(jié)點(diǎn)的深度是其父節(jié)點(diǎn)的深度加1。葉子節(jié)點(diǎn)的深度是從根節(jié)點(diǎn)到該葉子節(jié)點(diǎn)的路徑上的節(jié)點(diǎn)數(shù)。
樹的深度可以用來衡量樹的高度或者樹的層數(shù)。深度為0的樹只有一個根節(jié)點(diǎn)，深度為1的樹有一個根節(jié)點(diǎn)和一個子節(jié)點(diǎn)，以此類推。
二叉樹binary tree
二叉樹(binary tree)是一棵樹，其中每個節(jié)點(diǎn)都不能有多于兩個的兒子。一棵由一個根和兩棵子樹組成的二叉樹，子樹TL,和TK均可能為空。
因?yàn)橐粋€二叉樹節(jié)點(diǎn)最多有兩個子節(jié)點(diǎn)，所以我們可以保存直接鏈接到它們的鏈。樹節(jié)點(diǎn)的聲明在結(jié)構(gòu)上類似于雙鏈表的聲明，在聲明中，節(jié)點(diǎn)就是由element(元素)的信息加上兩個到其他節(jié)點(diǎn)的引用( Left 和 Right)組成的結(jié)構(gòu)。
節(jié)點(diǎn)的實(shí)現(xiàn)
toString方法
/**
* 內(nèi)部類，節(jié)點(diǎn)，元素，左節(jié)點(diǎn)，右節(jié)點(diǎn)。類似于鏈表
* @param <T>
*/
public static class BinaryNode<T>{
T element; // 當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)
BinaryNode<T> left; // 左側(cè)的節(jié)點(diǎn)
BinaryNode<T> right; // 右側(cè)的節(jié)點(diǎn)
public BinaryNode(T element) {
this(element,null,null);
}
public BinaryNode(T element, BinaryNode<T> left, BinaryNode<T> right) {
this.element = element;
this.left = left;
this.right = right;
}
@Override
public String toString() {
String leftStr = null;
String rightStr = null;
if (left!=null) {
leftStr = left.element.toString();
}
if (right!=null){
rightStr = right.element.toString();
}
String sTree = " %s\n" +
" / \\\n" +
" %s %s";
System.out.printf(sTree,element.toString(),leftStr,rightStr);
System.out.println();
return "BinaryNode{" +
"element=" + element +
", left=" + leftStr +
", right=" + rightStr +
'}';
}
}
查找樹ADT——二叉查找樹Binary Search Tree
二叉樹的一個重要的應(yīng)用是它們在查找中的使用。假設(shè)樹中的每個節(jié)點(diǎn)存儲一項(xiàng)數(shù)據(jù)。在我們的例子中，雖然任意復(fù)雜的項(xiàng)在Jva中都容易處理，但為簡單起見還是假設(shè)它們是整數(shù)。還將假設(shè)所有的項(xiàng)都是互異的，以后再處理有重復(fù)元的情況。
使二叉樹成為二叉查找樹的性質(zhì)是，對于樹中的每個節(jié)點(diǎn)X,它的左子樹中所有項(xiàng)的值小于X中的項(xiàng)，而它的右子樹中所有項(xiàng)的值大于X中的項(xiàng)。注意，這意味著該樹所有的元素可以用某種一致的方式排序。
二叉查找樹（Binary Search Tree，簡稱BST）是一種特殊的二叉樹，它具有以下性質(zhì)：
- 對于樹中的每個節(jié)點(diǎn)，其左子樹中的所有節(jié)點(diǎn)的值都小于該節(jié)點(diǎn)的值，而右子樹中的所有節(jié)點(diǎn)的值都大于該節(jié)點(diǎn)的值。
- 對于樹中的每個節(jié)點(diǎn)，其左子樹和右子樹也都是二叉查找樹。
基于這些性質(zhì)，二叉查找樹可以支持高效的查找、插入和刪除操作。
6
/ \
2 8
/ \
1 4
/
3
提供一個生成一顆樹的方法
/**
*
* 6
* / \
* 2 8
* / \
* 1 4
* /
* 3
* @return 獲得一二叉樹
*/
public BinarySearchTree<Integer> getIntegerTree() {
BinaryNode<Integer> root = new BinaryNode<>(6);
root.left = new BinaryNode<>(2);
root.right = new BinaryNode<>(8);
root.left.left = new BinaryNode<>(1);
root.left.right = new BinaryNode<>(4);
root.left.right.left = new BinaryNode<>(3);
return new BinarySearchTree<>(root);
}
1.contains方法
如果在樹T中存在含有項(xiàng)X的節(jié)點(diǎn)，那么這個操作需要返回true,如果這樣的節(jié)點(diǎn)不存在則返回false。樹的結(jié)構(gòu)使得這種操作很簡單。如果T是空集，那么可以就返回false。否則，如果存儲在T處的項(xiàng)是X,那么可以返回true。否則，我們對樹T的左子樹或右子樹進(jìn)行一次遞歸調(diào)用，這依賴于X與存儲在T中的項(xiàng)的關(guān)系。
關(guān)鍵的問題是首先要對是否空樹進(jìn)行測試，否則我們就會生成一個企圖通過null引用訪問數(shù)據(jù)域的NullPointerException異常。
/**
* 從根節(jié)點(diǎn)開始，遞歸查找，判斷x是否在樹中
* @param x 判斷的元素
* @param node 從哪個節(jié)點(diǎn)開始判斷
* @return
*/
public boolean contains(T x,BinaryNode<T> node){
if (node==null){// 根節(jié)點(diǎn)為null，空樹
return false;
}
// 進(jìn)行比較
int compareResult = x.compareTo(node.element);
if (compareResult >0){
// 說明x大于當(dāng)前節(jié)點(diǎn)，則往右走
System.out.println("right: "+x+"--node: "+node.element);
return contains(x, node.right);
}else if(compareResult <0){
System.out.println("left: "+x+"--node: "+node.element);
return contains(x, node.left); // 往左走
}else {
return true; // 找到了
}
}
查找的順序
2.findMax和findMin方法
最大
最小
/**
* 查找最大值，需要保證不是空樹
* @return
*/
public T findMax(){
if (isEmpty()){
System.out.println("空樹");
return null;
}
// 根據(jù)二叉查找樹的定義，最大值就是不斷往右找
BinaryNode<T> right = root.right;
T max = root.element;
while (right!=null){
max = right.element;
right = right.right;
}
return max;
}
/**
* 從某個節(jié)點(diǎn)開始找最大值
* @param node 開始的節(jié)點(diǎn)
* @return
*/
public T findMax(BinaryNode<T> node){
if (isEmpty()){
System.out.println("空樹");
return null;
}
if (node!=null){
while (node.right!=null){
node = node.right;
}
return node.element;
}
return null;
}
/**
*
* @param node 開始查找的節(jié)點(diǎn)
* @return
*/
public T findMin(BinaryNode<T> node){
if (isEmpty()){
System.out.println("空樹");
return null;
}
if (node==null){
return null;
}else if (node.left==null){
return node.element;
}
return findMin(node.left);
}
3.insert方法
進(jìn)行插入操作的例程在概念上是簡單的。為了將X插入到樹T中，你可以像用contains那樣沿著樹查找。如果找到X,則什么也不用做（或做一些“更新”）。否則，將X插入到遍歷的路徑上的最后一點(diǎn)上。
下圖顯示實(shí)際的插入情況。為了插入5，我們遍歷該樹就好像在運(yùn)行contains。在具有關(guān)鍵字4的節(jié)點(diǎn)處，我們需要向右行進(jìn)，但右邊不存在子樹，因此5不在這棵樹上，從而這個位置就是所要插入的位置。
進(jìn)行插入的測試
/**
* 獲取insert操作后的運(yùn)行腳本
*/
String scriptJ = "root";
/**
* 插入元素，和判斷是否包含某個元素的思路一樣
* @param x 想要插入的元素
* @param t 從哪個節(jié)點(diǎn)開始
* @return
*/
public BinaryNode<T> insert(T x,BinaryNode<T> t){
// 最后5又到了這里
if (t==null){
// System.out.println("isHere???");
return new BinaryNode<T>(x);
}
// 從t節(jié)點(diǎn)開始把x元素插入到樹中
int compareTo = x.compareTo(t.element);
if (compareTo>0){
// x比當(dāng)前比較的節(jié)點(diǎn)的元素大，向右查找
scriptJ = scriptJ + ".right";
// System.out.println("Turn to right："+t.element);
return insert(x, t.right);
}else if (compareTo<0){
// System.out.println("Turn to left："+t.element);
scriptJ = scriptJ + ".left";
return insert(x,t.left);
}else {
;
}
return t;
}
進(jìn)行測試：flag腳本執(zhí)行未成功
System.out.println("插入新的元素");
BinarySearchTree.BinaryNode<Integer> insert = binarySearchTree.insert(5, binarySearchTree.root);
System.out.println(insert);
System.out.println(binarySearchTree.scriptJ); // .left.right.right
System.out.println(binarySearchTree.root.left.right);
System.out.println("執(zhí)行插入：binarySearchTree."+binarySearchTree.scriptJ + "=insert");
binarySearchTree.root.left.right.right = insert; // 根節(jié)點(diǎn)的左右為插入的新節(jié)點(diǎn)
System.out.println(binarySearchTree.root.left.right.right);
System.out.println("執(zhí)行插入后的節(jié)點(diǎn)4："+binarySearchTree.root.left.right);
System.out.println("#######################################");
ScriptEngineManager manager = new ScriptEngineManager();
ScriptEngine engine = manager.getEngineByName("js");
Bindings bindings = new SimpleBindings();
bindings.put("binarySearchTree", binarySearchTree);
// String script = "binarySearchTree.root.left.right.right=insert";
String script = "binarySearchTree.root";
Object result = engine.eval(script, bindings);
System.out.println(result);
4.remove方法（復(fù)雜）
正如許多數(shù)據(jù)結(jié)構(gòu)一樣，最困難的操作是remove(刪除)。一旦我們發(fā)現(xiàn)要被刪除的節(jié)點(diǎn)，就需要考慮幾種可能的情況。如果節(jié)點(diǎn)是一片樹葉，那么它可以被立即刪除。如果節(jié)點(diǎn)有一個兒子，則該節(jié)點(diǎn)可以在其父節(jié)點(diǎn)調(diào)整自己的鏈以繞過該節(jié)點(diǎn)后被刪除（為了清楚起見，我們將明確地畫出鏈的指向）
復(fù)雜的情況是處理具有兩個兒子的節(jié)點(diǎn)。一般的刪除策略是用其右子樹的最小的數(shù)據(jù)（很容易找到)代替該節(jié)點(diǎn)的數(shù)據(jù)并遞歸地刪除那個節(jié)點(diǎn)（現(xiàn)在它是空的）。因?yàn)橛易訕渲械淖钚〉墓?jié)點(diǎn)不可能有左兒子，所以第二次remove要容易。圖4-24顯示一棵初始的樹及其中一個節(jié)點(diǎn)被刪除后的結(jié)果。要被刪除的節(jié)點(diǎn)是根的左兒子；其關(guān)鍵字是2。它被其右子樹中的最小數(shù)據(jù)3所代替，然后關(guān)鍵字是3的原節(jié)點(diǎn)如前例那樣被刪除。
6
/ \
2 8
/ \
1 5
/
3
\
4
/**
* 刪除元素
* @param x 要刪除的元素
* @param t 開始遍歷的節(jié)點(diǎn)
* @return
*/
public BinaryNode<T> remove(T x,BinaryNode<T> t){
if (t==null){
return null; // 要刪除的元素未找到
}
int compareTo = x.compareTo(t.element);
if (compareTo>0){
// 要刪除的元素比當(dāng)前節(jié)點(diǎn)的元素的值大，往右走
return remove(x, t.right);
}else if (compareTo<0){
return remove(x,t.left); // 往左走
}else{
// 找到了要刪除的節(jié)點(diǎn)
System.out.println(t);
if (t.left!=null && t.right!=null){
System.out.println("該節(jié)點(diǎn)有兩個兒子節(jié)點(diǎn)");
t.element = findMin(t.right); // 用右側(cè)的最小數(shù)據(jù)代替當(dāng)前的數(shù)據(jù)
System.out.println("用右側(cè)最小數(shù)據(jù)代替當(dāng)前數(shù)據(jù)后的節(jié)點(diǎn)");
System.out.println(t);
// 還要把3節(jié)點(diǎn)刪除
t.right = remove(t.element, t.right);
}else {
System.out.println("該節(jié)點(diǎn)只有一個兒子節(jié)點(diǎn)");
// 如果該節(jié)點(diǎn)只有1個兒子
t = (t.left != null) ? t.left : t.right;
System.out.println("刪除原有節(jié)點(diǎn)后，該節(jié)點(diǎn)被兒子節(jié)點(diǎn)替換后");
System.out.println(t);
}
return t;
}
}
刪除只有一個兒子的節(jié)點(diǎn)4
刪除有兩個兒子的節(jié)點(diǎn)
二叉查找樹的深度
如果向一棵樹輸入預(yù)先排好序的數(shù)據(jù)，那么一連串insert操作將花費(fèi)二次的時間，而鏈表實(shí)現(xiàn)的代價會非常巨大，因?yàn)榇藭r的樹將只由那些沒有左兒子的節(jié)點(diǎn)組成。一種解決辦法就是要有一個稱為平衡(balance)的附加的結(jié)構(gòu)條件：任何節(jié)點(diǎn)的深度均不得過深。許多一般的算法都能實(shí)現(xiàn)平衡樹。
但是，大部分算法都要比標(biāo)準(zhǔn)的二叉查找樹復(fù)雜得多，而且更新要平均花費(fèi)更長的時間。不過，它們確實(shí)防止了處理起來非常麻煩的一些簡單情形。下面，我們將介紹最古老的一種平衡查找樹，即AVL樹。
AVL(Adelson-Velskii和Landis)樹——平衡條件(balance condition)的二叉查找樹
AVL(Adelson-Velskii和Landis)樹是帶有**平衡條件(balance condition)**的二叉查找樹。這個平衡條件必須要容易保持，而且它保證樹的深度須是O(1ogN)。最簡單的想法是要求左右子樹具有相同的高度。如圖4-28所示，這種想法并不強(qiáng)求樹的深度要淺。
另一種平衡條件是要求每個節(jié)點(diǎn)都必須有相同高度的左子樹和右子樹。雖然這種平衡條件保證了樹的深度小，但是它太嚴(yán)格而難以使用，需要放寬條件。
一棵AVL樹是其每個節(jié)點(diǎn)的左子樹和右子樹的高度最多差1的二叉查找樹（空樹的高度定義為-1)。在圖4-29中，左邊的樹是AVL樹，但是右邊的樹不是。
插入元素-旋轉(zhuǎn)(rotation)
因此，除去可能的插入外（我們將假設(shè)懶惰刪除），所有的樹操作都可以以時間O(logN)執(zhí)行。當(dāng)進(jìn)行插入操作時，我們需要更新通向根節(jié)點(diǎn)路徑上那些節(jié)點(diǎn)的所有平衡信息，而插人操作隱含著困難的原因在于，插入一個節(jié)點(diǎn)可能破壞AVL樹的特性（例如，將6插入到圖4-29中的AVL樹中將會破壞關(guān)鍵字為8的節(jié)點(diǎn)處的平衡條件)。如果發(fā)生這種情況，那么就要在考慮
這一步插入完成之前恢復(fù)平衡的性質(zhì)。事實(shí)上，這總可以通過對樹進(jìn)行簡單的修正來做到，我們稱其為旋轉(zhuǎn)(rotation)。
在插入以后，只有那些從插入點(diǎn)到根節(jié)點(diǎn)的路徑上的節(jié)點(diǎn)的平衡可能被改變，因?yàn)橹挥羞@些節(jié)點(diǎn)的子樹可能發(fā)生變化。當(dāng)我們沿著這條路徑上行到根并更新平衡信息時，可以發(fā)現(xiàn)一個節(jié)點(diǎn)，它的新平衡破壞了AVL條件。我們將指出如何在第一個這樣的節(jié)點(diǎn)（即最深的節(jié)點(diǎn)）重新平衡這棵樹，并證明這一重新平衡保證整個樹滿足AVL性質(zhì)。
單旋轉(zhuǎn)：左左，右右
圖4-32顯示了在將6插人左邊原始的AVL樹后節(jié)點(diǎn)8便不再平衡。于是，我們在7和8之間做一次單旋轉(zhuǎn)，結(jié)果得到右邊的樹。
雙旋轉(zhuǎn)：左右，右左
樹的遍歷
7
/ \
4 13
/ \ / \
2 6 11 15
/ \ / / \ / \
1 3 5 9 12 14 16
/ \
8 10
1.中序遍歷：依序列
中序遍歷（Inorder Traversal）是一種樹的遍歷方式，它的遍歷順序是先遞歸地遍歷左子樹，然后訪問根節(jié)點(diǎn)，最后遞歸地遍歷右子樹。中序遍歷的順序可以表示為：左子樹 -> 根節(jié)點(diǎn) -> 右子樹。
正如我們前面看到的，這類例程當(dāng)用于樹的時候則稱為中序遍歷（由于它依序列出了各項(xiàng)，因此是有意義的）。一個中序遍歷的一般方法是首先處理左子樹，然后是當(dāng)前的節(jié)點(diǎn)，最后處理右子樹。這個算法的有趣部分除它簡單的特性外，還在于其總的運(yùn)行時間是O(N)。這是因?yàn)樵跇涞拿恳粋€節(jié)點(diǎn)處進(jìn)行的工作是常數(shù)時間的。每一個節(jié)點(diǎn)訪問一次，而在每一個節(jié)點(diǎn)進(jìn)行的工作是檢測是否ull、建立兩個方法調(diào)用、并執(zhí)行println。由于在每個節(jié)點(diǎn)的工作花費(fèi)常數(shù)時間以及總共有N個節(jié)點(diǎn)，因此運(yùn)行時間為O(N)。
2.后序遍歷：樹的深度
后序遍歷（Postorder Traversal）是一種樹的遍歷方式，它的遍歷順序是先遞歸地遍歷左子樹，然后遞歸地遍歷右子樹，最后訪問根節(jié)點(diǎn)。后序遍歷的順序可以表示為：左子樹 -> 右子樹 -> 根節(jié)點(diǎn)。
有時我們需要先處理兩棵子樹然后才能處理當(dāng)前節(jié)點(diǎn)。例如，為了計算一個節(jié)點(diǎn)的高度，首先需要知道它的子樹的高度程序就是計算高度的。由于檢查一些特殊的情況總是有益的——當(dāng)涉及遞歸時尤其重要，因此要注意這個例程聲明樹葉的高度為零，這是正確的。這種一般的遍歷順序叫作后序遍歷，我們在前面也見到過。因?yàn)樵诿總€節(jié)點(diǎn)的工作花費(fèi)常
數(shù)時間，所以總的運(yùn)行時間也是O(N)。
樹的深度是指從根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的路徑上的節(jié)點(diǎn)數(shù)。換句話說，樹的深度表示樹中最長路徑的長度。
在一棵樹中，根節(jié)點(diǎn)位于第一層，它沒有父節(jié)點(diǎn)。每個非葉子節(jié)點(diǎn)的深度是其父節(jié)點(diǎn)的深度加1。葉子節(jié)點(diǎn)的深度是從根節(jié)點(diǎn)到該葉子節(jié)點(diǎn)的路徑上的節(jié)點(diǎn)數(shù)。
/**
* 后續(xù)遍歷：左子樹 -> 右子樹 -> 根節(jié)點(diǎn)
* @param t
* @return
*/
public int height(BinaryNode<T> t){
if (t==null){
return -1;
}else {
return 1+Math.max(height(t.left), height(t.right));
}
}
3.先序遍歷
先序遍歷（Preorder Traversal）是一種樹的遍歷方式，它的遍歷順序是先訪問根節(jié)點(diǎn)，然后遞歸地遍歷左子樹，最后遞歸地遍歷右子樹。先序遍歷的順序可以表示為：根節(jié)點(diǎn) -> 左子樹 -> 右子樹。
/**
* 先序遍歷：根節(jié)點(diǎn) -> 左子樹 -> 右子樹
* @param root
*/
public void preorderTraversal(BinaryNode<T> root) {
if (root == null) {
return;
}
System.out.print(root.element + " ");
preorderTraversal(root.left);
preorderTraversal(root.right);
}
完整代碼
BinarySearchTree<T extends Comparable<? super T>>實(shí)體類
package com.tianju.book.jpa.tree;
import com.baomidou.mybatisplus.extension.api.R;
import com.github.pagehelper.PageHelper;
public class BinarySearchTree<T extends Comparable<? super T> >{
public BinaryNode<T> root; // 根節(jié)點(diǎn)
/**
* 內(nèi)部類，節(jié)點(diǎn)，元素，左節(jié)點(diǎn)，右節(jié)點(diǎn)。類似于鏈表
* @param <T>
*/
public static class BinaryNode<T>{
T element; // 當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)
BinaryNode<T> left; // 左側(cè)的節(jié)點(diǎn)
BinaryNode<T> right; // 右側(cè)的節(jié)點(diǎn)
public BinaryNode(T element) {
this(element,null,null);
}
public BinaryNode(T element, BinaryNode<T> left, BinaryNode<T> right) {
this.element = element;
this.left = left;
this.right = right;
}
@Override
public String toString() {
String leftStr = null;
String rightStr = null;
if (left!=null) {
leftStr = left.element.toString();
}
if (right!=null){
rightStr = right.element.toString();
}
String sTree = " %s\n" +
" / \\\n" +
" %s %s";
System.out.printf(sTree,element.toString(),leftStr,rightStr);
System.out.println();
return "BinaryNode{" +
"element=" + element +
", left=" + leftStr +
", right=" + rightStr +
'}';
}
}
/**
*
* 6
* / \
* 2 8
* / \
* 1 4
* /
* 3
* @return 獲得一二叉樹
*/
public BinarySearchTree<Integer> getIntegerTree() {
BinaryNode<Integer> root = new BinaryNode<>(6);
root.left = new BinaryNode<>(2);
root.right = new BinaryNode<>(8);
root.left.left = new BinaryNode<>(1);
root.left.right = new BinaryNode<>(4);
root.left.right.left = new BinaryNode<>(3);
return new BinarySearchTree<>(root);
}
/**
* 6
* / \
* 2 8
* / \
* 1 5
* /
* 3
* \
* 4
* @return
*/
public BinarySearchTree<Integer> getIntegerTreeR() {
BinaryNode<Integer> root = new BinaryNode<>(6);
root.left = new BinaryNode<>(2);
root.right = new BinaryNode<>(8);
root.left.left = new BinaryNode<>(1);
root.left.right = new BinaryNode<>(5);
root.left.right.left = new BinaryNode<>(3);
root.left.right.left.right = new BinaryNode<>(4);
return new BinarySearchTree<>(root);
}
/**
* 調(diào)用可獲得一顆平衡AVL樹
* 7
* / \
* 4 13
* / \ / \
* 2 6 11 15
* / \ / / \ / \
* 1 3 5 9 12 14 16
* / \
* 8 10
* @return 平衡AVL樹
*/
public BinarySearchTree<Integer> getBalanceTree() {
BinaryNode<Integer> root = new BinaryNode<>(7);
root.left = new BinaryNode<>(4);
root.left.left = new BinaryNode<>(2);
root.left.left.left = new BinaryNode<>(1);
root.left.left.right = new BinaryNode<>(3);
root.left.right = new BinaryNode<>(6);
root.left.right.left = new BinaryNode<>(5);
root.right = new BinaryNode<>(13);
root.right.left = new BinaryNode<>(11);
root.right.left.left = new BinaryNode<>(9);
root.right.left.left.left = new BinaryNode<>(8);
root.right.left.left.right = new BinaryNode<>(10);
root.right.left.right = new BinaryNode<>(12);
root.right.right = new BinaryNode<>(15);
root.right.right.left = new BinaryNode<>(14);
root.right.right.right = new BinaryNode<>(16);
return new BinarySearchTree<>(root);
}
public BinarySearchTree(BinaryNode<T> root) {
this.root = root;
}
public BinarySearchTree() {
}
public void makeEmpty(){
root = null;
}
public boolean isEmpty(){
return root == null;
}
/**
* 從根節(jié)點(diǎn)開始，遞歸查找，判斷x是否在樹中
* @param x 判斷的元素
* @param node 從哪個節(jié)點(diǎn)開始判斷
* @return
*/
public boolean contains(T x,BinaryNode<T> node){
if (node==null){// 找完了還沒找到
return false;
}
// 進(jìn)行比較
int compareResult = x.compareTo(node.element);
if (compareResult >0){
// 說明x大于當(dāng)前節(jié)點(diǎn)，則往右走
System.out.println("right: "+x+"--node: "+node.element);
return contains(x, node.right);
}else if(compareResult <0){
System.out.println("left: "+x+"--node: "+node.element);
return contains(x, node.left); // 往左走
}else {
return true; // 找到了
}
}
/**
* 查找最大值，需要保證不是空樹
* @return
*/
public T findMax(){
if (isEmpty()){
System.out.println("空樹");
return null;
}
// 根據(jù)二叉查找樹的定義，最大值就是不斷往右找
BinaryNode<T> right = root.right;
T max = root.element;
while (right!=null){
max = right.element;
right = right.right;
}
return max;
}
/**
* 從某個節(jié)點(diǎn)開始找最大值
* @param node 開始的節(jié)點(diǎn)
* @return
*/
public T findMax(BinaryNode<T> node){
if (isEmpty()){
System.out.println("空樹");
return null;
}
if (node!=null){
while (node.right!=null){
node = node.right;
}
return node.element;
}
return null;
}
/**
*
* @param node 開始查找的節(jié)點(diǎn)
* @return
*/
public T findMin(BinaryNode<T> node){
if (isEmpty()){
System.out.println("空樹");
return null;
}
if (node==null){
return null;
}else if (node.left==null){
return node.element;
}
return findMin(node.left);
}
/**
* 獲取insert操作后的運(yùn)行腳本
*/
String scriptJ = "root";
/**
* 插入元素，和判斷是否包含某個元素的思路一樣
* @param x 想要插入的元素
* @param t 從哪個節(jié)點(diǎn)開始
* @return
*/
public BinaryNode<T> insert(T x,BinaryNode<T> t){
// 最后5又到了這里
if (t==null){
// System.out.println("isHere???");
return new BinaryNode<T>(x);
}
// 從t節(jié)點(diǎn)開始把x元素插入到樹中
int compareTo = x.compareTo(t.element);
if (compareTo>0){
// x比當(dāng)前比較的節(jié)點(diǎn)的元素大，向右查找
scriptJ = scriptJ + ".right";
// System.out.println("Turn to right："+t.element);
return insert(x, t.right);
}else if (compareTo<0){
// System.out.println("Turn to left："+t.element);
scriptJ = scriptJ + ".left";
return insert(x,t.left);
}else {
;
}
return t;
}
/**
* 刪除元素
* @param x 要刪除的元素
* @param t 開始遍歷的節(jié)點(diǎn)
* @return
*/
public BinaryNode<T> remove(T x,BinaryNode<T> t){
if (t==null){
return null; // 要刪除的元素未找到
}
int compareTo = x.compareTo(t.element);
if (compareTo>0){
// 要刪除的元素比當(dāng)前節(jié)點(diǎn)的元素的值大，往右走
return remove(x, t.right);
}else if (compareTo<0){
return remove(x,t.left); // 往左走
}else{
// 找到了要刪除的節(jié)點(diǎn)
System.out.println(t);
if (t.left!=null && t.right!=null){
System.out.println("該節(jié)點(diǎn)有兩個兒子節(jié)點(diǎn)");
t.element = findMin(t.right); // 用右側(cè)的最小數(shù)據(jù)代替當(dāng)前的數(shù)據(jù)
System.out.println("用右側(cè)最小數(shù)據(jù)代替當(dāng)前數(shù)據(jù)后的節(jié)點(diǎn)");
System.out.println(t);
// 還要把3節(jié)點(diǎn)刪除
t.right = remove(t.element, t.right);
}else {
System.out.println("該節(jié)點(diǎn)只有一個兒子節(jié)點(diǎn)");
// 如果該節(jié)點(diǎn)只有1個兒子
t = (t.left != null) ? t.left : t.right;
System.out.println("刪除原有節(jié)點(diǎn)后，該節(jié)點(diǎn)被兒子節(jié)點(diǎn)替換后");
System.out.println(t);
}
return t;
}
}
/**
* 中序遍歷
* @param root
*/
public void printTree(BinaryNode<T> root){
if (isEmpty()){
System.out.println("Empty tree");
}
else {
printTreeP(root);
}
}
/**
* 中序遍歷：左子樹 -> 根節(jié)點(diǎn) -> 右子樹
* @param node
*/
private void printTreeP(BinaryNode<T> node){
if (node!=null){
printTreeP(node.left);
System.out.print(node.element+" ");
printTreeP(node.right);
}
}
/**
* 后續(xù)遍歷：左子樹 -> 右子樹 -> 根節(jié)點(diǎn)
* @param t
* @return
*/
public int height(BinaryNode<T> t){
if (t==null){
return -1;
}else {
return 1+Math.max(height(t.left), height(t.right));
}
}
/**
* 先序遍歷：根節(jié)點(diǎn) -> 左子樹 -> 右子樹
* @param root
*/
public void preorderTraversal(BinaryNode<T> root) {
if (root == null) {
return;
}
System.out.print(root.element + " ");
preorderTraversal(root.left);
preorderTraversal(root.right);
}
}
測試代碼
package com.tianju.book.jpa.tree;
import javax.script.*;
public class TestTreeDemo {
public static void main(String[] args) throws ScriptException {
BinarySearchTree.BinaryNode<Integer> root = new BinarySearchTree.BinaryNode<>(1);
BinarySearchTree<Integer> tree = new BinarySearchTree<>(root);
BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>().getIntegerTree();
Integer element = binarySearchTree.root.left.element;
System.out.printf("根節(jié)點(diǎn) %d 的左側(cè)節(jié)點(diǎn)的元素為 %d ",binarySearchTree.root.element,element);
System.out.println();
String s = " 6\n" +
" / \\\n" +
" 2 8\n" +
" / \\\n" +
"1 4\n" +
" /\n" +
" 3";
System.out.println(s);
System.out.println("contains方法測試：");
boolean contains = binarySearchTree.contains(3, binarySearchTree.root);
System.out.println(contains);
System.out.println("查找最大值");
Integer max = binarySearchTree.findMax();
System.out.println(max);
System.out.println("從某個節(jié)點(diǎn)開始找最大值");
Integer max2 = binarySearchTree.findMax(binarySearchTree.root.left);
System.out.println(max2);
System.out.println("查找最小值");
Integer min = binarySearchTree.findMin(binarySearchTree.root);
System.out.println(min);
// System.out.println("插入新的元素");
// BinarySearchTree.BinaryNode<Integer> insert = binarySearchTree.insert(5, binarySearchTree.root);
// System.out.println(insert);
//
// System.out.println(binarySearchTree.scriptJ); // .left.right.right
// System.out.println(binarySearchTree.root.left.right);
//
// System.out.println("執(zhí)行插入：binarySearchTree."+binarySearchTree.scriptJ + "=insert");
//
// binarySearchTree.root.left.right.right = insert; // 根節(jié)點(diǎn)的左右為插入的新節(jié)點(diǎn)
//
// System.out.println(binarySearchTree.root.left.right.right);
// System.out.println("執(zhí)行插入后的節(jié)點(diǎn)4："+binarySearchTree.root.left.right);
//
//
// System.out.println("#######################################");
// ScriptEngineManager manager = new ScriptEngineManager();
// ScriptEngine engine = manager.getEngineByName("js");
// Bindings bindings = new SimpleBindings();
//
// bindings.put("binarySearchTree", binarySearchTree);
//
String script = "binarySearchTree.root.left.right.right=insert";
// String script = "binarySearchTree.root";
//
// Object result = engine.eval(script, bindings);
// System.out.println(result);
System.out.println("刪除節(jié)點(diǎn)");
BinarySearchTree.BinaryNode<Integer> remove = binarySearchTree.remove(4, binarySearchTree.root);
System.out.println(remove);
System.out.println("刪除有兩個兒子的節(jié)點(diǎn)");
BinarySearchTree<Integer> treeR = new BinarySearchTree<>().getIntegerTreeR();
treeR.remove(2, treeR.root);
}
}
樹的遍歷測試文章來源：http://www.zghlxwxcb.cn/news/detail-683017.html
package com.tianju.book.jpa.tree;
public class TestFindAll {
public static void main(String[] args) {
BinarySearchTree<Integer> balanceTree = new BinarySearchTree<Integer>().getBalanceTree();
System.out.println(" 7\n" +
" / \\\n" +
" 4 13\n" +
" / \\ / \\\n" +
" 2 6 11 15\n" +
" / \\ / / \\ / \\\n" +
" 1 3 5 9 12 14 16\n" +
" / \\\n" +
" 8 10");
System.out.println(balanceTree.root.left.right);
System.out.println("中序遍歷：按順序");
balanceTree.printTree(balanceTree.root);
System.out.println();
System.out.println("后序遍歷：計算節(jié)點(diǎn)的高度");
System.out.println(balanceTree.height(balanceTree.root.right));
System.out.println("先序遍歷");
balanceTree.preorderTraversal(balanceTree.root);
}
}
總結(jié)
1.樹的出現(xiàn)：解決鏈表線性訪問時間太慢，樹的時間復(fù)雜度O(logN)；
2.二叉樹的定義，最多兩個兒子節(jié)點(diǎn)；
3.二叉查找樹，左小，右大，中居中；remove方法，兩種，只有一個兒子節(jié)點(diǎn)，有兩個兒子節(jié)點(diǎn)；
4.AVL樹，在二叉查找樹基礎(chǔ)上加平衡條件，旋轉(zhuǎn)方法，單旋轉(zhuǎn)，雙旋轉(zhuǎn)；
5.樹的遍歷方式，中序遍歷，左根右；后續(xù)遍歷，左右根；先序遍歷，根左右；文章來源地址http://www.zghlxwxcb.cn/news/detail-683017.html
到了這里，關(guān)于Java學(xué)數(shù)據(jù)結(jié)構(gòu)（2）——樹Tree & 二叉樹binary tree & 二叉查找樹 & AVL樹 & 樹的遍歷的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
