Fork me on GitHub

Java面试题总结八算法

发表于 | 分类于 | |
1.使用随机算法产生一个数，要求把1-1000W之间这些数全部生成。（考察高效率，解决产生冲突的问题）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
以100为例，1000W时将value值更改即可，选取1-100范围方便时输出检验是否正确。
先构建一个value大小的数组，按下标存储1-value范围的值。
有了这样一个数组之后，用random.nextInt(value) 每次随机生成[0,value)范围的值，用count+value 作为下标交换count+value 和count位置的两个数，比如交换 list[0+5] 和list[0]。 下一次count++，交换某个位置和list[1],这样相当于随机选取某个位置的数，逐一放在数组的第0个位置、第1个位置。注意：count+value不能超过原本value的值，每次count++都要value--。

public static void main(String[] args) {
         Random random = new Random();
         long start = System.currentTimeMillis();
         int value = 100;
         //使用数组速度更快
         int[] list = new int[value];
         for (int j = 0; j < value; ++j) {
             list[j] = j+1;
         }
         int index = 0;
         int count = 0;
         int tmp = 0;
         while (value > 0) {
             index = random.nextInt(value);
             //System.out.println(list[count + index]);
             tmp = list[count + index];
             list[count + index] = list[count];
             list[count] = tmp;
             ++count;
             --value;
         }
         long end = System.currentTimeMillis();
         //----验证是否正确
         Arrays.sort(list);
         int i = 0, size = list.length;
         for (; i < size; ++i) {
             //System.out.println(list[i]);
             if (list[i] != (i + 1))
                 System.out.println(i + "error" + list[i]);
          }
         //----验证是否正确
         System.out.println("creat4------");
         System.out.println("执行耗时 : " + (end - start) / 1000f + " 秒 ");
         System.out.println("完了，集合大小为" + list.length);
    }
2.两个有序数组的合并排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
思路：新建一个以两个集合长度之和为长度的新数组，从两数组最左边开始比起，把小的放入新集合，并用变量标记后一位置，
    每次比较都是比较的最左边未比较过的元素（通过变量），循环比较，直至其中有一个集合遍历结束，将另一个集合剩余部分加入新集合中
    

public class MyClass {

    public static void main(String[] args) {

        int[] num1 = new int[]{1, 2, 4, 6, 7, 123, 411, 5334, 1414141, 1314141414};

        int[] num2 = new int[]{0, 2, 5, 7, 89, 113, 5623, 6353, 134134};

        //变量用于存储两个集合应该被比较的索引（存入新集合就加一）

        int a = 0;

        int b = 0;

        int[] num3 = new int[num1.length + num2.length];

        for (int i = 0; i < num3.length; i++) {

            if (a < num1.length && b < num2.length) {   //两数组都未遍历完，相互比较后加入

                if (num1[a] > num2[b]) {

                    num3[i] = num2[b];

                    b++;

                } else {

                    num3[i] = num1[a];

                    a++;

                }

            } else if (a < num1.length) {   //num2已经遍历完，无需比较，直接将剩余num1加入

                num3[i] = num1[a];

                a++;

            } else if (b < num2.length) {    //num1已经遍历完，无需比较，直接将剩余num2加入

                num3[i] = num2[b];

                b++;

            }

        }

        System.out.println("排序后:" + Arrays.toString(num3));

    }

}
3.一个数组的倒序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;
public class lianxi31 {
public static void main(String[] args)
{
	Scanner s = new Scanner(System.in);
 	int a[] = new int[20];
	System.out.println("请输入多个正整数（输入-1表示结束）：");
	 int i=0,j;
 	do{
	 	a[i]=s.nextInt();
	  	i++;
	 }while (a[i-1]!=-1);
 	System.out.println("你输入的数组为：");
	 for( j=0; j<i-1; j++) 
	 {
		 System.out.print(a[j]+" ");
	 }
 	System.out.println("\n数组逆序输出为：");
	 for( j=i-2; j>=0; j=j-1) 
	 {
 		System.out.print(a[j]+" ");
	 }
 	}
}
4.计算一个正整数的正平方根
5.说白了就是常见的那些查找、排序算法以及各自的时间复杂度
6.二叉树的遍历算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//二叉树节点
public class BinaryTreeNode {
    private int data;
    private BinaryTreeNode left;
    private BinaryTreeNode right;
    
    public BinaryTreeNode() {}

