经典题集之树四

1. 将数组转换为二叉搜索树
2. 平衡树，注意旋转是从失衡的哪个元素开始，不是插入的节点，同时LR，RL旋转是相反的，例如：LR旋转是先R旋转再L旋转。
3. 向树的左侧子节点的左子树中插入元素,采用LL旋转
4. 向树的右侧子节点的右子树中插入元素，采用RR旋转
5. 向x的左侧节点的右子树中插入元素，采用LR旋转
6. 向x的右侧子节点的左子树中插入元素，采用RL旋转
7. 判断二叉搜索树是不是AVL

	public Node BuildBinaryTreeFromArray(int [] a,int left,int right) {
		Node temp = new Node();
		int mid;
		if(left > right) return null;
		if(left == right) {
			temp.data = a[left];
			temp.leftchild = temp.rightchild = null;
		}else {
			mid = left+(right-left)/2;
			temp.data = a[mid];
			temp.leftchild = BuildBinaryTreeFromArray(a, left, mid);
			temp.rightchild = BuildBinaryTreeFromArray(a, mid+1, right);
		}
		return temp;
	}
	//2.平衡树，注意旋转是从失衡的哪个元素开始，不是插入的节点，同时LR，RL旋转是相反的，例如：LR旋转是先R旋转再L旋转。
	//向树的左侧子节点的左子树中插入元素,采用LL旋转
	public Node RotateLeft(Node x) {
		Node w = x.leftchild;
		x.leftchild = w.rightchild;
		w.rightchild  = x;
		x.height = Integer.max(Height(x.leftchild), Height(x.rightchild)) + 1;
		w.height = Integer.max(Height(w.leftchild), x.height) + 1;
		return w;
	}
	//向树的右侧子节点的右子树中插入元素，采用RR旋转
	public Node RotateRight(Node x) {
		Node w = x.rightchild;
		x.rightchild = w.leftchild;
		w.leftchild = x;
		w.height = Integer.max(Height(w.rightchild),Height(w.leftchild)) + 1;
		x.height = Integer.max(x.rightchild, w.height) + 1;
		return w;
	}
	//双旋转
	//向x的左侧节点的右子树中插入元素，采用LR旋转
	public Node RotateLeftRight(Node x) {
		x.leftchild = RotateRight(x.leftchild);
		return RotateLeft(x);
	}
	//向x的右侧子节点的左子树中插入元素，采用RL旋转
	public Node RotateRightLeft(Node x) {
		x.rightchild = RotateLeft(x.rightchild);
		return RotateRight(x);
	}
	//3.判断二叉搜索树是不是AVL
	public int IsAVL(Node root) {
		int left,right;
		if(root == null) return 0;
		left = IsAVL(root.leftchild);
		if(left == -1)
			return left;
		right = IsAVL(root.rightchild);
		if(right == -1)
			return right;
		if(Math.abs(left - right) > 1 )
			return -1;
		return Integer.max(left, right) + 1;
	}