没想到苦逼IT女还得去“种树”——苦逼IT女种树记之二叉树

      想当初，爸爸妈妈、爷爷奶奶不让我去学农业，然后我就稀里糊涂滴进了IT行业，木有想到啊，IT和农业一样，都得种树。哈哈，开个小玩笑，不过人生何尝不是一个种树耕耘的过程呢，开始我们各自就是一颗种子，慢慢地长成一棵树，因为我们付出的努力不一样，最后得到的树也是不一样的。貌似又扯远了，还是来继续种二叉树吧，二叉树这棵树比较特殊，只要我们制定的规则以及数据一样，我们种到最后得到的结果应该是一样的：

       个人感觉二叉树这棵树可不像普通的树那么好种啊，我可是种了好几天的。

       二叉树的概念神马的我就不班门弄斧了，想了解更多二叉树的概念请去二叉树的维基百科--------------------->>> http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91   

       二叉树的难点还是它的实现（创建），但和之前的链表一结合起来，就会发现，其实链表和二叉树的结构是相似的，只是链表节点存的是指向前后节点的地址，而二叉树存的是指向左右节点的地址，明白了这一点，然后实现了链表，二叉树也就不难了。

 

         首先，我们要写一个二叉树的节点类：

/**
 * 节点类
 * @author ZhuMei
 */
public class TreeNode {

	//节点数据
	private int data;
	//左子树节点
	private TreeNode left;
	//右子树节点
	private TreeNode right;
	
	/**
	 * 构造方法1
	 */
	public TreeNode(){
		
	}
	/**
	 * 构造方法2
	 * @param n：要输入的数据
	 */
	public TreeNode(int  n){
		this.data = n;
	}
	/**
	 * 构造方法3
	 * @param data：要输入的数据
	 * @param left：左节点
	 * @param right：右节点
	 */
	public TreeNode(int data, TreeNode left, TreeNode right) {
		this.data = data;
		this.left = left;
		this.right = right;
	}

	public int getData() {
		return data;
	}
	public void setData(int data) {
		this.data = data;
	}
	public TreeNode getLeft() {
		return left;
	}
	public void setLeft(TreeNode left) {
		this.left = left;
	}
	public TreeNode getRight() {
		return right;
	}
	public void setRight(TreeNode right) {
		this.right = right;
	}
  
}

 

       然后当然就是二叉树的实现类了，我们主要是要实现构建一个二叉树，添加，删除功能，然后实现前、中、后序三种遍历方式。

       在这里，我仅用添加构建了一棵二叉树，改变添加顺序二叉树的结构就会改变，删除是借鉴的某位不知名的大神的，但我是在看懂的条件下自己敲出来的（不过大神的代码可不是这么容易看懂，暂时还是处于似懂非懂的状态，得趁热打铁多看几遍），模仿也是一种学习方式滴！

       然后用递归实现了前、中、后三种遍历方式并输出了结果：

/**
 * 节点的实现类
 * @author ZhuMei
 *
 */
public class BinTree {
	private TreeNode root = null;
	/**
	 * 添加方法
	 * @param node：要添加的对象
	 */
	public void add(TreeNode node){
		if(root == null)
			root = node;
		else
			sortNode(root,node);
	}