    public BinaryTreeNode(int data, BinaryTreeNode left, BinaryTreeNode right) {
        super();
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public BinaryTreeNode getLeft() {
        return left;
    }

    public void setLeft(BinaryTreeNode left) {
        this.left = left;
    }

    public BinaryTreeNode getRight() {
        return right;
    }

    public void setRight(BinaryTreeNode right) {
        this.right = right;
    }
}

前序递归遍历算法：访问根结点–>递归遍历根结点的左子树–>递归遍历根结点的右子树

中序递归遍历算法：递归遍历根结点的左子树–>访问根结点–>递归遍历根结点的右子树

后序递归遍历算法：递归遍历根结点的左子树–>递归遍历根结点的右子树–>访问根结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
import com.ccut.aaron.stack.LinkedStack;

public class BinaryTree {
    //前序遍历递归的方式
    public void preOrder(BinaryTreeNode root){
        if(null!=root){
            System.out.print(root.getData()+"\t");
            preOrder(root.getLeft());
            preOrder(root.getRight());
        }
    }
    
    //前序遍历非递归的方式
    public void preOrderNonRecursive(BinaryTreeNode root){
        Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>();
        while(true){
            while(root!=null){
                System.out.print(root.getData()+"\t");
                stack.push(root);
                root=root.getLeft();
            }
            if(stack.isEmpty()) break;
            root=stack.pop();
            root=root.getRight();
        }
    }
    
    //中序遍历采用递归的方式
    public void inOrder(BinaryTreeNode root){
        if(null!=root){
            inOrder(root.getLeft());
            System.out.print(root.getData()+"\t");
            inOrder(root.getRight());
        }
    }
    
    //中序遍历采用非递归的方式
    public void inOrderNonRecursive(BinaryTreeNode root){
        Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>();
        while(true){
            while(root!=null){
                stack.push(root);
                root=root.getLeft();
            }
            if(stack.isEmpty())break;
            root=stack.pop();
            System.out.print(root.getData()+"\t");
            root=root.getRight();
        }
    }
    
    //后序遍历采用递归的方式
    public void postOrder(BinaryTreeNode root){
        if(root!=null){
            postOrder(root.getLeft());
            postOrder(root.getRight());
            System.out.print(root.getData()+"\t");
        }
    }
    
    //后序遍历采用非递归的方式
    public void postOrderNonRecursive(BinaryTreeNode root){
        Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>();
        while(true){
            if(root!=null){
                stack.push(root);
                root=root.getLeft();
            }else{
                if(stack.isEmpty()) return;
                
                if(null==stack.lastElement().getRight()){
                    root=stack.pop();
                    System.out.print(root.getData()+"\t");
                    while(root==stack.lastElement().getRight()){
                        System.out.print(stack.lastElement().getData()+"\t");
                        root=stack.pop();
                        if(stack.isEmpty()){
                            break;
                        }
                    }
                }
                
                if(!stack.isEmpty())
                    root=stack.lastElement().getRight();
                else
                    root=null;
            }
        }
    }

    //层序遍历
    public void levelOrder(BinaryTreeNode root){
        BinaryTreeNode temp;
        Queue<BinaryTreeNode> queue=new LinkedList<BinaryTreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            temp=queue.poll();
            System.out.print(temp.getData()+"\t");
            if(null!=temp.getLeft()) 
                queue.offer(temp.getLeft());
            if(null!=temp.getRight()){
                queue.offer(temp.getRight());
            }
        }
    }
    
    public static void main(String[] args) {
        BinaryTreeNode node10=new BinaryTreeNode(10,null,null);
        BinaryTreeNode node8=new BinaryTreeNode(8,null,null);
        BinaryTreeNode node9=new BinaryTreeNode(9,null,node10);
        BinaryTreeNode node4=new BinaryTreeNode(4,null,null);
        BinaryTreeNode node5=new BinaryTreeNode(5,node8,node9);
        BinaryTreeNode node6=new BinaryTreeNode(6,null,null);
        BinaryTreeNode node7=new BinaryTreeNode(7,null,null);
        BinaryTreeNode node2=new BinaryTreeNode(2,node4,node5);
        BinaryTreeNode node3=new BinaryTreeNode(3,node6,node7);
        BinaryTreeNode node1=new BinaryTreeNode(1,node2,node3);
        
        BinaryTree tree=new BinaryTree();
        //采用递归的方式进行遍历
        System.out.println("-----前序遍历------");
        tree.preOrder(node1);
        System.out.println();
        //采用非递归的方式遍历
        tree.preOrderNonRecursive(node1);
        System.out.println();

        
        //采用递归的方式进行遍历
        System.out.println("-----中序遍历------");
        tree.inOrder(node1);
        System.out.println();
        //采用非递归的方式遍历
        tree.inOrderNonRecursive(node1);
        System.out.println();
        
        //采用递归的方式进行遍历
        System.out.println("-----后序遍历------");
        tree.postOrder(node1);
        System.out.println();
        //采用非递归的方式遍历
        tree.postOrderNonRecursive(node1);
        System.out.println();
        
        //采用递归的方式进行遍历
        System.out.println("-----层序遍历------");
        tree.levelOrder(node1);
        System.out.println();
    }
}
7.DFS,BFS算法

