动手写一个二叉搜索树

前面已经手写了一个简单的双向链表

在此基础上再写一个简单的二叉搜索树【这里仅简单实现】。二叉搜索树在结构上跟双向链表比较相似，将左节点看做左子树，将右节点看做父节点，只是多个右字数的对应。

package com.tree;

import java.util.List;


/**
 * 实现二叉搜索树（又叫二叉排序树）
 * 	先思考正常情况，再考虑特殊情况，否则会进入到死胡同
 * @author Tang
 * @param <T>
 */
public class TreeTable<T extends Comparable<T>>{
	
	private TreeNode<T> rootNode;
	private int size;

 
	/**
	 * 添加元素
	 * @param data
	 */
    public void put(T data) {
        TreeNode<T> newNode = new TreeNode<T>(data);
    	
        //如果根节点为空，直接赋值
    	if (rootNode == null){
    		rootNode = newNode;
    		size++;
    		return;
        }
    	
        int ret = 0;
        TreeNode<T> currentNode = rootNode;
        TreeNode<T> parentNode = null;
        
        while (true){
        	parentNode = currentNode;
            //每次插入都从根节点进行遍历，同时不断的更换对比节点。
            ret = data.compareTo(currentNode.data);
            
            if (ret < 0){
            	//插入的数据比当前节点小，获取当前节点的左节点，跟左节点进行比较。如果左节点为null，数据就直接插入到这里
            	currentNode = currentNode.leftNode;
            	if(currentNode == null){
            		parentNode.leftNode = newNode;
            		return;
            	}
            } else {
            	//数据相等进行覆盖，不操作，所以这里只处理大于
            	currentNode = currentNode.rightNode;
            	if(currentNode == null){
            		parentNode.rightNode = newNode;
            		return;
            	}
            } 
        }
    }
    
    /**
     * 查找数据
     * @param data
     * @return
     */
    public TreeNode get(T data){
    	TreeNode<T> currentNode = rootNode;
        int ret;
        //从根节点开始遍历。并且不断的切换需要比较的节点为currentNode
        while(currentNode != null){
            ret = data.compareTo(currentNode.data);
            if (ret < 0){
            	currentNode = currentNode.leftNode;
            } else if (ret > 0){
            	currentNode = currentNode.rightNode;
            } else {
            	return currentNode;
            }
        }
        return null;
    }
    
    /**
     * 获取根节点
     * @return
     */
    public TreeNode getRootNode(){
    	return rootNode;
    }
    
    
    /**
     * 遍历数据。这里是按照顺序进行遍历的。
     */
    public void display() {
        display(rootNode);
    }
    private void display(TreeNode node) {
        if (node != null) {
            display(node.leftNode);
            System.out.print(" " + node.data);
            display(node.rightNode);
        }
    }
    
    /**
     * 前序遍历<br>
     * 	前序遍历的顺序是：根节点->左节点->右节点
     * @param e 开始遍历元素
     */
    public void prevIterator(TreeNode<T> node,List list){
        if (node != null) {
            //System.out.print(node.data + " ");
            list.add(node);
            prevIterator(node.leftNode,list);
            prevIterator(node.rightNode,list);
        }
    }
    
    /**
     * 中序遍历
     * @param e
     */
    public void midIterator(TreeNode<T> node,List list){
        if (node != null){
            midIterator(node.leftNode,list);
            //System.out.print(node.data + " ");
            list.add(node);
            midIterator(node.rightNode,list);
        }
    }
    
    /**
     * 后续遍历
     * @param e 开始遍历元素
     */
    public void subIterator(TreeNode<T> node,List list){
        if (node != null) {
            subIterator(node.leftNode,list);
            subIterator(node.rightNode,list);
            //System.out.print(node.data + " ");
            list.add(node);
        }
    }
    
