java实现树的遍历
首先来看看树节点的定义：
TNode.java:
package datastructure.tree;
/**
*树节点
* @author yunfeiyang
*/
public class TNode<E> {
private TNode<E> LChild = null, RChild = null;
private E data;
/**
* default node
*/
public TNode() {
data = null;
left(null);
right(null);
}
/**
* node with data
* @param data data of the node
*/
public TNode(E data) {
this.data = data;
left(null);
right(null);
}
/**
* set data of the node
* @param data data of the node
*/
public void data(E data) {
this.data = data;
}
/**
* get data of the node
* @return data of the node
*/
public E data() {
return data;
}
/**
*set the reference of left child
* @param left reference of left child
*/
public void left(TNode<E> left) {
LChild = left;
}
/**
* get reference of left child
* @return reference of left child
*/
public TNode<E> left() {
return LChild;
}
/**
*set the reference of right child
* @param reference of right child
*/
public void right(TNode<E> left) {
RChild = left;
}
/**
* get reference of right child
* @return reference of right child
*/
public TNode<E> right() {
return RChild;
}
@Override
public String toString() {
String s = "a node with value:" + data.toString();
return s;
}
}
其次，树的遍历方法写在一个类当中：
TreeOutput.java:
package datastructure.tree;
import java.util.ArrayList;
/**
*遍历并输出树节点的值
* @author yunfeiyang
* @version 1.0
*/
public class TreeOutput<E> {
/**
* 中序遍历树节点
* @param root 树的根节点
* @param separate 分隔符
*/
public void inorderOutput(TNode<E> root, String separate) {
if (root == null) {
return;
}
inorderOutput(root.left(), separate);
System.out.print(root.data() + separate);
inorderOutput(root.right(), separate);
}
/**
* 后续遍历树节点
* @param root 树的根节点
* @param separate 分隔符
*/
public void postorderOutput(TNode<E> root, String separate) {
if (root == null) {
return;
}
postorderOutput(root.left(), separate);
postorderOutput(root.right(), separate);
System.out.print(root.data() + separate);
}
/**
* 前序遍历树节点
* @param root 数的根节点
* @param separate 分隔符
*/
public void preorderOutput(TNode<E> root, String separate) {
if (root == null) {
return;
}
System.out.print(root.data() + separate);
preorderOutput(root.left(), separate);
preorderOutput(root.right(), separate);
}
/**
* 层次遍历树节点
* @param root 树的根节点
* @param separate 分隔符
*/
public void levelorderOutput(TNode<E> root, String separate) {
if (root == null) {
return;
}
ArrayList<TNode<E>> queue=new ArrayList<TNode<E>>();
queue.add(root);
while(!queue.isEmpty())
{
TNode<E> head=queue.remove(0);
System.out.print(head.data()+separate);
if(head.left()!=null)
{
queue.add(head.left());
}
if(head.right()!=null)
{
queue.add(head.right());
}
}
}
}
最后写测试方法来测试下：
Main.java
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package datastructure.tree.test;
import datastructure.tree.TNode;
import datastructure.tree.TreeOutput;
/**
*
* @author Administrator
*/
public class Main {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
Main main = new Main();
TreeOutput<Integer> output = new TreeOutput<Integer>();
TNode<Integer> newNode = new TNode<Integer>(0);
TNode<Integer> root = main.initData(newNode);
System.out.print("中序遍历树节点:");
output.inorderOutput(root, ",");
System.out.println();
System.out.print("后序遍历树节点:");
output.postorderOutput(root, ",");
System.out.println();
System.out.print("前序遍历树节点:");
output.preorderOutput(root, ",");
System.out.println();
System.out.print("层次遍历树节点:");
output.levelorderOutput(root, ",");
System.out.println();
}
private TNode<Integer> initData(TNode<Integer> root) {
TNode<Integer> result=null;
if (root == null) {
result=root;
} else {
TNode<Integer> leftNode = new TNode<Integer>(10);
root.left(leftNode);
TNode<Integer> rightNode = new TNode<Integer>(20);
root.right(rightNode);
leftNode.left(new TNode<Integer>(30));
leftNode.right(new TNode<Integer>(40));
rightNode.left(new TNode<Integer>(50));
rightNode.right(new TNode<Integer>(60));
result= root;
}
return result;
}
}
