二叉树的性质以及二叉树的遍历（非递归）（c语言）(一)

BST具有以下三个性质:

1.如果它的左子树不为空，则左子树上的所有节点的值均小于它的根节点的值。

2.如果它的右子树不为空，则右子树上的所有结点的值均大于它的根节点的值。

3.它的左右子树也分别为二叉排序树。

下图为BST

BST的查找操作，比如查找元素9 .首先与根节点12比较，因为9<12 继续与12的左子树的根节点8比较，因为9>8所以与8的右子树比较 8=8 查找成功。

BST的插入操作，插入时首先也是一个查找的过程，新插入的结点一定是新添加的叶子结点，并且查找不成功时返回路径上最后一个结点的左孩子或者右孩子结点。

比如插入元素7 ，首先是一个查找过程 ，查找到值为6的结点时 因为7>6所以查找6的右子树，以为值为6的结点的右子树为空。所以查找完毕。返回最后访问的值为6的结点的右子树（此时为空），接着将值为7的结点插入。

BST的删除操作：假设被删除的结点为小p。其中p的双亲结点为大P。

下面分三种情况来讨论删除操作：

1.如果p为叶子结点 如上图中的7,9,14.则直接删除即可。

2.如果p为P的左(右)子树，且p只有左子树或者右子树。直接让p的左子树或者右子树直接成为P的左（右）子树即可。

3.如果p的左右子树均不为空，以元素为8的结点为例。令p的直接前驱或者直接后继代替p然后在从二叉树中删除它的直接前驱或者直接后继。（中序遍历为6,7,8,9,12,,13,14,15 .其中8的直接前驱为7 8的直接后继为9）.

java代码实现BST的插入与删除操作

class Tree{ 	private String element; 	private Tree left; 	private Tree right; 	public Tree(Tree left,Tree right,String element) { 		this.left=left; 		this.right=right; 		this.element=element; 		 	} 	//set get } /** 	 * 二叉排序树的插入操作 	 * @param tree 	 * @return 	 */ 	public static boolean InsertBST(Tree root,Tree newNode) { 		Tree parent=null; 		while(true) { 			if (root==null) break; 			parent=root; 			if (newNode.getElement().compareTo(root.getElement())<0) { 				root=root.getLeft(); 			}else if(newNode.getElement().compareTo(root.getElement())>0){ 				root=root.getRight(); 			}else { 				return false; 			} 		} 		if (parent!=null) { 			if (newNode.getElement().compareTo(parent.getElement())<0) { 				parent.setLeft(newNode); 			}else { 				parent.setRight(newNode); 			} 		} 		return false; 	}  /*** 	 * 删除一个结点 	 * @param root 树的根节点 	 * @param element 要删除的元素的值 	 * @return 删除后的树 	 */ 	public static Tree DeleteBST(Tree root,String element) { 		Tree ROOT=root; 		Tree parent=null; 		while(true) { 			if (root==null) break; 			if (element.compareTo(root.getElement())<0) { 				parent=root; 				root=root.getLeft(); 			}else if (element.compareTo(root.getElement())>0) { 				parent=root; 				root=root.getRight(); 			}else { 				break; 			} 		} 		if (root!=null&&parent!=null) { 			if (root.getLeft()==null&&root.getRight()==null) { 				if (parent.getLeft()==root) { 					parent.setLeft(null); 					return ROOT; 				}else { 					parent.setRight(null); 					return ROOT; 				} 			} 			 			if (root.getLeft()==null&&root.getRight()!=null){ 				if (parent.getLeft()==root) { 					parent.setLeft(root.getRight()); 					return ROOT; 				}else { 					parent.setRight(root.getRight()); 					return ROOT; 				} 			}else	if (root.getLeft()!=null&&root.getRight()==null) { 				if (parent.getLeft()==root) { 					parent.setLeft(root.getLeft()); 					return ROOT; 				}else { 					parent.setRight(root.getLeft()); 					return ROOT; 				} 			} 			//当左孩子右孩子都存在时 			if (root.getLeft()!=null && root.getRight()!=null){ 				Tree deleteNode=root; 				Tree partentNode=root; 				root=root.getLeft(); 				while(root.getRight()!=null) { 					partentNode=root; 					root=root.getRight(); 				} 				if (root.getLeft()!=null) { 					partentNode.setRight(root.getLeft()); 				} 				root.setLeft(deleteNode.getLeft()); 				root.setRight(deleteNode.getRight()); 				if (parent.getLeft()==deleteNode) { 					parent.setLeft(root); 				}else { 					parent.setRight(root); 				} 			} 		}else if(root!=null&&parent==null){ 			if (root.getLeft()!=null&&root.getRight()!=null) { 				root=root.getLeft(); 				Tree partentNode=null; 				while(root.getRight()!=null) { 					partentNode=root; 					root=root.getRight(); 				} 				if (root.getLeft()!=null) { 					partentNode.setRight(root.getLeft()); 				} 				if (ROOT.getLeft()!=null&&ROOT.getLeft()!=root) { 					root.setLeft(ROOT.getLeft()); 				} 				root.setRight(ROOT.getRight()); 				ROOT=root; 				return ROOT; 			}else if (root.getLeft()!=null&&root.getRight()==null) { 				ROOT=root.getLeft(); 			}else { 				ROOT=root.getRight(); 			} 			return ROOT; 		} 		return null; 	} 

由BST的概念可知二叉树的中序遍历一定是有序的，中序遍历的java实现如下:

