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里这种方式不行。