Go语言视频零基础入门到精通

thinkinjava

递归在我们程序开发中运用很广泛，在适合的场合可以减少我们代码量，递归很普遍的运行如：如求前n项的和及其乘积、汉诺塔、二叉树的遍历。

下面是二叉树中遍历的递归运用。

下面的代码写得复杂了点，采用泛型的方式来写，呵呵，天天写j2me的代码，这里巩固一下。

import java.util.Comparator;
import java.util.Random;
public class Tree< T> {
    private T data;
    private Tree< T> left;
    private Tree< T> right;
    private Comparator< T> compator = null;
  
    public Tree(T data, Comparator< T> compator) {
        this.data = data;
        this.left = null;
        this.right = null;
        this.compator = compator;
    }
   
    /**
     * 创建二叉树，返回根结点
     *
     * @param input
     * @return
     */
    public Tree< T> createTree(T[] input) {
       Tree< T> root = null;
        Tree< T> temp = null;
        for (int i = 0; i < input.length; i++) {
            // 创建根节点
            if (root == null) {
                root = temp = new Tree< T>(input, compator);
            } else {
                // 回到根结点
                temp = root;
                // 添加节点
                while (compator.compare(temp.data, input) != 0) {
                    if (compator.compare(temp.data, input) >= 0) {
                        if (temp.left != null) {
                            temp = temp.left;
                        } else {
                            temp.left = new Tree< T>(input, compator);
                        }
                    } else {
                        if (temp.right != null) {
                            temp = temp.right;
                        } else {
                            temp.right = new Tree< T>(input, compator);
                        }
                    }
                }
            }
        }
        return root;
    }
  
    /**
     * 前序遍历
     *
     * @param tree
     */
    public void preOrder(Tree< T> tree) {
       if (tree != null) {
            System.out.print(tree.data + " ");
            preOrder(tree.left);
            preOrder(tree.right);
        }
    }
  
    /**
     * 中序遍历
     *
     * @param tree
     */
    public void midOrder(Tree< T> tree) {
        if (tree != null) {
            midOrder(tree.left);
            System.out.print(tree.data + " ");
            midOrder(tree.right);
        }
    }
  
    /**
     * 后序遍历
     *
     * @param tree
     */
    public void posOrder(Tree< T> tree) {
        if (tree != null) {
            posOrder(tree.left);
            posOrder(tree.right);
            System.out.print(tree.data + " ");
        }
    }
  
    public T findData(Tree< T> tree, T data) {
        if (tree == null) {
            System.out.println("没有找到");
            return null;
        }
        if (compator.compare(data, tree.data) == 0) {
            System.out.print("\nthe data:" + tree.data);
            return (T) data ;
        }
        if (compator.compare(data, tree.data) < 0) {
            return findData(tree.left, data);
        } else {
            return findData(tree.right, data);
        }
    }
  
    /**
     * @param args
     */
    public static void main(String[] args) {
        Comparator< Integer> compator = new Comparator< Integer>() {
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);
            }
        };
        Integer[] input = new Integer[10];
        for(int i=0;i< 10;i++){
              input=i;
            //Random r = new Random();
            //try {
             //   input =r.nextInt(10);
           // } catch (Exception ex) {
            //    ex.printStackTrace();
            //}
        }
        Tree< Integer> tree= new Tree< Integer>(1, compator);
        tree = tree.createTree(input);
        System.out.print("前序遍历：");
        tree.preOrder(tree);
        System.out.print("\n中序遍历：");
        tree.midOrder(tree);
        System.out.print("\n后序遍历：");
        tree.posOrder(tree);
        int findData = 6;
        tree.findData(tree, findData);
    }
   
}

运行结果：

C:\java>javac Tree.java

C:\java>java Tree
前序遍历：0 1 2 3 4 5 6 7 8 9
中序遍历：0 1 2 3 4 5 6 7 8 9
后序遍历：9 8 7 6 5 4 3 2 1 0
the data:6

yy1020

不错啊。