package com.itjob.structure;

public class Tree {
	TreeNode root;
	TreeNode parent;
	boolean b;

	public boolean add(int d) {
		// 增加数据的方法
		TreeNode jd = new TreeNode(d);
		if (root == null) {
			// 如果根节点为空，那么把新节点加给根节点
			root = jd;
		} else {
			TreeNode current = root;
			while (current != null) {
				// 是找到一个位置加新节点
				if (d == current.data) {
					// 如果已经存在，则直接返回false 表示加失败
					return false;
				} else if (d > current.data) {
					// 如果该值大于当前节点，那么应该往右边找
					parent = current; // 记录要加新节点的父节点
					b = true; // 记录是左边还是右边
					current = current.right;
				} else if (d < current.data) {
					parent = current;
					b = false;
					current = current.left;
				}
			}
			if (b) {
				// 如果是右儿子为空 ，就加父节点的右边
				parent.right = jd;
			} else {
				parent.left = jd;
			}
		}
		return true;
	}

	public TreeNode find(int d) {
		// 查询的方法
		TreeNode current = root;
		while (current != null) {
			if (current.data == d)
				return current;
			else {
				// 记录找到节点的父节点，以方便删除操作
				parent = current;
				if (d > current.data) {
					current = current.right;
					b = true;
				} else if (d < current.data) {
					current = current.left;
					b = false;
				}
			}
		}
		return current;
	}

	public boolean delete(int d) {
		TreeNode current = find(d);
		if (current == null) {
			return false;
		} else if (current.left == null && current.right == null) {
			// 如果要删除的节点是页节点
			if (current == root) {
				// 如果是根节点（也是页节点），直接让根节点==null
				root = null;
			} else if (b) {
				parent.right = null;
			} else {
				parent.left = null;
			}
		} else if (current.left == null) {
			// 如果删除节点只有右节点
			if (b) {
				parent.right = current.right;
			} else {
				parent.left = current.right;
			}
		} else if (current.right == null) {
			// 如果删除节点只有左节点
			if (b) {
				// 该变量记录了要删除的节点，在其父节点的左边还是右边
				parent.right = current.left;
			} else {
				parent.left = current.left;
			}
		} else {
			TreeNode temp = fenlie(current);
			// 分裂节点
			if (b)
				parent.right = temp;
			else
				parent.left = temp;
		}
		return true;
	}

	public TreeNode fenlie(TreeNode c) {
		TreeNode temp = c.right;
		TreeNode p = temp; // 用来记录要删除节点右儿子那边的最小节点
		TreeNode pp = temp; // 用来记录要删除节点右儿子那边的最小节点的父节点
		while (temp != null) {
			// 找到要删除节点右儿子那边的最小节点
			pp = p;
			p = temp;
			temp = temp.left;
		}
		if (pp == p) {
			// 如果删除节点的右儿子节点没有左儿子
			// 把删除节点左儿子加到删除节点的右儿子的左边
			pp.left = c.left;
			return pp;
		} else {
			pp.left = p.right;// 把找到的节点的右儿子部分加到该节点父节点的左边
			p.left = c.left;// 把删除节点的左儿子加到分裂节点的左边
			p.right = c.right;// 把删除节点的右儿子加到分裂节点的右边
			return p;
		}
	}

	public boolean modify(int s, int m) {
		// 修改数据的方法=先删除后增加，这样还是有//顺序的
		delete(s);
		return add(m);
	}

	public void print(TreeNode jd) {
		// 递归中序遍历该有序二叉树
		if (jd != null) {
			print(jd.left);
			System.out.print(jd + " ");
			print(jd.right);
		}
	}

	public void p() {
		print(root);
	}

	public static void main(String[] args) {
		Tree t = new Tree();
		t.add(5);
		t.add(7);
		t.add(3);
		t.add(9);
		t.add(1);
		t.p();
		System.out.println();
		t.modify(3, 18);// 把接点值为3的接点，把该值改为18
		t.delete(9);// 删除接点值为9的接点
		t.p();
	}
}
