平衡树java代码 平衡二叉树代码java

平衡二叉树

平衡二叉树的定义:

10年积累的网站设计制作、成都网站制作经验，可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你，你也不认识我。但先网站设计后付款的网站建设流程，更有保亭黎族免费网站建设让你可以放心的选择与我们合作。

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是二叉搜索树，反之则不一定.

问题1:

把一个升序的数组转换成平衡二叉树

对一个二叉搜索树进行中序遍历就可以得到一个升序的数组,那么反过来考虑,数组的中值即为root,然后数组分为左子树和右子树,继续进行递归即可得出结果.

问题2:

给一个二叉树,判断是否是平衡树

首先写计算二叉树高度的函数

树的高度 = max(左子树高度，右子树高度)+1

可以得到高度后对树递归求解每个节点的左右子树的高度差，如果有大于1的，则return False

java二叉树的顺序表实现

做了很多年的程序员，觉得什么树的设计并不是非常实用。二叉树有顺序存储，当一个insert大量同时顺序自增插入的时候，树就会失去平衡。树的一方为了不让塌陷，会增大树的高度。性能会非常不好。以上是题外话。分析需求在写代码。

import java.util.List;

import java.util.LinkedList;

public class Bintrees {

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

private static ListNode nodeList = null;

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]));

}

// 对除最后一个父节点按照父节点和孩子节点的数字关系建立二叉树

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);

}

}

// 前序遍历

public static void preOrderTraverse(Node node) {

if (node == null) {

return;

}

System.out.print(node.data + " ");

preOrderTraverse(node.leftChild);

preOrderTraverse(node.rightChild);

}

// 中序遍历

public static void inOrderTraverse(Node node) {

if (node == null) {

return;

}

inOrderTraverse(node.leftChild);

System.out.print(node.data + " ");

inOrderTraverse(node.rightChild);

}

// 后序遍历

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) {

Bintrees binTree = new Bintrees();

binTree.createBintree();

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怎么实现平衡树动态演示

public class treenode1 {         //二叉树的结点类

public string data;          //数据元数

public treenode1 left,right; //指向左,右孩子结点的链

public treenode1(){

this("?");

}

public treenode1(string d){  //构造有值结点

data = d;

left = right = null;

}

public void preorder(treenode1 p){   //先根次序遍历二叉树

if(p!=null){ 

system.out.print(p.data+" "); 

preorder(p.left); 

preorder(p.right);

}

}

public void inorder(treenode1 p){    //中根次序遍历二叉树

if(p!=null){ inorder(p.left); 

system.out.print(p.data+" "); 

inorder(p.right);

}

}

public void postorder(treenode1 p){   //后根次序遍历二叉树

if(p!=null){ postorder(p.left); 

postorder(p.right); 

system.out.print(p.data+" ");

}

}

}

[数据结构4.8]平衡二叉树

平衡二叉树（AVL），任意结点的平衡因子的绝对值不超过一（左子树高度-右子树高度）。

高度为h的最小平衡二叉树的结点数 。

利用递归的后序遍历过程：

1、判断左子树是一个平衡二叉树

2、判断右子树是一个平衡二叉树

3、判断以该结点为根的二叉树为平衡二叉树

判断条件：若左子树和右子树均为平衡二叉树，且左子树与右子树高度差的绝对值小于等于1，则平衡。

先插入，正调整，每次调整最小不平衡子树

LL平衡旋转（右单旋转）

原因：在结点A的左孩子的左子树上插入了新结点。

调整方法：右旋操作，将A的左孩子B代替A，将A结点称为B的右子树根结点，而B的原右子树则作为A的左子树。

RR平衡旋转（左单旋转）

原因：在结点A的右孩子的右子树上插入了新结点。

调整方法：左旋操作，将A的右孩子B代替A，将A结点称为B的左子树根结点，而B的原右左树则作为A的右子树。

LR平衡旋转（先左后右双旋转）

原因：在结点A的左孩子的右子树上插入了新结点。

调整方法：先左旋后右旋操作，将A的左孩子B的右孩子结点C代替B，然后再将C结点向上代替A的位置。

RL平衡旋转（先右后左双旋转）

原因：在结点A的右孩子的左子树上插入了新结点。

调整方法：先右旋后左旋操作，将A的右孩子B的左孩子结点C代替B，然后再将C结点向上代替A的位置。