	/**
	 * 将node2添加到二叉树中
	 * @param root1：根节点
	 * @param node2：被添加的节点
	 */
	private void sortNode(TreeNode root1, TreeNode node2) {
		if(node2.getData()<root1.getData()){
			if(root1.getLeft() == null)
				root1.setLeft(node2);
			else
				sortNode(root1.getLeft(),node2);
		}else{
			if(root1.getRight() == null)
				root1.setRight(node2);
			else
				sortNode(root1.getRight(),node2);
		}
			
	}
	
	
	public boolean deleteNode(int data){
		TreeNode parent = root;
		TreeNode temp = root;
		boolean isLeft = true;
		//当找不到与data相等的值时，就一直找
		while(temp.getData()!=data){
			parent = temp;//将temp的值存在parent中
			if(data<temp.getData()){
				isLeft = true;
				temp = temp.getLeft();
			}else{
				isLeft = false;
				temp = temp.getRight();
			}
			//当找到最后（temp为null的时候说明已经遍历完）没有找到，返回false
			if(temp == null){
				return false;
			}
		}
		
		//当退出while时，说明已经找到值为data的节点,而且节点为temp
		
		//当temp不存在子节点的时候，直接删除temp（清空树 或 将temp的父节点（parent）的子节点设为null）
		if(temp.getLeft() == null && temp.getRight() == null){
			//如果temp是根节点，直接清空树
			if(temp == root)
				root =null;
			//如果temp是parent的左子节点，将parent的左子结点设为null
			else if(isLeft)
				parent.setLeft(null);
			//如果是右子节点，则将parent的右子节点设为null
			else
				parent.setRight(null);
		}
		
		//当temp没有右子节点的时候
		else if(temp.getRight() == null){
			//如果temp是根节点，让其左节点等于根节点
			if(temp == root)
				root = temp.getLeft();
			//如果temp为parent左子结点，将temp的左子结点设为parent的左子结点
			else if(isLeft)
				parent.setLeft(temp.getLeft());
			//否则设parent的右子节点
			else
				parent.setRight(temp.getLeft());	
		}
		
		//当temp没有左子节点的时候
		else if(temp.getLeft() == null){
			//若temp为根节点，则让其右子节点为根节点
			if(temp == root)
				root = temp.getRight();
			//如果temp是parent的左子结点，则将temp的右子节点设为parent的左子结点
			else if(isLeft)
				parent.setLeft(temp.getRight());
			//如果temp是parent的右子节点，则将temp的右子结点设为parent的右子节点
			else
				parent.setRight(temp.getRight());
		}
		
		//当temp的两个子节点都存在的时候
		else{
			//得到要被删除的节点temp的继承节点next
			TreeNode next = getNext(temp);
			//如果被删除的节点是根节点，将next设为根节点
			if(temp == root)
				root = next;
			//如果temp是parent的左子节点，将next设为设为parent的左子结点
			else if(isLeft)
				parent.setLeft(next);
			//如果temp是parent的右子节点，将next设为parent的右子节点
			else
				parent.setRight(next);
			next.setLeft(temp.getLeft());//将temp的左子结点赋给next的左子节点
		}
		return true;
	}
	
	/**
	 * 获取被删除节点的子节点中大的那一个，取代被删除的节点
	 * @param delNode：被删除的节点
	 */
	public TreeNode getNext(TreeNode delNode){
		TreeNode next = delNode;
		TreeNode nextParent = delNode;
		TreeNode temp = delNode.getRight();
		//当要被删除的右子节点存在（不为空）时,一直执行以下操作
		while(temp != null){
			nextParent = next;
			next = temp;
			temp = temp.getLeft();
		}
		//当跳出while循环的时候，说明此时的temp为null，而且next为temp的父节点nextParent为next的父节点
		if(next != delNode.getRight()){
			nextParent.setLeft(next.getRight());
			next.setRight(delNode.getRight());
		}
		return next;
	}
	
	
	/**
	 * 前序遍历：根→左→右
	 * @param root：根节点
	 */
	public void preOrder(TreeNode root){
		if(root == null)
			return;
		System.out.print(root.getData()+"   ");
		preOrder(root.getLeft());
		preOrder(root.getRight());
	}
	
	/**
	 * 中序遍历：左→根→右
	 * @param root
	 */
	public void inOrder(TreeNode root){
		if(root == null)
			return;
		inOrder(root.getLeft());
		System.out.print(root.getData()+"   ");
		inOrder(root.getRight());
	}

	/**
	 * 后序遍历：左→右→根
	 * @param root
	 */
	public void pastOrder(TreeNode root){
		if(root == null)
			return;
		pastOrder(root.getLeft());
		pastOrder(root.getRight());
		System.out.print(root.getData()+"   ");
	}
		
}

       当然，一个程序运行起来必须不能少了主函数，这个，就大家自己看情况写吧，当然是调用节点实现类里的方法哦！

       最后，做个小结吧，我总觉得“种树”好难，每次都半途而废，以至于把这个很久以前的任务到现在才完成，其实当自己把任务完成之后，也不是特别难。其实不论是敲代码还是平时的各种事情，有时候看起来会很难，但只要坚持做，会有结果的，而且当你做完的时候，会觉得“世界如此美好”，自己又会在不知不觉中改变。

评论

1 楼 刘凯宁 2013-09-30