数据结构与算法：二叉树

 

public class TreeNode {

	private int data;

	private TreeNode leftNode;

	private TreeNode rightNode;

	public TreeNode(int data) {
		this.data = data;
		this.leftNode = null;
		this.rightNode = null;
	}

	/**
	 * 把value插入二叉树
	 * @param value
	 */
	public void insertNode(int value) {
		if (value < this.data) {
			if (this.leftNode == null)
				this.leftNode = new TreeNode(value);
			else
				this.leftNode.insertNode(value);
		} else if (value > this.data) {
			if (this.rightNode == null)
				this.rightNode = new TreeNode(value);
			else
				this.rightNode.insertNode(value);
		} else {
			return;
		}
	}
	
	/**
	 * 搜索二叉树中是否有value值
	 * @param value
	 * @return
	 */
	public boolean searchNode(int value){
		if(value == this.data)
			return true;
		else if(value < this.data){
			if(this.leftNode != null)
				return this.leftNode.searchNode(value);
			else
				return false;
		}
		else{
			if(this.rightNode != null)
				return this.rightNode.searchNode(value);
			else
				return false;
		}
	}
	
	/**
	 * 前序遍历
	 * @return String
	 */
	public static String preOrder(TreeNode node){
		StringBuffer sb = new StringBuffer();
		sb.append(node.data).append(" ");
		if(node.leftNode != null)
			sb.append(preOrder(node.leftNode));
		if(node.rightNode != null)
			sb.append(preOrder(node.rightNode));
		return sb.toString();
	}

	/**
	 * 中序遍历
	 * @param node
	 * @return String
	 */
	public static String inOrder(TreeNode node){
		StringBuffer sb = new StringBuffer();
		if(node.leftNode != null){
			sb.append(inOrder(node.leftNode));
		}
		sb.append(node.data).append(" ");
		if(node.rightNode != null){
			sb.append(inOrder(node.rightNode));
		}
		return sb.toString();
	}
	
	/**
	 * 后序遍历
	 * @param node
	 * @return String
	 */
	public static String postOrder(TreeNode node){
		StringBuffer sb = new StringBuffer();
		if(node.leftNode != null)
			sb.append(postOrder(node.leftNode));
		if(node.rightNode != null)
			sb.append(postOrder(node.rightNode));
		sb.append(node.data).append(" ");
		return sb.toString();	
	}
	
	public int getData() {
		return data;
	}

	public void setData(int 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;
	}

}

 

 

 

import junit.framework.TestCase;

/**
 * 二叉树
 * 
 * @author jsczxy2
 * 
 */
public class TestBinaryTree extends TestCase {

	@Override
	protected void setUp() throws Exception {
		super.setUp();
	}

	public void testBinaryTree() {
		TreeNode node = new TreeNode(10);
		node.insertNode(6);
		node.insertNode(5);
		node.insertNode(7);
		node.insertNode(11);
		node.insertNode(13);
		node.insertNode(12);
		System.out.println(node.searchNode(7));
		System.out.println(node.searchNode(17));

		System.out.println("前序遍历: " + TreeNode.preOrder(node));
		System.out.println("中序遍历: " + TreeNode.inOrder(node));
		System.out.println("后序遍历: " + TreeNode.postOrder(node));
	}

}