参考：https://blog.csdn.net/qq_40660894/article/details/88385180

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
import java.util.LinkedList;
import java.util.Queue;

public class Graph {
	private int v;	//顶点个数
	private LinkedList<Integer> adj[];	//存放边
	Graph(int v){
		this.v = v;
		adj = new LinkedList[v];
		for(int i=0; i<v; ++i) {
			adj[i] = new LinkedList<>();
		}
	}
	public void addEdge(int s, int t) {	//无向图一条边要存两次
		adj[s].add(t);
		adj[t].add(s);
	}
	//广度优先搜索
	public void bfs(int s, int t) {
		if(s == t)return;
		boolean[] visited = new boolean[v];	//存放已经访问过的节点
		visited[s] = true;
		Queue<Integer> queue = new LinkedList<>();	//存放已经访问过但相连节点还没有被访问过的节点
		queue.add(s);
		int[] prev = new int[v];			//记录搜素路径
		for(int i=0; i<v;i++) {
			prev[i] = -1;
		}
		while(queue.size() != 0) {
			int w =queue.poll();
			for(int i=0; i<adj[w].size();++i) {
				int q = adj[w].get(i);
				while(!visited[q]) {
					prev[q] = w;
					if(q == t) {
						print(prev,s,t);
						return;
					}
					visited[q] = true;
					queue.add(q);
				}
			}
		}
	}
	public void print(int[] prev, int s,int t) {	//递归打印s-->t的路径
		if(prev[t] != -1 && s != t) {
			print(prev,s,prev[t]);
		}
		System.out.print(t + " ");
	}
	boolean found = false;
	//深度优先搜索
	public void dfs(int s,int t) {
		found = false;
		boolean[] visited = new boolean[v];
		int[] prev = new int[v];
		for(int i=0;i<v;++i) {
			prev[i] = -1;
		}
		recurDfs(s,t,visited,prev);
		print(prev,s,t);
 	}
	public void recurDfs(int w, int t, boolean[] visited,int [] prev) {
		if(found == true)return;
		visited[w] = true;
		if(w == t) {
			found = true;
			return;
		}
		for(int i=0; i<adj[w].size();++i) {
			int q = adj[w].get(i);
			if(!visited[q]) {
				prev[q] = w;
				recurDfs(q,t,visited,prev);
			}
		}
	}
	public static void main(String[] args) {
		Graph graph = new Graph(8);
		graph.addEdge(0, 1);
		graph.addEdge(0, 3);
		graph.addEdge(1, 2);
		graph.addEdge(1, 4);
		graph.addEdge(3, 4);
		graph.addEdge(2, 5);
		graph.addEdge(4, 5);
		graph.addEdge(4, 6);
		graph.addEdge(5, 7);
		graph.addEdge(6, 7);
		graph.bfs(0, 6);
		System.out.println();
		graph.dfs(0, 7);
	}
}
8.比较重要的数据结构，如链表，队列，栈的基本理解及大致实现
9.排序算法与时空复杂度（快排为什么不稳定，为什么你的项目还在用）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

