近期在学习数据结构上关于平衡二叉树的知识，看了严老师的思路，感觉用java写出递归的构建方式有点困难，由于当中的递归须要把引用传进去，所以感觉是要实现起来比較麻烦，所以就首先想到使用非递归的方式来实现构建平衡二叉树。

       使用非递归的方式，思路也非常easy，就是为每个结点都要定义一个平衡因子的属性，当成功向树中插入一个数据时，我就要进行回溯，看看有没有平衡因子的绝对值等于2的结点，假设有，那就须要进行旋转。当时的思路仅限于这些，接触java没有多久，目測假设实现起来，有点困难。

      所以，上网查询了一个博客写的代码，虽然不知道原作者是谁，只是还是贴上我參考的博客地址：http://blog.csdn.net/zxman660/article/details/7940190

      当中，我觉得另一个难题就是，我定义的结点使用了泛型，即结点的value也是使用的泛型<E>,所以在比較大小的时候，我就无从下手，可能是我接触java不太久的原因，当我參考上述博客的思路后，竟然是这样实现的。

void compare(E element, Node node){ 	Comparable<? super E> e = (Comparable<? super E>)element; 	int cmp = e.compareTo(node.element); 	if(cmp > 0) //大于 	else if(cmp == 0) //等于 	else //小于}

     通过此次学习，尽管接触了平衡二叉树的构建，但还是感觉学到了不少的知识，而且对java的使用又有了很多其它的认识。

     有了上述的感悟，感觉还是写一个博客来收藏一下，等自己有时间，再补充一下结点删除的代码。

      可能本人代码在凝视上提供的思路有限，假设有看不懂的地方，能够參考上面的博客地址的内容。

package util;/**  * 平衡二叉树  * 定义:首先它是一种特殊的二叉排序树，其次它的左子树和右子树都是平衡二叉树，  * 且左子树和右子树的深度之差不超过1  * 平衡因子:能够定义为左子树的深度减去右子树的深度  *   * 平衡二叉树是对二叉排序树的优化，防止二叉排序树在最坏情况下平均查找时间为n，  * 二叉排序树在此时形如一个单链表  * 平衡二叉树查找元素的次数不超过树的深度，时间复杂度为logN  */ public class AVLTree<E> {		/**根节点*/	private Node<E> root = null;		/**树中元素的个数*/	private int size = 0;			private static final int LEFT_HIGH = 1;	private static final int RIGHT_HIGH = -1;	private static final int EQUAL_HIGH = 0;		public AVLTree(){}				public boolean insertElement(E element){				Node<E> t = root;		if(t == null){			/**将值复制给根节点，其父节点为空*/			root = new Node(element, null);			size = 1;			return true;		}				int cmp = 0;		Node<E> parent; /**用来保存t的父节点*/				/**查找结点应存放的位置*/		Comparable<? super E> e = (Comparable<? super E>)element;		do{			parent = t;			cmp = e.compareTo(t.element);			if(cmp < 0){				t = t.left;			}else if(cmp > 0){				t = t.right;			}else{				return false;			}		}while(t != null);				/**将结点存放在对应的位置*/		Node<E> child = new Node(element, parent);		if(cmp < 0){			parent.left = child;		}else{			parent.right = child;		}						/**開始回溯，为根节点改动balabce，以便进行对应的调整*/		while(parent != null){			cmp = e.compareTo(parent.element);			if(cmp < 0){				parent.balance ++;			}else{				parent.balance --;			}						if(parent.balance == 0){/**从这以上的结点都不须要改动了，也不须要旋转了*/				break;			}						if(Math.abs(parent.balance) == 2){				fixAfterInsertion(parent);				break;			}			parent = parent.parent;		}		size ++;		return true;	}					private void fixAfterInsertion(Node<E> p) {		if(p.balance == 2){			leftBanance(p);		}		if(p.balance == -2){			rightBalance(p);		}	}		/**	 * 左平衡操作，即结点t的不平衡是由于左子树过深	 * 	 * 1、假设新的结点插入到p的左孩子的左子树中，则直接进行右旋操作就可以	 * 				t								lc	 * 			   /  \		右旋操作				   /  	 * 			  lc   rc		------------->		 lcl   t	 * 			 /  \								 /	  /  	 * 			lcl  lcr						   lcll  lcr rc 	 * 			/	 *         lcll	 *         	 * 2、假设新的结点插入到p的左孩子的右子树中，则须要进行分情况讨论	 * 	 * 	情况a：当p的左孩子的右子树根节点的balance = RIGHT_HIGH	 * 	 * 			1						1						 	4	 * 		   /  \					   /  \						   /  	 *        2    6      左旋     	4    6                 右旋		2    1	 *       /  \  		------->     /  \        -------->       /    /  	 *      3    4                  2    5                      3    5    6	 *            \                /	 *             5			  3	 * 	 * 	 * 	情况b：当p的左孩子的右子树根节点的balance = LEFT_HIGH	 * 	 * 			1						1						 	4	 * 		   /  \					   /  \						   /  	 *        2    6      左旋     	4    6          右旋		2    1	 *       /  \  		------->     /          -------->        / \    	 *      3    4                  2                           3   5    6	 *          /                  / 	 *         5   			  	  3   5	 * 	 * 	情况c：当p的左孩子的右子树根节点的balance = EQUAL_HIGH	 * 	 * 			1						1						 	4	 * 		   /  \					   /  \						   /  	 *        2    7      左旋     	 4    7          右旋		2     1	 *       /  \  		------->     / \         -------->       / \   / 	 *      3    4                  2   6                       3   5  6  7	 *          / \                / 	 *         5   6			  3	  5	 * */	private void leftBanance(Node<E> t) {				Node<E> lc = t.left;		switch(lc.balance){		case LEFT_HIGH:		/**新结点插入到t的左孩子的左子树上，须要单右旋处理*/			lc.balance = EQUAL_HIGH;			t.balance = EQUAL_HIGH;			break;					case RIGHT_HIGH:	/**新结点插入到t的左孩子的右子树上，须要双旋处理*/			Node<E> rd = lc.right;			switch(rd.balance){			case LEFT_HIGH:				lc.balance = EQUAL_HIGH;				t.balance = RIGHT_HIGH;				break;							case RIGHT_HIGH:						lc.balance = LEFT_HIGH;				t.balance = EQUAL_HIGH;				break;			case EQUAL_HIGH:				t.balance = EQUAL_HIGH;				lc.balance = EQUAL_HIGH;				break;			}			rd.balance = EQUAL_HIGH;			/**对t的左子树进行左旋处理*/			left_Rotate(t.left);			/**对t进行右旋处理*/			right_Rotate(t);			break;		}	}	/**	 * 右平衡操作，即结点t的不平衡是由于右子树过深	 * 	 * 1、假设新的结点插入到p的右孩子的右子树中，则直接进行左旋操作就可以	 * 	 * 			p											r	 * 		  /   \										   /  	 * 		 l	   r			   左旋操作 				  p   rr	 * 			 /   \			----------->             / \    	 * 			rl    rr								l   rl   rrr	 * 				   	 * 					rrr	 * 	 * 	 * 2、假设新的结点插入到p的右孩子的左子树中，则须要进行分情况讨论	 * 	 * 	情况a：当p的右孩子的左子树根节点的balance = LEFT_HIGH	 * 	 *			1						1							4	 *		   /  \					   /  \						   /   	 *		  2    3		  右旋	  2	   4		左旋		  1     3	 *			  /  \	   ------->		  /  \		------->	 /  \     	 * 			 4	  5					 6    3					2	6  	   5		 * 			/							   	 * 		   6								5	 * 	 * 情况b：当p的右孩子的左子树根节点的balance = RIGHT_HIGH	 * 	 *			1						1							4	 *		   /  \					   /  \						   /   	 *		  2    3		  右旋	  2	   4			左旋		  1     3	 *			  /  \	   ------->		     \		------->	 /     /  	 * 			 4	  5					      3					2	  6	   5		 * 			  \							 /  	 * 		   	   6						6    5	 * 	 * 	 * 情况C：当p的右孩子的左子树根节点的balance = EQUAL_HIGH	 *			1						1							4	 *		   /  \					   /  \						   /   	 *		  2    3		  右旋	  2	   4 		左旋		  1     3	 *			  /  \	   ------->		  /  \		------->	 / \    / 	 * 			 4	  5					 6    3					2	6  7   5		 * 			/ \							 /  	 * 		   6   7						7    5	 * */	private void rightBalance(Node<E> p) {		Node<E> rc = p.right;		switch(rc.balance){		case RIGHT_HIGH:		/**新结点插入到t的右孩子的右子树上，须要单左旋处理*/			rc.balance = EQUAL_HIGH;			p.balance = EQUAL_HIGH;			break;					case LEFT_HIGH:		/**新结点插入到t的右孩子的左子树上，须要双旋处理*/			Node<E> ld = rc.left;			switch(ld.balance){			case LEFT_HIGH:				p.balance = EQUAL_HIGH;				rc.balance = RIGHT_HIGH;				break;			case RIGHT_HIGH:				p.balance = LEFT_HIGH;				rc.balance = EQUAL_HIGH;				break;			case EQUAL_HIGH:				p.balance = EQUAL_HIGH;				rc.balance = EQUAL_HIGH;				break;			}			ld.balance = EQUAL_HIGH;			/**对p的右子树进行右旋处理*/			right_Rotate(p.right);			/**对p进行左旋处理*/			left_Rotate(p);			break;		}			}	/**	 * 左旋操作	 * 			p											r	 * 		  /   \										   /  	 * 		 l	   r			   左旋操作 				  p   rr	 * 			 /   \			----------->             / \    	 * 			rl    rr								l   rl   rrr	 * 				   	 * 					rrr	 * */	private void left_Rotate(Node<E> p) {		if(p != null){			Node<E> r = p.right;	/**获得p的右子树的根节点r*/						p.right = r.left;		/**将r的左子树转接到p的右子树上*/			if(r.left != null){		/**假设r的左子树不为空，将左子树的父节点设置为p*/				r.left.parent = p;			}						r.parent = p.parent;	/**改动r的父节点，改动为p的父节点*/			if(p.parent == null){	/**假设p的父节点为null，那么如今r就是根节点了*/				root = r;			}else if(p == p.parent.left){/**假设p为其父节点的左孩子，将其父节点的左孩子指向r*/				p.parent.left = r;			}else if(p == p.parent.right){/**假设p为其父节点的右孩子，将其父节点的右孩子指向r*/				p.parent.right = r;			}						r.left = p;		/**将r的左孩子设置为p*/			p.parent = r;	/**将p的父节点设置为r*/		}	}	/**	 * 右旋操作	 * 	 * 				p									l	 * 			   /  \			 右旋操作				   /  	 * 			  l	   r		------------->		  ll   p	 * 			 /  \								 /	  /  	 * 			ll   lr								lll	 lr   r	 * 			/	 *         lll	 * */	private void right_Rotate(Node<E> p) {				if(p != null){			Node<E> l = p.left;		/**获取p的左孩子l*/						p.left = l.right;		/**将l的右子树变为p的左子树*/			if(l.right != null){	/**假设l的右子树不为空，将其父节点设置为p*/				l.right.parent = p;			}						l.parent = p.parent;	/**将r的父节点改动为p的父节点*/			if(p.parent == null){	/**假设p的父节点为null，即l为root*/				root = l;			}else if(p == p.parent.left){	/**假设p为其父节点的左孩子，将p的父节点的左孩子指向l*/				p.parent.left = l;			}else if(p == p.parent.right){ /**假设p为其父节点的右孩子，将p的父节点的右孩子指向l*/				p.parent.right = l;			}						l.right = p;		/**将l的右子树变为p*/			p.parent = l;		/**改动p的父节点为l*/		}	}		/**中序非递归方式遍历平衡二叉树*/	public void nrInOrderTraverse(){		Stack<Node<E>> stack = new Stack<Node<E>>();		Node<E> p = root;		while(p != null || !stack.isEmpty()){			while(p != null){				stack.push(p);				p = p.left;			}			p = stack.pop();			System.out.println(p.element);			p = p.right;		}	}		/**平衡二叉树的结点定义*/	class Node<E>{		E element;		/**结点的平衡因子*/		int balance = 0;			/**左孩子结点、右孩子结点、父节点*/		Node<E> left;		Node<E> right;		Node<E> parent;				public Node(){}		public Node(E element, Node<E> parent){			this.element = element;			this.parent = parent;		}				public String toString(){			return element + " BF=" + balance;		}			}		public static void main(String[] args) {		Integer[] num = {5,8,2,0,1, -2, -9, 100};		AVLTree<Integer> avl = new AVLTree<Integer>();		for(int i = 0; i < num.length; i++){			avl.insertElement(num[i]);		}		avl.nrInOrderTraverse();	}}