java實現avl樹的重構,java 樹 數據結構

本文目錄一覽：

• 1、用C++來實現AVL樹的程序,要求建立,插入,刪除,單旋,雙旋,前序和後序遍歷
• 2、用Java實現一個樹形結構，並對其進行遍歷
• 3、如何用Java實現樹形結構啊？
• 4、java（樹的內容）演算法與數據結構

用C++來實現AVL樹的程序,要求建立,插入,刪除,單旋,雙旋,前序和後序遍歷

7.6 AVL樹

7.6.1 AVL樹的定義

高度平衡的二叉搜索樹

一棵AVL樹或者是空樹，或者是具有下列性質的二叉搜索樹：它的左子樹和右子樹都是AVL樹，且左子樹和右子樹的高度之差的絕對值不超過1。

高度不平衡的二叉搜索樹 高度平衡的二叉搜索樹

結點的平衡因子balance (balance factor)

1、每個結點附加一個數字，給出該結點右子樹的高度減去左子樹的高度所得的高度差。這個數字即為結點的平衡因子balance 。

2、根據AVL樹的定義，任一結點的平衡因子只能取 -1，0和 1。

3、如果一個結點的平衡因子的絕對值大於1，則這棵二叉搜索樹就失去了平衡，不再是AVL樹。

4、如果一棵二叉搜索樹是高度平衡的，它就成為 AVL樹。如果它有n個結點，其高度可保持在O(log2n)，平均搜索長度也可保持在O(log2n)。

AVL樹的類定義

template class Type class AVLTree {

public:

struct AVLNode {

Type data;

AVLNode *left, *right;

int balance;

AVLNode ( ) : left (NULL), right (NULL), balance (0) { }

AVLNode ( Type d, AVLNode *l = NULL, AVLNode *r = NULL )

: data (d), left (l), right (r), balance (0) { }

};

protected:

Type RefValue;

AVLNode *root;

int Insert ( AVLNode* tree, Type x, int taller );

void RotateLeft ( AVLNode *Tree, AVLNode* NewTree );

void RotateRight ( AVLNode *Tree, AVLNode* NewTree );

void LeftBalance ( AVLNode* Tree, int taller );

void RightBalance(AVLNode* Tree, int taller);

int Depth ( AVLNode *t ) const;

public:

AVLTree ( ) : root (NULL) { }

AVLNode ( Type Ref ) : RefValue (Ref), root (NULL) { }

int Insert ( Type x ) {

int taller;

return Insert ( root, x, taller );

}

friend istream operator ( istream in, AVLTreetype Tree );

friend ostream operator ( ostream out, const AVLTreetype Tree );

int Depth ( ) const;

}

7.6.2 平衡化旋轉

1、如果在一棵平衡的二叉搜索樹中插入一個新結點，造成了不平衡。

此時必須調整樹的結構，使之平衡化。

2、平衡化旋轉有兩類：

單旋轉 (左旋和右旋) 雙旋轉 (左平衡和右平衡)

3、每插入一個新結點時，AVL樹中相關結點的平衡狀態會發生改變。因此，在插入一個新結點後，需要從插入位置沿通向根的路徑回溯，檢查各結點的平衡因子(左、右子樹的高度差)。

4、如果在某一結點發現高度不平衡，停止回溯。

5、從發生不平衡的結點起，沿剛才回溯的路徑取直接下兩層的結點。

6、 如果這三個結點處於一條直線上，則採用單旋轉進行平衡化。單旋轉可按其方向分為左單旋轉和右單旋轉，其中一個是另一個的鏡像，其方向與不平衡的形狀相關。

7、如果這三個結點處於一條折線上，則採用雙旋轉進行平衡化。雙旋轉分為先左後右和先右後左兩類。

右單旋轉

左單旋轉

左右雙旋轉

右左雙旋轉

1、左單旋轉 (RotateLeft )

(1)如果在子樹E中插入一個新結點，該子樹高度增1導致結點A的平衡因子變成+2，出現不平衡。

