1 二叉查找树定义（查找最好时间复杂度O(logN)，最坏时间复杂度O(N)）

 

在二叉查找树中：
(01) 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
(02) 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
(03) 任意节点的左、右子树也分别为二叉查找树。
(04) 没有键值相等的节点

 

 

2 具体代码流程

 节点结构

public class BiTreeNode {
    private Object data;
    private BiTreeNode lchild, rchild;

    public BiTreeNode() {
        this(null);
    }

    public BiTreeNode(Object data) {
        this(data, null, null);
    }

    public BiTreeNode(Object data, BiTreeNode lchild, BiTreeNode rchild) {
        this.data = data;
        this.lchild = lchild;
        this.rchild = rchild;
    }

    public Object getData() {
        return data;
    }

    public BiTreeNode getLchild() {
        return lchild;
    }

    public BiTreeNode getRchild() {
        return rchild;
    }

    public void setData(Object data) {
        this.data = data;
    }

    public void setLchild(BiTreeNode lchild) {
        this.lchild = lchild;
    }

    public void setRchild(BiTreeNode rchild) {
        this.rchild = rchild;
    }
}

 头结点（这个类其实可以不需要直接定义在上面那个类一个root静态变量就可以）

public class BiTree {
    public BiTreeNode root;
    private static int index = 0;

    public BiTree(){
        this.root = null;
    }

    public BiTree(BiTreeNode root){
        this.root = root;
    }

  public BiTreeNode getRoot() {
        return root;
    }

    public void setRoot(BiTreeNode root) {
        this.root = root;
    }

}

  方法

public class DebugBiTree {

    private int index = 0;

    //创建二叉树
    public BiTree createBiTree(){
        BiTreeNode d = new BiTreeNode('D');
        BiTreeNode g = new BiTreeNode('G');
        BiTreeNode h = new BiTreeNode('H');
        BiTreeNode e = new BiTreeNode('E', g, null);
        BiTreeNode b = new BiTreeNode('B', d, e);
        BiTreeNode f = new BiTreeNode('F', null, h);
        BiTreeNode c = new BiTreeNode('C', f, null);
        BiTreeNode a = new BiTreeNode('A', b, c);
        return new BiTree(a);
    }

    public static void main(String[] args) throws Exception {
        DebugBiTree debugBiTree = new DebugBiTree();
        BiTree biTree = debugBiTree.createBiTree();
        BiTreeNode root = biTree.root;

        
        //先根遍历查找结点G
        BiTreeNode result = searchNode(root, 'G');
        System.out.println(result.getData());

        //计算二叉树中结点个数
        System.out.println(countNode(root));
       
    }

    //二叉树先根遍历查找
    public static BiTreeNode searchNode(BiTreeNode T, Object x){
        if (T != null){
            if (T.getData().equals(x))
                return T;
            else{
                BiTreeNode lresult = searchNode(T.getLchild(), x);
                return  lresult != null?lresult:searchNode(T.getRchild(), x);
            }
        }
        return null;
    }

    //计算二叉树中结点个数
    public static int countNode(BiTreeNode T){
        int count = 0;
        if (T != null){
            ++count;
            count += countNode(T.getLchild());
            count += countNode(T.getRchild());
        }
        return count;
    }


}

 

  2  平衡二叉树

1：定义

       1、父节点的左子树和右子树的高度之差不能大于1，也就是说不能高过1层，否则该树就失衡了，此时就要旋转节点，在

编码时，我们可以记录当前节点的高度，比如空节点是-1，叶子节点是0，非叶子节点的height往根节点递增，比如在下图

中我们认为树的高度为h=2。

　　2、它的左子树和右子树都是平衡二叉树。

2：旋转

    节点再怎么失衡都逃不过4种情况，下面我们一一来看一下。

① 左左情况（左子树的左边节点）

我们看到，在向树中追加“节点1”的时候，根据定义我们知道这样会导致了“节点3"失衡，满足“左左情况“，可以这样想，把这

