复习BST树(java)

BST树算法掌握不够熟练 对递归有了更深的了解
找最大，最小节点，插入节点，查找节点，遍历不算太难 注意细心
删除某个节点有三种可能（考虑root节点是否为空）
1.删除叶子节点

2.删除只有左子树或者只有右子树的节点（要考虑它是否为根节点，考虑它是父节点的左孩子还是右孩子）

3.删除既有左子树也有右子树的节点（找大于它的最小值—->找右子树中最左边的节点，替换该节点位置的值，并删除这个最左边的节点（要考虑这个节点是否有右子树，是父节点的左孩子还是右孩子))

package solution;

class TreeNode {
	int value;
	TreeNode parent;
	TreeNode left;
	TreeNode right;
	public TreeNode(int val) {
		this.value = val;
		this.left = this.right = null;
	}
	public TreeNode(int value, TreeNode parent, TreeNode left, TreeNode right) {
		this.value = value;
		this.parent = parent;
		this.left = left;
		this.right = right;
	}
	public void setParent(TreeNode parent )
	{
		this.parent=parent;
	}
	public void setLeft(TreeNode x )
	{
		this.left=x;
	}
	public void setRight(TreeNode x )
	{
		this.right=x;
	}
}

public class Solution {
	public static TreeNode getMax(TreeNode root) {
		if (root == null) // 注意判断root为空的情况
			return null;
		while (root.right != null)
			root = root.right;
		return root;
	}

	public static TreeNode getMin(TreeNode root) {
		if (root == null)
			return null;
		while (root.left != null)
			root = root.left;
		return root;
	}

	public static TreeNode pre(TreeNode root, TreeNode x) {
		if (x.left != null)// 有左子树找左子树的最大的
			return getMax(x.left);
		else {
			TreeNode p = x.parent;
			while (p != null && p.left == x) {
				x = p;
				p = p.parent;
			}
			return p;
		}
	}

	public static TreeNode post(TreeNode root, TreeNode x) {
		if (x.right != null)// 有右子树找右子树的最小的
			return getMin(x.right);
		else {
			TreeNode p = x.parent;// 来记录父节点
			while (p != null && p.right == x) {
				x = p;
				p = p.parent;
			}
			return p;
		}
	}

	public static TreeNode search1(TreeNode root, int val) {//注意递归条件
		if (root == null)
			return null;
		if (val < root.value)
			return search1(root.left, val);
		else if (val > root.value)
		return	search1(root.right, val);//**不可以少写return**

		 return root;

	}

	public static TreeNode search2(TreeNode root, int val) {
		if (root == null)
			return null;
		while (root != null) {
			if (val < root.value)
				root = root.left;
			else if (val > root.value)
				root = root.right;
			else
				break;
		}
		return root;
	}

	public static TreeNode insert1(TreeNode root, TreeNode x) {
		if (root == null)
			root = x;
		if (x.value < root.value)
			root.left = insert1(root.left, x);
		if (x.value > root.value)
			root.right = insert1(root.right, x);
		return root;// 记录根节点并返回
	}

	public static TreeNode insert2(TreeNode root, TreeNode x) {
		if (root == null)
			root = x;
		TreeNode p = null;// 来记录父节点
		while (root != null) {
			p = root;
			if (x.value < root.value)
				root = root.left;
			if (x.value > root.value)
				root = root.right;
		}
		x.parent = p;
		if (x.value < p.value)
			p.left = x;
		else
			p.right = x;
		return root;
	}

	public static void delete(TreeNode root, TreeNode x) {
		if (root == null)
			return;
		TreeNode p = null;
		while (root != null) {
			if (x.value < root.value)
				
			{
				p = root;//**不可以放在if外面**
				root = root.left;
				
			}
			else if (x.value > root.value)
			{
				p = root;
				root = root.right;
				
			}
				
			else {
				if (root.left == null && root.right == null) {
					p.left = null;
					p.right = null;
				}

				else if (root.left != null && root.right == null) {
					if (p == null)
						root = root.left;
					else {
						// 如果是一个节点的左孩子
						if (p.left == root)
							p.left = root.left;
						// 如果是一个节点的右孩子
						if (p.right == root)
							p.right = root.left;
					}
				} else if (root.right != null && root.left == null) {
					if (p == null)
						root = root.right;
					else {
						// 如果是一个节点的左孩子
						if (p.left == root)
							p.left = root.right;
						// 如果是一个节点的右孩子
						if (p.right == root)
							p.right = root.right;
					}

				}
				// 有两个孩子的情况
				else {
					TreeNode rmin = root.right;
					TreeNode rminp = null;
					while (rmin.left != null) {
						rminp = rmin;
						rmin = rmin.left;
					}
					root.value = rmin.value;
					if (rminp.left == rmin)// 如果要删的节点是父节点的左孩子
						rminp.left = rmin.right;
					if (rminp.right == rmin)// 如果要删的节点是父节点的右孩子
						rminp.right = rmin.right;
				}
				break;
			}
		}
	}
	public static void tranverse(TreeNode root)
	{
		if(root==null) return;
		System.out.println(root.value);
		if(root.left!=null) tranverse(root.left);
		if(root.right!=null) tranverse(root.right);
	}
	public static void main(String[] args)
	{
		TreeNode node12=new TreeNode(12);
		TreeNode node16=new TreeNode(16);
		TreeNode node17=new TreeNode(17);
		TreeNode node14=new TreeNode(14);
		TreeNode node10=new TreeNode(10);
		TreeNode node11=new TreeNode(11);
		TreeNode node5=new TreeNode(5);
		node5.setParent(node10);
		node12.setParent(node11);
		node16.setParent(node17);
		node11.setRight(node12);
		node11.setParent(node14);
		node17.setLeft(node16);
		node17.setParent(node14);
		node14.setLeft(node11);
		node14.setRight(node17);
		node14.setParent(node10);
		node10.setLeft(node5);
		node10.setRight(node14);
		TreeNode max=getMax(node10);
		System.out.println("max:"+max.value);
		TreeNode min=getMin(node10);
		System.out.println("min:"+min.value);
		TreeNode x=new TreeNode(12);
		TreeNode y=new TreeNode(14);
		System.out.println("\n删除12:");
		delete(node10, x);
		tranverse(node10);
		System.out.println("\n插入12:");
		insert1(node10, x);
		tranverse(node10);
		TreeNode t=search1(node10, 14);
		System.out.println("查找14的节点的父节点值"+t.parent.value);
		System.out.println("\n删除14:");
		delete(node10, y);
		tranverse(node10);
		TreeNode pt= post(node10,node16);
		System.out.println("\n16的后继节点:"+pt.value);
		TreeNode pre= pre(node10,node11);
		System.out.println("\n11的前驱节点:"+pre.value);
	}
}