	/**** 	 * 中序遍历的递归操作 	 * @param tree 	 */ 	public static void  InOrderTraverse_3(Tree tree) { 		if (tree.getLeft()!=null) { 			InOrderTraverse_3(tree.getLeft()); 		} 		PrintTree(tree); 		if (tree.getRight()!=null) { 			InOrderTraverse_3(tree.getRight()); 		} 	} 	/** 	 * 中序遍历二叉树的非递归算法 	 * @param tree 	 */ 	public static void  InOrderTraverse(Tree tree) { 		Stack<Tree> stack=getStack(); 		stack.push(tree); 		while(!stack.isEmpty()) { 			while(stack.peek()!=null&&tree!=null) stack.push(tree=tree.getLeft()); 			stack.pop(); 			if (!stack.isEmpty()) { 				tree=stack.pop(); 				PrintTree(tree); 				stack.push(tree=tree.getRight()); 			} 		} 	} 	/** 	 * 中序遍历二叉树的非递归算法 	 * @param tree 	 */ 	public static void InOrderTraverse_1(Tree tree) { 		Stack<Tree> stack=getStack(); 		Tree t=tree; 		while(t!=null||!stack.isEmpty()){ 			if (t!=null) { 				stack.push(t); 				t=t.getLeft(); 			}else { 				t=stack.pop(); 				PrintTree(t); 				t=t.getRight(); 			} 		} 	}

二叉查找树查找关键字等于给定值结点的过程，恰巧是走了一条从根节点到该节点的过程。其中比较的次数为该节点的层次数。可见，层次数越少，查找的效率越高。假设由两组数字相同，但顺序不同的数字构成二叉树（45，24，53，12，37，93）（12，24，37，45，53，93）。

如图，同样查找数字93，第一个只需要比较3次，而第二棵树需要比较6次。因为（b）树已经发生了倾斜，为了解决这个问题可以使用平衡二叉树(有AVL树和红黑树，本文只介绍AVL树)。

AVL树有以下性质：

它的的左子树或者右子树都是平衡二叉树，并且左子树和右子树的深度的差值不超过1.

AVL树的插入。

假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针为a（即a是离插入点最近，且平衡因子绝对值超过1的祖先结点），则失去平衡后进行进行的规律可归纳为下列四种情况：

单向右旋平衡处理LL：由于在*a的左子树根结点的左子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行一次右旋转操作；

单向左旋平衡处理RR：由于在*a的右子树根结点的右子树上插入结点，*a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行一次左旋转操作；

双向旋转（先左后右）平衡处理LR：由于在*a的左子树根结点的右子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行两次旋转（先左旋后右旋）操作。

双向旋转（先右后左）平衡处理RL：由于在*a的右子树根结点的左子树上插入结点，*a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行两次旋转（先右旋后左旋）操作。

java代码实现插入操作:

/**  * AVL定义  * @author WangShiXiang  *  * @param <T>  */ class BSTNode<T extends Comparable<T>>{ 	public T value; 	public int bf;//平衡因子实现复杂 此处存高度 	public BSTNode<T> left;	 	public BSTNode<T> right; 	public BSTNode() { 	} 	public BSTNode(T value,BSTNode<T> left,BSTNode<T> right){ 		this.value=value; 		this.left=left; 		this.right=right; 		this.bf=0; 	} }  /** 	 * AVL插入 	 * @param value 	 * @param root 	 * @return 	 */ 	public static <T extends Comparable<T>> BSTNode<T> insertNode(T value,BSTNode<T> root){ 		if (root==null) { 			return new BSTNode<T>(value,null,null); 		} 		int comparable=value.compareTo(root.value); 		if (comparable<0) { 			root.left=insertNode(value, root.left); 			if (getBf(root.left)-getBf(root.right)>1) { 				if (value.compareTo(root.left.value)<0) { 					root=LL_Rotate(root); 				}else { 					root=LR_Rotate(root); 				} 			} 		}else if (comparable>0) { 			root.right=insertNode(value, root.right); 			if (getBf(root.right)-getBf(root.left)>1) { 				if (value.compareTo(root.right.value)>0) { 					root=RR_Rotate(root); 				}else { 					root=RL_Rotate(root); 				} 			} 		} 		root.bf=(getBf(root.left)>getBf(root.right)?getBf(root.left):getBf(root.right))+1; 		return root; 	} 	/** 	 * 单向右旋转 	 * @param node 	 * @return 	 */ 	public static <T extends Comparable<T>> BSTNode<T> LL_Rotate(BSTNode<T> node) { 		BSTNode<T> k=node.left; 		node.left=k.right; 		k.right=node; 		node.bf=(getBf(node.left)>getBf(node.right)?getBf(node.left):getBf(node.right))+1; 		k.bf=(getBf(k.left)>getBf(k.right)?getBf(k.left):getBf(k.right))+1; 		return k; 	} 	/** 	 * 单项左旋转 	 * @param node 	 * @return 	 */ 	public static <T extends Comparable<T>> BSTNode<T> RR_Rotate(BSTNode<T> node) { 		BSTNode<T> k=node.right; 		node.right=k.left; 		k.left=node; 		node.bf=(getBf(node.left)>getBf(node.right)?getBf(node.left):getBf(node.right))+1; 		k.bf=(getBf(k.left)>getBf(k.right)?getBf(k.left):getBf(k.right))+1; 		return k; 	} 	/** 	 * 双向旋转（先左后右） 	 * @param node 	 * @return 	 */ 	public static <T extends Comparable<T>> BSTNode<T> LR_Rotate(BSTNode<T> node) { 		node.left=RR_Rotate(node); 		return LL_Rotate(node); 	} 	/** 	 * 双向旋转（先右后左） 	 * @param node 	 * @return 	 */ 	public static <T extends Comparable<T>> BSTNode<T> RL_Rotate(BSTNode<T> node) { 		node.right=LL_Rotate(node); 		return RR_Rotate(node); 	} 	/** 	 * 获取高度 	 * @param node 	 * @return 	 */ 	private static<T extends Comparable<T>> int getBf(BSTNode<T> node) { 		return node==null?-1:0; 	}