ÓÃjavaÔõô¹¹ÔìÒ»¸ö¶þ²æÊ÷ÄØ£¿

ѧÊý¾Ý½á¹¹Ê±ÓõÄÊÇC£¬ÓÃÁ´±í¹¹Ôì¶þ²æÊ÷£¬µ«´ó¼Ò¶¼¶®µÄ£¬javaÖв»¿ÉÒÔ×Ô¼º×öÖ¸Õ루ÄÚ´æ·ÖÅ䣩Õⲿ·Ö£¬ÄÇôÔõô¹¹ÔìÒ»¸ö¶þ²æÊ÷ÄØ£¿

java¹¹Ôì¶þ²æÊ÷£¬¿ÉÒÔͨ¹ýÁ´±íÀ´¹¹Ô죬ÈçÏ´úÂ룺
public class BinTree {
public final static int MAX=40;
BinTree []elements = new BinTree[MAX];//²ã´Î±éÀúʱ±£´æ¸÷¸ö½Úµã
    int front;//²ã´Î±éÀúʱ¶ÓÊ×
    int rear;//²ã´Î±éÀúʱ¶Óβ
private Object data; //Êý¾ÝÔªÊý
private BinTree left,right; //Ö¸Ïò×ó,ÓÒº¢×Ó½áµãµÄÁ´
public BinTree()
{
}
public BinTree(Object data)
{ //¹¹ÔìÓÐÖµ½áµã
   this.data = data;
   left = right = null;
}
public BinTree(Object data,BinTree left,BinTree right)
{ //¹¹ÔìÓÐÖµ½áµã
   this.data = data;
   this.left = left;
   this.right = right;
}
public String toString()
{
   return data.toString();
}
//Ç°Ðò±éÀú¶þ²æÊ÷
public static void preOrder(BinTree parent){ 
     if(parent == null)
      return;
     System.out.print(parent.data+" ");
     preOrder(parent.left);
     preOrder(parent.right);
}
//ÖÐÐò±éÀú¶þ²æÊ÷
public void inOrder(BinTree parent){
   if(parent == null)
      return;
   inOrder(parent.left);
   System.out.print(parent.data+" ");
     inOrder(parent.right);
}
//ºóÐò±éÀú¶þ²æÊ÷
public void postOrder(BinTree parent){
   if(parent == null)
    return;
   postOrder(parent.left);
   postOrder(parent.right);
   System.out.print(parent.data+" ");
}
// ²ã´Î±éÀú¶þ²æÊ÷ 
public void LayerOrder(BinTree parent)
{ 
     elements[0]=parent;
     front=0;rear=1;
   while(front

¶þ²æÊ÷µÄÏà¹Ø²Ù×÷£¬°üÀ¨´´½¨£¬ÖÐÐò¡¢ÏÈÐò¡¢ºóÐò£¨µÝ¹éºÍ·ÇµÝ¹é£©£¬ÆäÖÐÖصãµÄÊÇjavaÔÚÏÈÐò´´½¨¶þ²æÊ÷ºÍºóÐò·ÇµÝ¹é±éÀúµÄµÄʵÏÖ¡£
package com.algorithm.tree;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;

public class Tree {

private Node root;

public Tree() {
}

public Tree(Node root) {
  this.root = root;
}

//´´½¨¶þ²æÊ÷
public void buildTree() {

  Scanner scn = null;
  try {
   scn = new Scanner(new File("input.txt"));
  } catch (FileNotFoundException e) {
   // TODO Auto-generated catch block
   e.printStackTrace();
  }
  root = createTree(root,scn);
}
//ÏÈÐò±éÀú´´½¨¶þ²æÊ÷
private Node createTree(Node node,Scanner scn) {

  String temp  = scn.next();

  if (temp.trim().equals("#")) {
   return null;
  } else {
   node = new Node((T)temp);
   node.setLeft(createTree(node.getLeft(), scn));
   node.setRight(createTree(node.getRight(), scn));
   return node;
  }

}

//ÖÐÐò±éÀú(µÝ¹é)
public void inOrderTraverse() {
  inOrderTraverse(root);
}

public void inOrderTraverse(Node node) {
  if (node != null) {
   inOrderTraverse(node.getLeft());
   System.out.println(node.getValue());
   inOrderTraverse(node.getRight());
  }
}

//ÖÐÐò±éÀú(·ÇµÝ¹é)
public void nrInOrderTraverse() {

  Stack stack = new Stack();
  Node node = root;
  while (node != null || !stack.isEmpty()) {
   while (node != null) {
    stack.push(node);
    node = node.getLeft();
   }
   node = stack.pop();
   System.out.println(node.getValue());
   node = node.getRight();

  }

}
//ÏÈÐò±éÀú(µÝ¹é)
public void preOrderTraverse() {
  preOrderTraverse(root);
}

public void preOrderTraverse(Node node) {
  if (node != null) {
   System.out.println(node.getValue());
   preOrderTraverse(node.getLeft());
   preOrderTraverse(node.getRight());
  }
}

//ÏÈÐò±éÀú£¨·ÇµÝ¹é£©
public void nrPreOrderTraverse() {

  Stack stack = new Stack();
  Node node = root;

  while (node != null || !stack.isEmpty()) {

   while (node != null) {
    System.out.println(node.getValue());
    stack.push(node);
    node = node.getLeft();
   }
   node = stack.pop();
   node = node.getRight();
  }

}

//ºóÐò±éÀú(µÝ¹é)
public void postOrderTraverse() {
  postOrderTraverse(root);
}

public void postOrderTraverse(Node node) {
  if (node != null) {
   postOrderTraverse(node.getLeft());
   postOrderTraverse(node.getRight());
   System.out.println(node.getValue());
  }
}

//ºóÐø±éÀú(·ÇµÝ¹é)
public void nrPostOrderTraverse() {

  Stack stack = new Stack();
  Node node = root;
  Node preNode = null;//±íʾ×î½üÒ»´Î·ÃÎʵĽڵã

  while (node != null || !stack.isEmpty()) {

   while (node != null) {
    stack.push(node);
    node = node.getLeft();
   }

   node = stack.peek();

   if (node.getRight() == null || node.getRight() == preNode) {
    System.out.println(node.getValue());
    node = stack.pop();
    preNode = node;
    node = null;
   } else {
    node = node.getRight();
   }

  }

}

//°´²ã´Î±éÀú
public void levelTraverse() {
  levelTraverse(root);
}

public void levelTraverse(Node node) {

  Queue queue = new LinkedBlockingQueue();
  queue.add(node);
  while (!queue.isEmpty()) {

   Node temp = queue.poll();
   if (temp != null) {
    System.out.println(temp.getValue());
    queue.add(temp.getLeft());
    queue.add(temp.getRight());
   }

  }

}

}

//Ê÷µÄ½Úµã

class Node {

private Node left;
private Node right;
private T value;

public Node() {
}
public Node(Node left,Node right,T value) {
  this.left = left;
  this.right = right;
  this.value = value;
}

public Node(T value) {
  this(null,null,value);
}
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 T getValue() {
  return value;
}
public void setValue(T value) {
  this.value = value;
}

}
²âÊÔ´úÂ룺
package com.algorithm.tree;

public class TreeTest {

/**
  * @param args
  */
public static void main(String[] args) {
  Tree tree = new Tree();
  tree.buildTree();
  System.out.println("ÖÐÐò±éÀú");
  tree.inOrderTraverse();
  tree.nrInOrderTraverse();
  System.out.println("ºóÐø±éÀú");
  //tree.nrPostOrderTraverse();
  tree.postOrderTraverse();
  tree.nrPostOrderTraverse();
  System.out.println("ÏÈÐò±éÀú");
  tree.preOrderTraverse();
  tree.nrPreOrderTraverse();

//
}

}

¶¨ÒåÒ»¸ö½áµãÀࣺ
public class Node {
private int value;
private Node leftNode;
private Node rightNode;

public Node getRightNode() {
  return rightNode;
}
public void setRightNode(Node rightNode) {
  this.rightNode = rightNode;
}
public int getValue() {
  return value;
}
public void setValue(int value) {
  this.value = value;
}
public Node getLeftNode() {
  return leftNode;
}
public void setLeftNode(Node leftNode) {
  this.leftNode = leftNode;
}

}

³õʼ»¯½áµãÊ÷£º
public void initNodeTree()
{
  int nodeNumber;
  HashMap map = new HashMap();
  Node nodeTree = new Node();

  Scanner reader = new Scanner(System.in);

  nodeNumber = reader.nextInt();
  for(int i = 0; i < nodeNumber; i++) {
   int value = reader.nextInt();
   String str = reader.next();
   map.put(str, value);
  }

  if (map.containsKey("#")) {
   int value = map.get("#");
   nodeTree.setValue(value);
   setChildNode(map, value, nodeTree);
  }

  preTraversal(nodeTree);
}

private void setChildNode(HashMap map, int nodeValue, Node parentNode) {
  int value = 0;
  if (map.containsKey("L" + nodeValue)) {
   value = map.get("L" + nodeValue);
   Node leftNode = new Node();
   leftNode.setValue(value);
   parentNode.setLeftNode(leftNode);

   setChildNode(map, value, leftNode);
  }

  if (map.containsKey("R" + nodeValue)) {
   value = map.get("R" + nodeValue);
   Node rightNode = new Node();
   rightNode.setValue(value);
   parentNode.setRightNode(rightNode);

   setChildNode(map, value, rightNode);
  }
}

Ç°Ðò±éÀú¸Ã½áµãÊ÷£º
public void preTraversal(Node nodeTree) {
  if (nodeTree != null) {
   System.out.print(nodeTree.getValue() + "\t");
   preTraversal(nodeTree.getLeftNode());
   preTraversal(nodeTree.getRightNode());
  }
}