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

javalearner

递归在我们程序开发中运用很广泛，在适合的场合可以减少我们代码量，递归很普遍的运行如：如求前n项的和及其乘积、汉诺塔、二叉树的遍历。 下面是二叉树中遍历的递归运用。 下面的代码写得复杂了点，采用泛型的方式来写，呵呵，天天写j2me的代码，这里巩固一下。

1. import java.util.Comparator;
   
2. import java.util.Random;
   
3. public class Tree< T> {
   
4.     private T data;
   
5.     private Tree< T> left;
   
6.     private Tree< T> right;
   
7.     private Comparator< T> compator = null;
   
8.   
   
9.     public Tree(T data, Comparator< T> compator) {
   
10.         this.data = data;
    
11.         this.left = null;
    
12.         this.right = null;
    
13.         this.compator = compator;
    
14.     }
    
15.    
    
16.     /**
    
17.      * 创建二叉树，返回根结点
    
18.      *
    
19.      * @param input
    
20.      * @return
    
21.      */
    
22.     public Tree< T> createTree(T[] input) {
    
23.        Tree< T> root = null;
    
24.         Tree< T> temp = null;
    
25.         for (int i = 0; i < input.length; i++) {
    
26.             // 创建根节点
    
27.             if (root == null) {
    
28.                 root = temp = new Tree< T>(input[i], compator);
    
29.             } else {
    
30.                 // 回到根结点
    
31.                 temp = root;
    
32.                 // 添加节点
    
33.                 while (compator.compare(temp.data, input[i]) != 0) {
    
34.                     if (compator.compare(temp.data, input[i]) >= 0) {
    
35.                         if (temp.left != null) {
    
36.                             temp = temp.left;
    
37.                         } else {
    
38.                             temp.left = new Tree< T>(input[i], compator);
    
39.                         }
    
40.                     } else {
    
41.                         if (temp.right != null) {
    
42.                             temp = temp.right;
    
43.                         } else {
    
44.                             temp.right = new Tree< T>(input[i], compator);
    
45.                         }
    
46.                     }
    
47.                 }
    
48.             }
    
49.         }
    
50.         return root;
    
51.     }
    
52.   
    
53.     /**
    
54.      * 前序遍历
    
55.      *
    
56.      * @param tree
    
57.      */
    
58.     public void preOrder(Tree< T> tree) {
    
59.        if (tree != null) {
    
60.             System.out.print(tree.data + " ");
    
61.             preOrder(tree.left);
    
62.             preOrder(tree.right);
    
63.         }
    
64.     }
    
65.   
    
66.     /**
    
67.      * 中序遍历
    
68.      *
    
69.      * @param tree
    
70.      */
    
71.     public void midOrder(Tree< T> tree) {
    
72.         if (tree != null) {
    
73.             midOrder(tree.left);
    
74.             System.out.print(tree.data + " ");
    
75.             midOrder(tree.right);
    
76.         }
    
77.     }
    
78.   
    
79.     /**
    
80.      * 后序遍历
    
81.      *
    
82.      * @param tree
    
83.      */
    
84.     public void posOrder(Tree< T> tree) {
    
85.         if (tree != null) {
    
86.             posOrder(tree.left);
    
87.             posOrder(tree.right);
    
88.             System.out.print(tree.data + " ");
    
89.         }
    
90.     }
    
91.   
    
92.     public T findData(Tree< T> tree, T data) {
    
93.         if (tree == null) {
    
94.             System.out.println("没有找到");
    
95.             return null;
    
96.         }
    
97.         if (compator.compare(data, tree.data) == 0) {
    
98.             System.out.print("
99. the data:" + tree.data);
    
100.             return (T) data ;
     
101.         }
     
102.         if (compator.compare(data, tree.data) < 0) {
     
103.             return findData(tree.left, data);
     
104.         } else {
     
105.             return findData(tree.right, data);
     
106.         }
     
107.     }
     
108.   
     
109.     /**
     
110.      * @param args
     
111.      */
     
112.     public static void main(String[] args) {
     
113.         Comparator< Integer> compator = new Comparator< Integer>() {
     
114.             public int compare(Integer o1, Integer o2) {
     
115.                 return o1.compareTo(o2);
     
116.             }
     
117.         };
     
118.         Integer[] input = new Integer[10];
     
119.         for(int i=0;i< 10;i++){
     
120.               input[i]=i;
     
121.             //Random r = new Random();
     
122.             //try {
     
123.              //   input[i] =r.nextInt(10);
     
124.            // } catch (Exception ex) {
     
125.             //    ex.printStackTrace();
     
126.             //}
     
127.         }
     
128.         Tree< Integer> tree= new Tree< Integer>(1, compator);
     
129.         tree = tree.createTree(input);
     
130.         System.out.print("前序遍历：");
     
131.         tree.preOrder(tree);
     
132.         System.out.print("
133. 中序遍历：");
     
134.         tree.midOrder(tree);
     
135.         System.out.print("
136. 后序遍历：");
     
137.         tree.posOrder(tree);
     
138.         int findData = 6;
     
139.         tree.findData(tree, findData);
     
140.     }
     
141.    
     
142. }

复制代码

运行结果：
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

   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/9/000428890.zip