(2)沿插入路徑檢查三個結點A、C和E。它們處於一條方向為「\」的直線上，需要做左單旋轉。

(3)以結點C為旋轉軸，讓結點A反時針旋轉。

左單旋轉的演算法

template class Type void AVLTreetype:: RotateLeft ( AVLNode *Tree, AVLNode* NewTree ) {

NewTree = Tree→right;

Tree→right = NewTree→left;

NewTree→left = Tree;

}

2、右單旋轉 (RotateRight )

(1)在左子樹D上插入新結點使其高度增1，導致結點A的平衡因子增到 -2，造成了不平衡。

(2) 為使樹恢復平衡，從A沿插入路徑連續取3個結點A、B和D，它們處於一條方向為「/」的直線上，需要做右單旋轉。

(3) 以結點B為旋轉軸，將結點A順時針旋轉。

右單旋轉的演算法

template class Type void AVLTreetype:: RotateRight( AVLNode *Tree, AVLNode* NewTree) {

NewTree = Tree→left;

Tree→left = NewTree→right;

NewTree→right = Tree;

}

3、先左後右雙旋轉 (RotationLeftRight)

(1)在子樹F或G中插入新結點，該子樹的高度增1。結點A的平衡因子變為 -2，發生了不平衡。

(2) 從結點A起沿插入路徑選取3個結點A、B和E，它們位於一條形如「?」的折線上，因此需要進行先左後右的雙旋轉。

(3)首先以結點E為旋轉軸，將結點B反時針旋轉，以E代替原來B的位置，做左單旋轉。

(4) 再以結點E為旋轉軸，將結點A順時針旋轉，做右單旋轉。使之平衡化。

左平衡化的演算法

template class Type void AVLTreetype:: LeftBalance ( AVLNode * Tree, int taller ) {

AVLNode *leftsub = Tree→left, *rightsub;

switch ( leftsub→balance ) {

case -1 :

Tree→balance = leftsub→balance = 0;

RotateRight ( Tree, Tree );

taller = 0;

break;

case 0 :

cout 「樹已經平衡化.\n”;

break;

case 1 :

rightsub = leftsub→right;

switch ( rightsub→balance ) {

case -1:

Tree→balance = 1;

leftsub→balance = 0;

break;

case 0 :

Tree→balance = leftsub→balance = 0;

break;

case 1 :

Tree→balance = 0;

leftsub→balance = -1;

break;

}

rightsub→balance = 0;

RotateLeft ( leftsub, Tree→left );

RotateRight ( Tree, Tree );

taller = 0;

}

}

4、先右後左雙旋轉 (RotationRightLeft)

(1)右左雙旋轉是左右雙旋轉的鏡像。

(2) 在子樹F或G中插入新結點，該子樹高度增1。結點A的平衡因子變為2，發生了不平衡。

(3) 從結點A起沿插入路徑選取3個結點A、C和D，它們位於一條形如「?」的折線上，需要進行先右後左的雙旋轉。

(4)首先做右單旋轉：以結點D為旋轉軸，將結點C順時針旋轉，以D代替原來C的位置。

(5) 再做左單旋轉：以結點D為旋轉軸，將結點A反時針旋轉，恢復樹的平衡。

右平衡化的演算法

template class Type void AVLTreetype:: RightBalance ( AVLNode * Tree, int taller ) {

AVLNode *rightsub = Tree→right, *leftsub;

switch ( rightsub→balance ) {

case 1 :

Tree→balance = rightsub→balance = 0;

RotateLeft ( Tree, Tree );

taller = 0;

break;

case 0 :

cout 「樹已經平衡化.\n”;

break;

case -1 :

leftsub = rightsub→left;

switch ( leftsub→balance ) {

case 1 :

Tree→balance = -1;

rightsub→balance = 0;

break;

case 0 :

Tree→balance = rightsub→balance = 0;

break;

case -1 :

Tree→balance = 0;

rightsub→balance = 1;

break;

}

leftsub→balance = 0;

RotateRight ( rightsub, Tree→left );

RotateLeft ( Tree, Tree );

taller = 0;

}

}

