189 8069 5689
平衡二叉树的定义:
10年积累的网站设计制作、成都网站制作经验，可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你，你也不认识我。但先网站设计后付款的网站建设流程，更有保亭黎族免费网站建设让你可以放心的选择与我们合作。
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是二叉搜索树，反之则不一定.
问题1:
把一个升序的数组转换成平衡二叉树
对一个二叉搜索树进行中序遍历就可以得到一个升序的数组,那么反过来考虑,数组的中值即为root,然后数组分为左子树和右子树,继续进行递归即可得出结果.
问题2:
给一个二叉树,判断是否是平衡树
首先写计算二叉树高度的函数
树的高度 = max(左子树高度，右子树高度)+1
可以得到高度后对树递归求解每个节点的左右子树的高度差，如果有大于1的，则return False
做了很多年的程序员，觉得什么树的设计并不是非常实用。二叉树有顺序存储，当一个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);
}
}
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+" ");
}
}
}
平衡二叉树（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的位置。