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;
    }
}