棵树比作齿轮，我们在“节点5”处把齿轮往下拉一个位置，也就变成了后面这样“平衡”的形式，如果用动画解释就最好理解了。

 

② 右右情况（右子树的右边节点）

同样，”节点5“满足”右右情况“，其实我们也看到，这两种情况是一种镜像，当然操作方式也大同小异，我们在”节点1“的地方

将树往下拉一位，最后也就形成了我们希望的平衡效果。

 

③左右情况（左子树的右边节点）

从图中我们可以看到，当我们插入”节点3“时，“节点5”处失衡，注意，找到”失衡点“是非常重要的，当面对”左右情况“时，我们将

失衡点的左子树进行"右右情况旋转"，然后进行”左左情况旋转“，经过这样两次的旋转就OK了，很有意思，对吧。

 

④右左情况(右子树的左边节点）

这种情况和“情景3”也是一种镜像关系，很简单，我们找到了”节点15“是失衡点，然后我们将”节点15“的右子树进行”左左情况旋转“，然后进行”右右情况旋转“，最终得到了我们满意的平衡。

 

1  计算树的高度及判断是否是平衡二叉树

public class TreeNode<T> {
	T data;
	TreeNode<T> left;
	TreeNode<T> right;
	
	public TreeNode(T data){
		this.data = data;
	}

}

public class CheckBalanceTreeTest {
	
	@Test
	public void testBalanced(){
		TreeNode<Integer> node1 = new TreeNode<Integer>(1);
		TreeNode<Integer> node2 = new TreeNode<Integer>(2);
		TreeNode<Integer> node3 = new TreeNode<Integer>(3);
		TreeNode<Integer> node4 = new TreeNode<Integer>(4);
		TreeNode<Integer> node5 = new TreeNode<Integer>(5);
		TreeNode<Integer> node6 = new TreeNode<Integer>(6);
		TreeNode<Integer> node7 = new TreeNode<Integer>(7);
		TreeNode<Integer> node8 = new TreeNode<Integer>(8);
		TreeNode<Integer> node9 = new TreeNode<Integer>(9);
		
		node1.left = node2;
		node1.right = node3;
		
		node2.left = node4;
		node2.right = node5;
		
		node3.left = node6;
		node3.right = node7;
		
		node4.left = node8;
		
		node7.right = node9;
		CheckBalanceTree.getHeight(node1);
		Assert.assertTrue(CheckBalanceTree.isBalanced(node1));
		Assert.assertTrue(CheckBalanceTree.isBalancedGood(node1));
	}
	
}

public class CheckBalanceTree {
	
	/**
	 * 返回树的高度
	 * @param root
	 * @return
	 */
	public static int getHeight(TreeNode<Integer> root){
		if(root == null){
			return 0;
		}
		
		return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
	}
	
	/**
	 * 判断树是否平衡<br>
	 * 此方法时间复杂度为O(NlogN),效率不高
	 * @param root
	 * @return
	 */
	public static boolean isBalanced(TreeNode<Integer> root){
		if(root == null){
			return true;
		}
		
		int heightDiff = getHeight(root.left) - getHeight(root.right);
		if(Math.abs(heightDiff) > 1){
			return false;
		}else{
			return isBalanced(root.left) && isBalanced(root.right);
		}
	}

	/**
	 * 检查树的高度,若子树不平衡直接返回-1
	 * @return
	 */
	private static int checkHeight(TreeNode<Integer> root){
		if(root == null){
			return 0;
		}
		
		int leftHeight = checkHeight(root.left);
		if(leftHeight == -1){
			return -1;
		}
		
		int rightHeight = checkHeight(root.right);
		if(rightHeight == -1){
			return -1;
		}
		
		int heightDiff = leftHeight -  rightHeight;
		if(Math.abs(heightDiff) > 1){
			return -1;
		}else{
			return Math.max(leftHeight, rightHeight) + 1;
		}
	}
	
	public static boolean isBalancedGood(TreeNode<Integer> root){
		if(checkHeight(root) == -1){
			return false;
		}else{
			return true;
		}
	}
	
}

  至于删除增加等操作后续再说