漫談二叉搜索樹的基本算法(三種思路實現查詢操作)

import java.util.Scanner;

/**
 * 二叉搜索樹的操作集錦
 * 
 * @author Administrator
 *
 */
class BinSearchTreeTest02 {
	public Point1 root;

	// 訪問結點
	public static void visitKey(Point1 p) {
		System.out.println(p.getKey() + "  ");
	}

	// 構造樹
	public static Point1 Tree() {
		Point1 m = new Point1(4, null, null);
		Point1 a = new Point1(6, m, null);
		Point1 b = new Point1(5, null, a);
		Point1 c = new Point1(14, null, null);
		Point1 d = new Point1(10, b, c);
		Point1 e = new Point1(24, null, null);
		Point1 f = new Point1(25, e, null);
		Point1 g = new Point1(20, null, f);
		Point1 h = new Point1(15, d, g);
		return h;// root
	}

	// 構造空樹
	public static Point1 EmptyTree(int t) {
		Point1 a = new Point1(t, null, null);
		return a;
	}

	// *********************************查找操作****************************
	/**
	 * 二叉搜索樹查找操作方法1
	 * 
	 * @param t
	 * @param node
	 * @return
	 */
	public static boolean contains(int t, Point1 node) {
		if (node == null)
			return false;// 結點為空，查找失敗
		String st = Integer.toString(t);// 把要查找的結點轉化為String類型
		int result = compareTo(st, node);
		if (result == 1) {
			return true;
		} else {
			return false;
		}
	}

	public static int compareTo(String a, Point1 p) {
		// String b = Integer.toString(p.getKey());
		// if(a.equals(b))和下面這行是等價的
		if (a.equals(p.getKey() + ""))
			return 1;
		int i = 0, j = 0;
		if (p.getLeftChild() != null) {
			i = compareTo(a, p.getLeftChild());
		}
		if (p.getRightChild() != null) {
			j = compareTo(a, p.getRightChild());
		}
		if (i == 1) {
			return i;
		} else if (j == 1) {
			return j;
		} else {
			return -1;
		}
	}

	/**
	 * 二叉搜索樹查找操作方法2(遞歸算法) 尾遞歸的方式
	 * 
	 * @param t
	 * @param node
	 * @return
	 */
	public static Point1 contains2(int t, Point1 node) {
		if (node == null)
			return null;// 結點為空，查找失敗
		if (t > node.getKey())
			return contains2(t, node.getRightChild());// 查找右子樹
		else if (t < node.getKey())
			return contains2(t, node.getLeftChild());// 查找左子樹
		else
			return node;
	}

	/**
	 * 二叉搜索樹查找的搜索方法2的變形，非遞歸算法的效率更高 將尾遞歸改為迭代函數
	 * 
	 * @param args
	 */
	public static Point1 contains3(int t, Point1 node) {
		while (node != null) {
			if (t > node.getKey())
				node = node.getRightChild();
			else if (t < node.getKey())
				node = node.getLeftChild();
			else
				return node;
		}
		return null;
	}

	/**
	 * 二叉搜索樹的最大元素 根據其性質可以得出二叉搜索樹的最大元一定位於右子樹的最右端，最小元則相反
	 * 
	 * @param args
	 */
	public static int findMax(Point1 point) {
		if (point != null) {
			while (point.getRightChild() != null) {
				point = point.getRightChild();
			}
		}
		return point.getKey();
	}

	public static int findMin(Point1 point) {
		if (point == null)
			return 0;// 先判斷樹是否為空
		else if (point.getLeftChild() == null)
			return point.getKey();// 在判斷左子樹是否為空
		else
			return findMin(point.getLeftChild());
	}

	public static void main(String[] args, Point1 p) {
		System.out.println("此二叉樹的最大結點為：" + findMax(Tree()));
		System.out.println("此二叉樹的最小結點為：" + findMin(Tree()));
		@SuppressWarnings("resource")
		Scanner scanner = new Scanner(System.in);
		System.out.println("輸入一個結點，將判斷是否是此二叉樹的結點");
		int a = scanner.nextInt();
		if (contains2(a, Tree()) != null) 
			System.out.println(a + " 是此二叉樹的結點"); 
		else 
			System.out.println(a + " 不是此二叉樹的結點");	 
	}
}

class Point1 {
	private int key;
	private Point1 LeftChild, RightChild;

	public Point1(int key, Point1 LeftChild, Point1 RightChild) {
		this.key = key;
		this.LeftChild = LeftChild;
		this.RightChild = RightChild;
	}

	public Point1(int key) {
		this(key, null, null);
	}

	public int getKey() {
		return key;
	}

	public void setKey(char key) {
		this.key = key;
	}

	public Point1 getLeftChild() {
		return LeftChild;
	}

	public void setLeftChild(Point1 leftChild) {
		LeftChild = leftChild;
	}

	public Point1 getRightChild() {
		return RightChild;
	}

	public void setRightChild(Point1 rightChild) {
		RightChild = rightChild;
	}
}