今天楠哥和大家一起来讨论一下Java当中二叉树的实现。 树是一种高级数据结构，但是却十分常用，稍微复杂的问题就会涉及到树的应用。本文先就树（Tree）的最简单形式——二叉树进行一些简单的分析。顾名思义，二叉树（Binary Tree）即为每个节点至多只有两个子结点（Child Node）的树，因为子结点的个数具有一个固定的范围，所以就可以用顺序存储的办法进行存储。第i个结点的左右子结点分别储存于2i和2i+1的位置。顺序存储的实现可参见本系列文章之《Java链表——菜鸟学数据结构（一）》（http://www.liubonan.com/articles/349.html）。（楠哥计算机学习网www.liubonan.com）

但是由于并不是每个二叉树结点都一定有子结点，这样就会浪费很大的存储空间。为此，我们可以使用非顺序存储的方式，本文也就这种方式进行详细的介绍。使用非顺序存储所使用的结点可以使用三种设计方式，分别是单指向、双指向和三指向式。单指向式的结点中有一个指向其父节点的属性，但是这样的方式会造成从根到叶节点无法顺利的进行遍历。另外一种方法是双指向式，每个节点指向其左右子结点（没有则为NULL），本文基于这种设计实现。另外一种三指向式包含了前两种的特点，但是只有特定问题才使用这种设计，所以在此不作阐述。（楠哥计算机学习网www.liubonan.com）

下面的代码当中实现了一个二叉排序树，每个节点的左节点或左子树的值都小于其本身，而其右节点或右子树的值都大于其本身，该算法将在后面详解，此例的重点在于描述二叉树的数据结构。下文中，将详细介绍该树的各种遍历方法。（楠哥计算机学习网www.liubonan.com）

package ds;
//楠哥计算机学习网www.liubonan.com
public class Node {

	private int data;
	private int depth;
	private boolean visited;

	private Node left, right;

	public Node(int data)
	{
		this.setData(data);
		this.setLeft(null);
		this.setRight(null);
		this.setVisited(false);
	}

	public Node getLeft() {
		return left;
	}

	public void setLeft(Node left) {
		this.left = left;
	}

	public Node getRight() {
		return right;
	}

	public void setRight(Node right) {
		this.right = right;
	}

	public int getData() {
		return data;
	}

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

	public int getDepth() {
		return depth;
	}

	public void setDepth(int depth) {
		this.depth = depth;
	}

	public boolean isVisited() {
		return visited;
	}

	public void setVisited(boolean visited) {
		this.visited = visited;
	}
}

package ds;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
//楠哥计算机学习网www.liubonan.com
public class BinaryTree {

	private Node root;

	public BinaryTree(int data)
	{
		Node temp = new Node(data);
		setRoot(temp);
	}

	public Node getRoot() {
		return root;
	}

	public void setRoot(Node root) {
		this.root = root;
	}
	//楠哥计算机学习网www.liubonan.com
	public void add_it(int data)
	{
		Node current = root;
		Node prev=null;
		boolean childflag = false;

		while(current != null)
		{
			prev = current;

			if(data  q = new LinkedList();

		q.add(root);

		while(!q.isEmpty())
		{
			Node temp = q.remove();
			if(temp.getLeft()!=null)
				q.add(temp.getLeft());
			if(temp.getRight()!=null)
				q.add(temp.getRight());
			System.out.print(temp.getData() + " ");
		}

	}
	//楠哥计算机学习网www.liubonan.com
	public void dfs_it()
	{
		Stack s = new Stack();

		s.push(root);

		while(!s.isEmpty())
		{
			Node temp = s.pop();

			if(((temp.getLeft() == null)&&(temp.getRight() == null)) || (temp.isVisited()))
				System.out.print(temp.getData() + " ");
			else
			{

				if(temp.getRight() == null)
				{
					Node left = temp.getLeft();
					temp.setVisited(true);

					s.push(temp);
					s.push(left);

				}
				else
				{
					if(temp.getLeft() == null)
					{
						Node right = temp.getRight();
						temp.setVisited(true);

						s.push(temp);
						s.push(right);
					}
					else
					{
						Node left = temp.getLeft();
						Node right = temp.getRight();
						temp.setVisited(true);
						s.push(temp);
						s.push(right);
						s.push(left);
					}
				}
			}
		}

	}

}

package ds;
//楠哥计算机学习网www.liubonan.com
public class Tester {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BinaryTree t = new BinaryTree(5);

		t.add_re(6,t.getRoot());
		t.add_re(7,t.getRoot());
		t.add_re(2,t.getRoot());
		t.add_re(3,t.getRoot());
		t.add_re(1,t.getRoot());

		t.add_it(8);
		t.add_it(10);
		t.add_it(4);
		t.add_it(9);

		t.dfs_re(t.getRoot());

		System.out.println();
		t.dfs_it();

		System.out.println();
		t.bfs();
	}

}