    /**
     * 删除指定的数据
     * @param data
     */
    public boolean remove(T data){
    	TreeNode<T> delNode = get(data);
    	if(delNode == null){
    		return false;
    	}
    	TreeNode parentNode = delNode.parentNode;
    	//要删除的节点没有子节点，直接删除即可。
    	if(delNode.leftNode == null && delNode.rightNode == null){
    		if(delNode == rootNode){
    			rootNode = null;
    		} else {
    			if(delNode == parentNode.leftNode){//判断当前节点是左节点还是右节点
    				parentNode.leftNode = null;
    			} else {
    				parentNode.rightNode = null;
    			}
    		}
    	//要删除的节点只有左节点
    	} else if(delNode.rightNode == null){
    		TreeNode leftNode = delNode.leftNode;
    		
    		if(delNode == parentNode.leftNode){//如果当前删除的节点是左节点。直接对接即可
    			parentNode.leftNode = leftNode;
    		} else {							//如果当前删除的节点是右节点。
    			parentNode.rightNode = leftNode;
    		}
    		leftNode.parentNode = parentNode;
    		
    	//要删除的节点只有右节点
    	} else if(delNode.leftNode == null){
    		TreeNode rightNode = delNode.rightNode;
    		if(delNode == parentNode.rightNode){
    			parentNode.rightNode = rightNode;
    		} else {
    			parentNode.leftNode = rightNode;
    		}
    		
    	} else {
    		
    	}
    	return true;
    }
    
	
    
    /**
     * 构建树节点类
     * @author T
     */
	class TreeNode<T extends Comparable<T>>{
		
		private T data;
		private TreeNode<T> leftNode;
		private TreeNode<T> rightNode;
		private TreeNode<T> parentNode;
	
		/**
		 * @param data 节点的值
		 * @param parentNode 父节点
		 */
		public TreeNode(T data,TreeNode<T> parentNode){
			this.data = data;
			this.parentNode = parentNode;
		}
		
		public TreeNode(T data){
			this.data = data;
		}

		public T getData() {
			return data;
		}

		public void setData(T data) {
			this.data = data;
		}

		public TreeNode getLeftNode() {
			return leftNode;
		}

		public void setLeftNode(TreeNode leftNode) {
			this.leftNode = leftNode;
		}

		public TreeNode getRightNode() {
			return rightNode;
		}

		public void setRightNode(TreeNode rightNode) {
			this.rightNode = rightNode;
		}

		public TreeNode getParentNode() {
			return parentNode;
		}

		public void setParentNode(TreeNode parentNode) {
			this.parentNode = parentNode;
		}
		
	}

}

           

测试：

package com.tree;

import java.util.ArrayList;
import java.util.List;

import com.tree.TreeTable.TreeNode;

public class TreeTableTest {
	
	public static void main(String[] args) {
		TreeTable<Integer> tt = new TreeTable<Integer>();
		
		tt.put(3);
		tt.put(8);
		tt.put(1);
		tt.put(10);
		tt.put(5);
		tt.put(9);
		tt.put(7);
		tt.put(18);
		tt.put(30);
		tt.put(25);
		tt.put(38);
		
		tt.display();
		System.out.println();
		System.out.println("===========================");
		System.out.println("获取根节点："+tt.getRootNode().getData());
		
		
		//遍历的结果存储在list集合中
		
		//前序遍历
		List<TreeNode> list = new ArrayList<TreeNode>();
		tt.prevIterator(tt.getRootNode(),list);
		System.out.println();
		for(TreeNode node:list){
			System.out.print(node.getData()+" ");
		}
		System.out.println("前序遍历完毕");
		
		
		//中序遍历
		list.clear();
		tt.midIterator(tt.getRootNode(),list);
		System.out.println();
		for(TreeNode node:list){
			System.out.print(node.getData()+" ");
		}
		System.out.println("中序遍历完毕");
		
		
		//后续遍历
		list.clear();
		tt.subIterator(tt.getRootNode(),list);
		System.out.println();
		for(TreeNode node:list){
			System.out.print(node.getData()+" ");
		}
		System.out.println("后续遍历完毕");
	}

}

           

结果：

1 3 5 7 8 9 10 18 25 30 38
===========================
获取根节点：3

3 1 8 5 7 10 9 18 30 25 38 前序遍历完毕

1 3 5 7 8 9 10 18 25 30 38 中序遍历完毕

1 7 5 9 25 38 30 18 10 8 3 后续遍历完毕