7.6.3 AVL樹的插入和刪除

AVL樹的插入:

1、在向一棵本來是高度平衡的AVL樹中插入一個新結點時，如果樹中某個結點的平衡因子的絕對值 |balance| 1，則出現了不平衡，需要做平衡化處理。

2、在AVL樹上定義了重載操作「」和「」，以及中序遍歷的演算法。利用這些操作可以執行AVL樹的建立和結點數據的輸出。

3、 演算法從一棵空樹開始，通過輸入一系列對象的關鍵碼，逐步建立AVL樹。在插入新結點時使用了前面所給的演算法進行平衡旋轉。

例，輸入關鍵碼序列為 { 16, 3, 7, 11, 9, 26, 18, 14, 15 }，插入和調整過程如下。

從空樹開始的建樹過程

1、下面的演算法將通過遞歸方式將新結點作為葉結點插入並逐層修改各結點的平衡因子。

2、 在發現不平衡時立即執行相應的平衡化旋轉操作，使得樹中各結點重新平衡化。

3、 在程序中，用變數success記載新結點是否存儲分配成功，並用它作為函數的返回值。

4、演算法從樹的根結點開始，遞歸向下找插入位置。在找到插入位置(空指針)後，為新結點動態分配存儲空間，將它作為葉結點插入，並置success為1，再將taller置為1，以表明插入成功。在退出遞歸沿插入路徑向上返回時做必要的調整。

template class Type int AVLTreetype:: Insert ( AVLNode* tree, Type x, int taller ) {

int success;

if ( tree == NULL ) {

tree = new AVLNode (x);

success = tree != NULL ? 1 : 0;

if ( success ) taller = 1;

}

else if ( x tree→data ) {

success = Insert ( tree→left, x, taller );

if ( taller )

switch ( tree→balance ) {

case -1 :

LeftBalance ( tree, taller );

break;

case 0 :

tree→balance = -1;

break;

case 1 :

tree→balance = 0;

taller = 0;

break;

}

}

else {

success = Insert ( tree→right, x, taller );

if ( taller )

switch ( tree→balance ) {

case -1 :

tree→balance = 0;

taller = 0;

break;

case 0 :

tree→balance = 1;

break;

case 1 :

RightBalance ( tree, taller );

break;

}

}

return success;

}

AVL樹的重載操作 、 和遍歷演算法的實現 :

template class Type istream operator ( istream in, AVLTreetype Tree ) {

Type item;

cout 「構造AVL樹 :\n”;

cout 「輸入數據(以” Tree.RefValue 「結束): “;

in item;

while ( item != Tree.RefValue ) {

Tree.Insert (item);

cout 「輸入數據(以” Tree.RefValue 「結束): “;

in item;

}

return in;

}

template class Type void AVLTree type

:: Traverse ( AVLNode *ptr, ostream out ) const { //AVL樹中序遍歷並輸出數據

if ( ptr != NULL ) {

Traverse ( ptr→left, out );

out ptr→data ‘ ‘;

Traverse ( ptr→right, out );

}

}

template class Type ostream operator ( ostream out, const AVLTreetype Tree ) {

out 「AVL樹的中序遍歷.\n”;

Tree.Traverse ( Tree.root, out );

out endl;

return out;

}

AVL樹的刪除

1、如果被刪結點x最多只有一個子女，那麼問題比較簡單。如果被刪結點x有兩個子女，首先搜索 x 在中序次序下的直接前驅 y (同樣可以找直接後繼)。再把 結點y 的內容傳送給結點x，現在問題轉移到刪除結點 y。 把結點y當作被刪結點x。

