数据结构之二叉搜索树

       我勒个去啊。。。刚刚好不容易写了一篇博客，怎么突然就不见了。。只要再写一遍了。。它这个自动保存草稿真是坑爹啊。。受不鸟了。。。

       这学期开了数据结构的课，刚刚上完树，正好在蓝杰也学到了树，今天，就实现下二叉搜索树。

       所谓二叉搜索树，它的最主要特征就是对于任意一个节点X，它的所有的左子树上存放的关键字一定比X的关键字要小，而右子树上存放的则比X的要大。正是由于这种特性，使得我们在查找的时候特别容易，时间复杂度大概是O(log N)。下图就是一个二叉搜索树。

 首先，定义一个节点类。

/*
 * 定义一个二叉树的节点类
 */
public class Node {
	
	int data;
	Node root;
	Node right_child;
	Node left_child;
	Node parent;
	int position;
	
	public Node(int data){
		this.data = data;
	}
}

 实现的方法如下：

1、MakeEmpty

       这个方法用于将树初始化。

/*
	 *将一棵二叉树置为空树的方法
	 */
	public void MakeEmpty(Node root){
		if(root != null){
			MakeEmpty(root.right_child);
			MakeEmpty(root.left_child);
			root = null;
		}
		System.out.println("该树为空树！");
	}

 2、Find

        这个方法用来查找某一元素，需要传入你所要查找的元素以及一个树的根节点作为参数。因为二叉搜索树的特点，查找是一件非常容易的事。

/*
	 * 在一棵二叉搜索树中查找某一元素的方法
	 */
	public Node Find(int x, Node root){
		if(root == null){
			System.out.println("该树为空树！");
			return null;
		}
		if(x < root.data){
			return Find(x, root.left_child);
		}else if(x > root.data){
			return Find(x, root.right_child);
		}
		else
			return root;
	}

 3、FindMin 和 FindMax

        分别用于查找最小和最大的元素。需要传入一个树的根节点作为参数。对于FindMin只需要一直查找它的左节点直到为空即可，FindMax则只需要查找右节点。这里运用了递归和非递归两种方法来实现。

/*
	 *在一棵二叉搜索树中查找最小的元素的方法（递归实现）
	 */
	public Node FindMin(Node root){
		if(root == null){
			System.out.println("该树为空树！");
			return null;
		}
		else if(root.left_child == null){
			return root;
		}else
			return FindMin(root.left_child);
	}
	
	/*
	 * 在一棵二叉搜索树中查找最大元撒的方法（非递归实现）
	 * 从根节点开始，一直查找它的右子树，直到最后一层
	 */
	public Node FindMax(Node root){
		Node node = root;
		
		if(root == null){
			System.out.println("该树为空！");
			return null;
		}
		else{
			while(node.right_child != null){
				node = node.right_child;
			}
		
			return node;
		}
	}

 4、Insert

       插入的方法在概念上简单的，需要传入你所要插入的元素及根节点作为参数。对于要插入的元素，判断它和节点之间的关系，直到找到它的位置。比如对于上图所示的树，我们需要插入一个新的元素“5”，首先判断它和根节点的关系，应该存放在左子树上，再判断它和“2”的关系，应该存放在有子树上，再判断和“4”的关系，应该存放在右子树上，而“4”的右子树为空，于是我们就找到了存放它的位置。

/*
	 * 向一棵二叉搜索树中添加元素的方法 
	 */
	public Node Insert(int x, Node root){
		Node node = new Node(x);
		
		if(root == null){
			root = node;
			return root;
		}else{
			Node current_node = root;
			Node parent_node;
			while(true){
				parent_node = current_node;
				if(x < current_node.data){
					current_node = current_node.left_child;
					if(current_node == null){
						parent_node.left_child = node;
						return root;
					}
				}else{
					current_node = current_node.right_child;
					if(current_node == null){
						parent_node.right_child = node;
						return root;
					}
				}
			}
		}
	}

 5、Delete

        喜闻乐见的又到了删除的时候，需要传入你所要删除的元素已经树的根节点作为参数。二叉搜索树的删除是比较复杂的。它可能会遇到三种情况，第一种是要删除的节点没有子节点，这无疑是最简单的一种。第二种是它由一个子节点，这种情况也是比较简单的，只需要记下要删除的节点的父节点即可。第三种是要删除的节点有两个子节点，这时候我采取的策略是用要删除的节点的右子树上存放元素最小的节点来代替你所要删除的节点。

	/*
	 * 删除二叉搜索树中的一个元素
	 */
	public Node Delete(int x, Node root){
		Node node = root;
		Node node1 =  Find(x, root);
		if(node1 == null){
			System.out.println("要删除的元素不存在！");
		}else if((node1.right_child != null) && (node1.left_child != null)){
			//判断要删除的节点是否有两个子节点
			//如果有两个子节点，则该用该节点的右子树的最小元素的子节点来代替该节点
			//判断要删除的及节点是它的父节点的左节点还是右节点
			if(node1.data < node1.parent.data){//左节点
				node1.parent.left_child = FindMin(node1.right_child);
				FindMin(node1.right_child).parent = node1.parent;
			}else{
				node1.parent.right_child = FindMin(node1.right_child);
				FindMin(node1.right_child).parent = node1.parent;
			}
			FindMin(node1.right_child).left_child = node1.left_child;
			node1.left_child.parent = FindMin(node1.right_child);
			
			
		}else{
			//如果要删除的节点只有一个子节点，则让它的父节点指向它的子节点
			if(node1.data < node1.parent.data){//左节点
				if(node1.left_child == null){
					node1.parent.left_child = node1.right_child;
					node1.right_child.parent = node1.parent;
				}else{
					node1.parent.left_child = node1.left_child;
					node1.left_child.parent = node1.parent;
				}
			}else{
				if(node1.left_child == null){
					node1.parent.left_child = node1.right_child;
					node1.right_child.parent = node1.parent;
				}else{
					node1.parent.left_child = node1.left_child;
					node1.left_child.parent = node1.parent;
				}
			}		
		}
		return root;
	}

 6、PrintTree

       遍历二叉搜索树将其打印。需要传入根节点作为参数。这里用的是中序遍历的方法。

	/*
	 * 遍历打印二叉搜索树
	 */
	public void PrintTree(Node root){
		Node node = root;
		if(node.left_child != null){
			PrintTree(node.left_child);
		}
		System.out.println(node.data);
		if(node.right_child != null){
			PrintTree(node.right_child);
		}
	}