本文共 3336 字，大约阅读时间需要 11 分钟。

Java与算法（11）

1.通过给定一个有序数组生成一棵平衡二叉搜索树

public class BuildAVL {	public static class Node {		public int value;		public Node left;		public Node right;		public Node(int data) {			this.value = data;		}	}		public static Node build(int[] array)  {		if (array==null) {			return null;		}				return buildtree(array, 0,array.length-1);	}	public static Node buildtree(int[] array,int start,int end) {		if (start>end) {			return null;		}				int mid = (start+end)/2;		Node root = new Node(array[mid]);		root.left = buildtree(array, start, mid-1);		root.right = buildtree(array, mid+1, end);				return root;	}	public static void print(Node root) {		if (root==null) {			return;		}		print(root.left);		System.out.print(root.value+"  ");		print(root.right);	}	public static void main(String[] args) {			int[] a = {
  1,4,9,15,26,33,45,59,62,79};			Node root = build(a);			print(root);	}}

2.判断一棵树是否为二叉搜索树和完全二叉树

public class isBSTandCBT {	List
   
     list = new LinkedList<>();	public static class Node {		int data;		Node left;		Node right;		public Node(int data) {			// TODO Auto-generated constructor stub			this.data = data;			left = null;			right = null;		}	}			public void toArrry(Node root) {		if (root==null) {			return;		}				toArrry(root.left);		list.add(root.data);		toArrry(root.right);	}	public boolean isBST() {		for(int i=0;i
    
      queue = new LinkedList
     
      ();		boolean leaf = false;		Node l = null;		Node r = null;		queue.offer(head);		while (!queue.isEmpty()) {			head = queue.poll();			l = head.left;			r = head.right;			if ((leaf && (l != null || r != null)) || (l == null && r != null)) {				return false;			}			if (l != null) {				queue.offer(l);			}			if (r != null) {				queue.offer(r);			} else {				leaf = true;			}		}		return true;	}			public static void main(String[] args) {		Node head = new Node(4);		head.left = new Node(2);		head.right = new Node(6);		head.left.left = new Node(1);		head.left.right = new Node(3);		head.right.left = new Node(5);		isBSTandCBT isBSTandCBT  = new isBSTandCBT();		isBSTandCBT.toArrry(head);		System.out.println(isBSTandCBT.isBST());		System.out.println(isCBT(head));	}}
     
    
   

3.给定一个数组，判断是否可能为一棵二叉搜索树后序遍历的结果

public class BSTArray {		public static class Node {		int data;		Node left;		Node right;		public Node(int data) {			// TODO Auto-generated constructor stub			this.data = data;			left = null;			right = null;		}	}				public boolean isPostArray(int[]  array) {		if (array==null && array.length==0) {			return false;		}				return isBSTArray(array, 0,array.length-1);	}			public boolean isBSTArray(int[] array,int start,int end) {		if (start==end) {			return true;		}		int less = -1;		int more = end;		for(int i=start;i
   
    end) {			return null;		}		Node root = new Node(array[end]);		int less = -1;		int more = end;		for(int i=start;i
    
     array[i]) {				less=i;			}  else {				more= more==end?i:more;			}		}				root.left=toBST(array, start, less);		root.right = toBST(array, more, end-1);		return root;			}	public void prinf(Node root) {		if (root==null) {			return ;		}		prinf(root.left);		System.out.print(root.data+" ");		prinf(root.right);	}		public static void main(String[] args) {			BSTArray bstArray = new BSTArray();			int[] a={
  1,4,3,7,27,10,5};			System.out.println(bstArray.isPostArray(a));			Node root = bstArray.arrayToBst(a);			bstArray.prinf(root);	}}
    
   

转载地址：http://ivcqb.baihongyu.com/