/**
 * java 二叉查找樹（增刪改查操作）
 */
public class Main
{
	public static void main ( String[] args )
	{
		BinarySearchTree btr = new BinarySearchTree();
		btr.insert ( 6 );
		btr.insert ( 2 );
		btr.insert ( 1 );
		btr.insert ( 3 );
		btr.insert ( 4 );
		btr.insert ( 8 );
		System.out.println ( btr.find ( 10 ) );
		System.out.println ( btr.findMin() );
		System.out.println ( btr.findMax() );
	}
}

// 定義樹節(jié)點(diǎn)
class BinaryNode
{
	Comparable element; // 保存節(jié)點(diǎn)內(nèi)容
	BinaryNode left; // 保存節(jié)點(diǎn)的左孩子
	BinaryNode right; // 保存節(jié)點(diǎn)的右孩子

	// 定義構(gòu)造函數(shù)，初始化成員
	BinaryNode ( Comparable theElement )
	{
		this ( theElement, null, null );
	}

	BinaryNode ( Comparable theElement, BinaryNode lt, BinaryNode rt )
	{
		element = theElement;
		left = lt;
		right = rt;
	}
}

// 定義二叉查找樹，將樹節(jié)點(diǎn)封裝成樹并進(jìn)行各種操作
class BinarySearchTree
{
	private BinaryNode root;

	public BinarySearchTree()
	{
		root = null;
	}

	// 判斷樹是否為空
	public boolean isEmpty()
	{
		return root == null;
	}

	// 查找樹中是否存在某節(jié)點(diǎn)
	public Comparable find ( Comparable x )
	{
		return find2 ( x, root ).element;
	}

	// 查找樹中最小的節(jié)點(diǎn)
	public Comparable findMin()
	{
		return findMin2 ( root ).element;
	}

	// 查找樹中最大的節(jié)點(diǎn)
	public Comparable findMax()
	{
		return findMax2 ( root ).element;
	}

	// 向樹中插入某節(jié)點(diǎn)
	public void insert ( Comparable x )
	{
		root = insert2 ( x, root );
	}

	// 刪除樹中某節(jié)點(diǎn)
	public void remove ( Comparable x )
	{
		root = remove2 ( x, root );
	}

	// 查找的具體操作,該操作對(duì)外是透明的,后面的操作同理
	private BinaryNode find2 ( Comparable x, BinaryNode t )
	{
		// 如果不存在，就新添加一個(gè)輔助樹節(jié)點(diǎn)，并將其內(nèi)容設(shè)為不存在
		if ( t == null )
		{
			BinaryNode s = new BinaryNode ( "不存在該元素！" );
			return s;
		}

		if ( x.compareTo ( t.element ) < 0 )   // 如果查找的元素比當(dāng)前根節(jié)點(diǎn)小，則繼續(xù)再該節(jié)點(diǎn)的左子樹中查找，直至根節(jié)點(diǎn)為空
		{
			return find2 ( x, t.left );
		}
		else if ( x.compareTo ( t.element ) > 0 )   // 如果查找的元素比當(dāng)前根節(jié)點(diǎn)大，則繼續(xù)再該節(jié)點(diǎn)的右子樹中查找，直至根節(jié)點(diǎn)為空
		{
			return find2 ( x, t.right );
		}
		else
			return t; // 如果查找的節(jié)點(diǎn)內(nèi)容和當(dāng)前根節(jié)點(diǎn)的內(nèi)容相等，則返回當(dāng)前根節(jié)點(diǎn)
	}

	// 找最小節(jié)點(diǎn)的具體過(guò)程
	private BinaryNode findMin2 ( BinaryNode t )
	{
		if ( t == null )
		{
			return null;
		}
		else if ( t.left == null )
		{
			return t;
		}
		return findMin2 ( t.left );
	}

	// 找最大節(jié)點(diǎn)的具體過(guò)程
	private BinaryNode findMax2 ( BinaryNode t )
	{
		if ( t != null )
		{
			while ( t.right != null )
			{
				t = t.right;
			}
		}
		return t;
	}

	// 構(gòu)造二叉查找樹的具體過(guò)程
	private BinaryNode insert2 ( Comparable x, BinaryNode t )
	{
		if ( t == null ) // 若樹是空的，則構(gòu)造一棵新的樹，t為樹的根
		{
			t = new BinaryNode ( x, null, null );
		}
		else if ( x.compareTo ( t.element ) < 0 )   // 如果要插入的元素小于當(dāng)前節(jié)點(diǎn)，則插入在該節(jié)點(diǎn)的左邊
		{
			t.left = insert2 ( x, t.left );
		}
		else if ( x.compareTo ( t.element ) > 0 )   // 如果要插入的元素大于當(dāng)前節(jié)點(diǎn)，則插入在該節(jié)點(diǎn)的又邊
		{
			t.right = insert2 ( x, t.right );
		}
		else
			; // 否則什么也不做
		return t;
	}

	// 刪除節(jié)點(diǎn)的具體操作過(guò)程
	private BinaryNode remove2 ( Comparable x, BinaryNode t )
	{
		if ( t == null )
		{
			return t;
		}
		if ( x.compareTo ( t.element ) < 0 )
		{
			t.left = remove2 ( x, t.left );
		}
		else if ( x.compareTo ( t.element ) > 0 )
		{
			t.right = remove2 ( x, t.right );
		}
		else if ( t.left != null && t.right != null )
		{
			t.element = findMin2 ( t.right ).element;
			t.right = remove2 ( x, t.right );
		}
		else
		{
			t = ( t.left != null ) ? t.left : t.right;
		}
		return t;
	}
}

標(biāo)簽：

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。