2、 將結點x從樹中刪去。因為結點x最多有一個子女，我們可以簡單地把x的雙親結點中原來指向x的指針改指到這個子女結點；如果結點x沒有子女，x雙親結點的相應指針置為NULL。然後將原來以結點x為根的子樹的高度減1，

3、必須沿x通向根的路徑反向追蹤高度的變化對路 徑上各個結點的影響。

4、 用一個布爾變數 shorter 來指明子樹的高度是否被縮短。在每個結點上要做的操作取決於 shorter 的值和結點的 balance，有時還要依賴子女的 balance 。

5、 布爾變數 shorter 的值初始化為True。然後對於從 x 的雙親到根的路徑上的各個結點 p，在 shorter 保持為 True 時執行下面的操作。如果 shorter 變成False，演算法終止。

6、case 1 : 當前結點p的balance為0。如果它的左子樹或右子樹被縮短，則它的 balance改為1或-1，同時 shorter 置為False。

7、case 2 : 結點p的balance不為0，且較高的子樹被縮短，則p的balance改為0，同時 shorter 置為True。

8、case 3 : 結點p的balance不為0，且較矮的子樹又被縮短，則在結點p發生不平衡。需要進行平衡化旋轉來恢復平衡。令p的較高的子樹的根為 q (該子樹未被縮短)，根據q的balance ，有如下3種平衡化操作。

9、case 3a : 如果q的balance為0，執行一個單旋轉來恢復結點p的平衡，置shorter為False。

10、 case 3b : 如果q的balance與p的balance相同，則執行一個單旋轉來恢復平衡，結點p和q的balance均改為0，同時置shorter為True。

11、case 3c : 如果p與q的balance相反，則執行一個雙旋轉來恢復平衡，先圍繞 q 轉再圍繞 p 轉。新的根結點的balance置為0，其它結點的balance相應處理，同時置shorter為True。

12、 在case 3a, 3b和3c的情形中，旋轉的方向取決於是結點p的哪一棵子樹被縮短。

7.6.4 AVL樹的高度

1、設在新結點插入前AVL樹的高度為h，結點個數為n，則插入一個新結點的時間是O(h)。對於AVL樹來說，h多大？

2、設 Nh 是高度為 h 的AVL樹的最小結點數。根的一棵子樹的高度為 h-1，另一棵子樹的高度為 h-2，這兩棵子樹也是高度平衡的。因此有 N-1 = 0 (空樹) N0 = 1 (僅有根結點) Nh = Nh-1 + Nh-2 +1 , h 0

3、可以證明，對於 h ? 0，有 Nh = Fh+3 -1 成立。

4、有n個結點的AVL樹的高度不超過

5、在AVL樹刪除一個結點並做平衡化旋轉所需時間為 O(log2n)。

6、 二叉搜索樹適合於組織在內存中的較小的索引(或目錄)。對於存放在外存中的較大的文件系統，用二叉搜索樹來組織索引不太合適。

7、 在文件檢索系統中大量使用的是用B_樹或B+樹做文件索引。

用Java實現一個樹形結構，並對其進行遍歷

import java.util.Iterator;

import java.util.Random;

import java.util.TreeSet;

public class Demo{

    public static void main(String[] args) throws Exception {

        TreeSetInteger ts = new TreeSetInteger();

        for(int i = 0; i  10; i++){

            ts.add(new Random().nextInt(999));

        }

        for(IteratorInteger it = ts.iterator(); it.hasNext();){

            System.out.println(it.next());

        }

    }

}

//上面是利用TreeSet進行簡單的二叉樹實現，另有遍歷，當然遍歷是自然順序。

//如有需要請自行修改吧。

如何用Java實現樹形結構啊？

package tree;

import java.util.LinkedList;

import java.util.List;

/**

* 功能：把一個數組的值存入二叉樹中，然後進行3種方式的遍歷

*

* 參考資料0:數據結構(C語言版)嚴蔚敏

*

* 參考資料1：

*

* 參考資料2：

*

* @author ocaicai@yeah.net @date: 2011-5-17

*

*/