public class QuickSort {
    public static void quickSort(int[] arr,int low,int high){
        int i,j,temp,t;
        if(low>high){
            return;
        }
        i=low;
        j=high;
        //temp就是基准位
        temp = arr[low];
        while (i<j) {
            //先看右边，依次往左递减

            while (temp<=arr[j]&&i<j) {

                j--;
            }
            //再看左边，依次往右递增
            while (temp>=arr[i]&&i<j) {
               i++;
            }
            //如果满足条件则交换
            if (i<j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
        }
        //最后将基准为与i和j相等位置的数字交换
         arr[low] = arr[i];
         arr[i] = temp;
        //递归调用左半数组
        quickSort(arr, low, j-1);
        //递归调用右半数组
        quickSort(arr, j+1, high);
    }
    public static void main(String[] args)
    {
        int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
        quickSort(arr, 0, arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}
10.逆波兰计算器
1
2


11.Hoffman 编码

参考：https://blog.csdn.net/sinat_22828505/article/details/50364158

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
/*-------------------------------------------------------------------------
 * Name:   哈夫曼编码源
 * Date:   2015.12.20
 * Author: Ingrid 
 * 实现过程：
 *      //初始化huffmanTree,huffmanCode
 *      initHuffmanTree(huffmanTree,m);
 *      initHuffmanCode(huffmanCode,n);
 *      
 *      //获取huffmanCode的符号
 *      getHuffmanCode(huffmanCode,n);
 *
 *      //获取huffmanTree的频数
 *      getHuffmanWeight(huffmanTree,n);
 *      
 *      //创建huffmanTree
 *      createHaffmanTree(huffmanTree,n);
 *      //创建huffmanCode
 *      createHaffmanCode(huffmanTree,huffmanCode,n);
 *      
 *      //输出huffmanCode编码
 *      ouputHaffmanCode(huffmanCode,n);    
 *------------------------------------------------------------------------*/


import java.util.Scanner;
public class HuffmanCode{
    //建立数的节点类
    static class Node{
        int weight;//频数
        int parent;
        int leftChild;
        int rightChild;

        public Node(int weight,int parent,int leftChild,int rightChild){
            this.weight=weight;
            this.parent=parent;
            this.leftChild=leftChild;
            this.rightChild=rightChild;
        }

        void setWeight(int weight){
            this.weight=weight;
        }

        void setParent(int parent){
            this.parent=parent;
        }

        void setLeftChild(int leftChild){
            this.leftChild=leftChild;
        }

        void setRightChild(int rightChild){
            this.rightChild=rightChild;
        }

        int getWeight(){
            return weight;
        }

        int getParent(){
            return parent;
        }

        int getLeftChild(){
            return leftChild;
        }

        int getRightChild(){
            return rightChild;
        }
    }

    //新建哈夫曼编码
    static class NodeCode{
        String character;
        String code;
        NodeCode(String character,String code){
            this.character=character;
            this.code=code;
        }
        NodeCode(String code){
            this.code= code;
        }

        void setCharacter(String character){
            this.character=character;
        }

        void setCode(String code){
            this.code=code;
        }

        String getCharacter(){
            return character;
        }

        String getCode(){
            return code;
        }
    }

    //初始化一个huffuman树
    public static void initHuffmanTree(Node[] huffmanTree,int m){
        for(int i=0;i<m;i++){
            huffmanTree[i] = new Node(0,-1,-1,-1);
        }
    }

    //初始化一个huffmanCode
    public static void initHuffmanCode(NodeCode[] huffmanCode,int n){
        for(int i=0;i<n;i++){
            huffmanCode[i]=new NodeCode("","");
        }
    }

    //获取huffmanCode的符号
    public static void getHuffmanCode(NodeCode[] huffmanCode , int n){
        Scanner input = new Scanner(System.in);
        for(int i=0;i<n;i++){
            String temp = input.next();
            huffmanCode[i] = new NodeCode(temp,"");
        }
    }

    //获取huffman树节点频数
    public static void getHuffmanWeight(Node[] huffmanTree , int n){
        Scanner input = new Scanner(System.in);
        for(int i=0;i<n;i++){
            int temp = input.nextInt();
            huffmanTree[i] = new Node(temp,-1,-1,-1);
        }
    }

    //从n个结点中选取最小的两个结点
    public static int[] selectMin(Node[] huffmanTree ,int n)  
    {  
        int min[] = new int[2];
          class TempNode
           {  
                  int newWeight;//存储权  
                  int place;//存储该结点所在的位置  

                  TempNode(int newWeight,int place){
                      this.newWeight=newWeight;
                      this.place=place;
                  }

                  void setNewWeight(int newWeight){
                      this.newWeight=newWeight;
                  }

                  void setPlace(int place){
                      this.place=place;
                  }

                  int getNewWeight(){
                      return newWeight;
                  }

                  int getPlace(){
                      return place;
                  }
           } 

           TempNode[] tempTree=new TempNode[n];  

         //将huffmanTree中没有双亲的结点存储到tempTree中 
           int i=0,j=0;   
           for(i=0;i<n;i++)  
           {  
                  if(huffmanTree[i].getParent()==-1&& huffmanTree[i].getWeight()!=0)  
                  {  
                      tempTree[j]= new TempNode(huffmanTree[i].getWeight(),i);  
                      j++;  
                  }  
           } 

           int m1,m2;  
           m1=m2=0;  
           for(i=0;i<j;i++)  
           {  
                  if(tempTree[i].getNewWeight()<tempTree[m1].getNewWeight())//此处不让取到相等，是因为结点中有相同权值的时候，m1取最前的   
                         m1=i;  
           }  
           for(i=0;i<j;i++)  
           {  
                  if(m1==m2)  
                         m2++;//当m1在第一个位置的时候，m2向后移一位  
                  if(tempTree[i].getNewWeight()<=tempTree[m2].getNewWeight()&& i!=m1)//此处取到相等，是让在结点中有相同的权值的时候，  

                                       //m2取最后的那个。  
                         m2=i;  
           }  

           min[0]=tempTree[m1].getPlace();  
           min[1]=tempTree[m2].getPlace();  
       return min;
    }  

    //创建huffmanTree
    public static void createHaffmanTree(Node[] huffmanTree,int n){   
           if(n<=1)  
               System.out.println("Parameter Error!");  
           int m = 2*n-1; 
           //initHuffmanTree(huffmanTree,m);  

           for(int i=n;i<m;i++)  
           {      
               int[] min=selectMin(huffmanTree,i);
               int min1=min[0];
               int min2=min[1];
               huffmanTree[min1].setParent(i);  
               huffmanTree[min2].setParent(i);  
               huffmanTree[i].setLeftChild(min1);  
               huffmanTree[i].setRightChild(min2);
               huffmanTree[i].setWeight(huffmanTree[min1].getWeight()+ huffmanTree[min2].getWeight());   
           }  
    }

    //创建huffmanCode
    public static void createHaffmanCode(Node[] huffmanTree,NodeCode[] huffmanCode,int n){
        Scanner input = new Scanner(System.in);
        char[] code = new char[10]; 
        int start;
        int c;
        int parent;
        int temp;

        code[n-1]='0'; 
        for(int i=0;i<n;i++)  
           {
            StringBuffer stringBuffer = new StringBuffer();
            start=n-1;
            c=i;
            while( (parent=huffmanTree[c].getParent()) >=0 )  
                  {  
                         start--;  
                         code[start]=((huffmanTree[parent].getLeftChild()==c)?'0':'1');  
                         c=parent;  

                  } 
            for(;start<n-1;start++){
                 stringBuffer.append(code[start]);
            }
            huffmanCode[i].setCode(stringBuffer.toString());
           }
    }

    //输出hufmanCode
    public static void ouputHaffmanCode(NodeCode[] huffmanCode,int n){
        System.out.println("字符与编码的对应关系如下：");
        for(int i=0;i<n;i++){
            System.out.println(huffmanCode[i].getCharacter()+":"+huffmanCode[i].getCode());
        }
    }

    //主函数
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n;
        int m;
        System.out.print("请输入字符个数：");
        n = input.nextInt();
        m=2*n-1;
        Node[] huffmanTree = new Node[m];
        NodeCode[] huffmanCode = new NodeCode[n];

        //初始化huffmanTree,huffmanCode
        initHuffmanTree(huffmanTree,m);
        initHuffmanCode(huffmanCode,n);

        //获取huffmanCode的符号
        System.out.print("请输入哈夫曼编码的字符：");
        getHuffmanCode(huffmanCode,n);

        //获取huffmanTree的频数
        System.out.print("请输入哈夫曼编码字符对应的频数：");
        getHuffmanWeight(huffmanTree,n);

        //创建huffmanTree
        createHaffmanTree(huffmanTree,n);
        //创建huffmanCode
        createHaffmanCode(huffmanTree,huffmanCode,n);

        //输出huffmanCode编码
        ouputHaffmanCode(huffmanCode,n);

    }   
}
12.查找树与红黑树
1
2
3
4
5
6
7
8
9
10
二叉查找树：是由2节点的树组成的，最坏的时间复杂度是O(N)
树为空插入的节点作为根节点
插入的节点等于子树的值，则树不增加节点
插入的节点大于最终查询的子树则作为子树的右节点
插入的节点小于最终查询的子树则作为子树的左节点
红黑树
每个节点要么是红色，要么是黑色（2-3树节点要么是2节点要么是3节点）
根节点必须是黑色
红色节点不能连续（红色节点的子和父不能为红）（不能有4节点。注意2-3的4节点是临时的）
对于每个节点，从该点至null（树的尾端）的任何路径，都含有相同个数的黑色节点。