定義

樹的遍歷方法：

代碼實現：

package yao.demo;import java.util.*;//二叉樹的定義class BinaryTree{	int val;	BinaryTree left;	BinaryTree right;	public BinaryTree(int val){		this.val = val;	}}/** * @author leo * @param f 如果在查找的過程中，查找成功，則f指向查找成功的節點；如果查找失敗，f指向查找路徑上的最后一個節點，也即待插入節點 * @param root 指向二叉排序樹的根節點 */public class BinarySortTree {	static BinaryTree f;	static BinaryTree root;		//二叉排序樹的創建	public static void createBST(BinaryTree root, int key){		BinaryTree newNode = new BinaryTree(key);		if(key > root.val){			if(root.right == null)				root.right = newNode;			else				createBST(root.right, key);		}		else if(key < root.val){			if(root.left == null)				root.left = newNode;			else				createBST(root.left, key);		}		else{			System.out.PRintln("The node " + key + " is already exists");			return;		}	}		//二叉排序樹的查找	//如果查找成功，則f指向查找成功的節點；如果查找失敗，f指向查找路徑上的最后一個節點，也即待插入節點	public static boolean sort(BinaryTree root, int key, BinaryTree p){		if(root == null){			f = p;			System.out.println("查找失敗！");			return false;		}		else if(root.val == key){			f = root;			System.out.println("查找成功！");			return true;		}		else if(root.val >= key)			return sort(root.left, key, root);		else 			return sort(root.right, key, root);	}		//二叉排序樹的插入	public static void insert(BinaryTree rt, int key){		if(sort(root, 100, null) == false){			BinaryTree newNode = new BinaryTree(100);			if(f == null)				root = newNode;			else if(key > f.val)				f.right = newNode;			else 				f.left = newNode;			System.out.println("插入成功！");			return;		}		System.out.println("不允許插入重復元素！");	}		//二叉樹的先序遍歷	public static void preOrder(BinaryTree rt){		if(rt != null){			System.out.print(rt.val + " ");				preOrder(rt.left);				preOrder(rt.right);		}	}		//二叉樹的中序遍歷	public static void inOrder(BinaryTree rt){		if(rt != null){			inOrder(rt.left);			System.out.print(rt.val + " ");			inOrder(rt.right);			}	}		//二叉樹的后序遍歷	public static void postOrder(BinaryTree rt){		if(rt != null){			postOrder(rt.left);			postOrder(rt.right);			System.out.print(rt.val + " ");		}	}		//二叉樹的層次遍歷	//用隊列實現     public static void levelOrder(BinaryTree rt){    	 if(rt == null)    		 return;    	 Queue<BinaryTree> queue = new LinkedList<BinaryTree>();    	 queue.add(rt);    	 while(!queue.isEmpty()){    		 BinaryTree temp = queue.remove();    		 System.out.print(temp.val + " ");    		 if(temp.left != null)    			 queue.add(temp.left);    		 if(temp.right != null)    			 queue.add(temp.right);     	 }     }	public static void main(String[] args) {		int[] array = {35, 76, 12, 22, 16, 48, 90, 46, 9, 40};		root = new BinaryTree(array[0]);		for(int i = 1; i < array.length; i++){			createBST(root, array[i]);		}		System.out.println(sort(root, 22, null));		System.out.println(sort(root, 100, null));		insert(root, 100);	    System.out.print("先序遍歷：");	    preOrder(root);	    System.out.println();	    System.out.print("中序遍歷：");	    inOrder(root);	    System.out.println();	    System.out.print("后序遍歷：");	    postOrder(root);	    System.out.println();	    System.out.print("層次遍歷：");	    leverOrder(root);	}}