public class BinTreeTraverse2 {

private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

private static ListNode nodeList = null;

/**

* 內部類：節點

*

* @author ocaicai@yeah.net @date: 2011-5-17

*

*/

private static class Node {

Node leftChild;

Node rightChild;

int data;

Node(int newData) {

leftChild = null;

rightChild = null;

data = newData;

}

}

public void createBinTree() {

nodeList = new LinkedListNode();

// 將一個數組的值依次轉換為Node節點

for (int nodeIndex = 0; nodeIndex array.length; nodeIndex++) {

nodeList.add(new Node(array[nodeIndex]));

}

// 對前lastParentIndex-1個父節點按照父節點與孩子節點的數字關係建立二叉樹

for (int parentIndex = 0; parentIndex array.length / 2 – 1; parentIndex++) {

// 左孩子

nodeList.get(parentIndex).leftChild = nodeList

.get(parentIndex * 2 + 1);

// 右孩子

nodeList.get(parentIndex).rightChild = nodeList

.get(parentIndex * 2 + 2);

}

// 最後一個父節點:因為最後一個父節點可能沒有右孩子，所以單獨拿出來處理

int lastParentIndex = array.length / 2 – 1;

// 左孩子

nodeList.get(lastParentIndex).leftChild = nodeList

.get(lastParentIndex * 2 + 1);

// 右孩子,如果數組的長度為奇數才建立右孩子

if (array.length % 2 == 1) {

nodeList.get(lastParentIndex).rightChild = nodeList

.get(lastParentIndex * 2 + 2);

}

}

/**

* 先序遍歷

*

* 這三種不同的遍歷結構都是一樣的，只是先後順序不一樣而已

*

* @param node

* 遍歷的節點

*/

public static void preOrderTraverse(Node node) {

if (node == null)

return;

System.out.print(node.data + ” “);

preOrderTraverse(node.leftChild);

preOrderTraverse(node.rightChild);

}

/**

* 中序遍歷

*

* 這三種不同的遍歷結構都是一樣的，只是先後順序不一樣而已

*

* @param node

* 遍歷的節點

*/

public static void inOrderTraverse(Node node) {

if (node == null)

return;

inOrderTraverse(node.leftChild);

System.out.print(node.data + ” “);

inOrderTraverse(node.rightChild);

}

/**

* 後序遍歷

*

* 這三種不同的遍歷結構都是一樣的，只是先後順序不一樣而已

*

* @param node

* 遍歷的節點

*/

public static void postOrderTraverse(Node node) {

if (node == null)

return;

postOrderTraverse(node.leftChild);

postOrderTraverse(node.rightChild);

System.out.print(node.data + ” “);

}

public static void main(String[] args) {

BinTreeTraverse2 binTree = new BinTreeTraverse2();

binTree.createBinTree();

// nodeList中第0個索引處的值即為根節點

Node root = nodeList.get(0);

System.out.println(“先序遍歷：”);

preOrderTraverse(root);

System.out.println();

System.out.println(“中序遍歷：”);

inOrderTraverse(root);

System.out.println();

System.out.println(“後序遍歷：”);

postOrderTraverse(root);

}

}

java（樹的內容）演算法與數據結構

其實有兩種方式：

第一種就是遞歸 就像現在比較老的樹形菜單。這種方式應該string類型應該是存不了的。就是自定義一個類型A 裡面有一個成員變數 listA。 這種結構就是list裡面嵌套list，你有多少級就有多少層。

第二種其實要做處理，就是把原數據按一定規則排序放到一個list裡面，這裡面不會再嵌套list。list排完序就如你的效果圖一樣。第一個 一級節點 》》其子節點；然後第二個一級節點》》其子節點，etc。 但是這種結構要有存的時候要循環一遍排成上述的順序，取的時候還需要判斷哪個是下一個不同級節點的開始。

js前台展示比較簡單，根據父id直接添加就行了，原數據什麼都不用做。但是java里這種方式不行。