tonglin0325的个人主页

Java数据结构——二叉树

tonglin0325

 

1.二叉树的遍历

前序遍历——根 左 右

中序遍历——左 根 右

后序遍历——左 右 根

 

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
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
292
293
294
295
296
297
298
299
300
301
302
class Stack_BinaryTree{
	private int maxSize;			//栈的长度
	private Node[] stackArray;		//创建栈的数组的引用
	private int top;			//创建栈顶的引用
	
	public Stack_BinaryTree(int s) {	//构造函数
		this.maxSize = s;
		stackArray = new Node[maxSize]; //创建对象
		top = -1;			//栈顶等于-1
	}
	
	public void push(Node j){		//入栈操作
		stackArray[++top] = j;		//先把top=-1自加成0,再入栈
	}
	
	public Node pop(){
		return stackArray[top--];	//弹出当前栈顶的元素后，再自减
	}
	
	public Node peek(){
		return stackArray[top];		//返回当前栈顶的元素
	}
	
	public boolean isEmpty(){	//栈顶为-1,即栈为空
		return (top == -1);
	}
	
	public boolean isFull(){	//栈顶为maxSize-1,即栈为满
		return (top == maxSize-1);
	}
	
}

class Node{
	int iData;
	double fData;
	Node leftChild;
	Node rightChild;
	
	public void display(){
		System.out.println('{');
		System.out.println(iData);
		System.out.println(',');
		System.out.println(fData);
		System.out.println('}');
	}
}

class Tree{
	public Node root;
	
	public Tree(){
		root = null;
	}
	
	public Node find(int key){		//查找关键字的节点
		Node current = root;
		while(current.iData != key){	//不等于就一直循环
			if(key<current.iData){
				current = current.leftChild;
			}else{
				current = current.rightChild;
			}
			if(current == null){
				return null;
			}
		}
		return current;	
	}
	
	public void insert(int id,double dd){	//插入新的节点
		Node newNode = new Node();
		newNode.iData = id;
		newNode.fData = dd;
		if(root == null){
			root = newNode;
		}else{
			Node current = root;
			Node parent;
			while(true){
				parent = current;
				if(newNode.iData<current.iData){	//如果插入的节点的数据小于当前节点的数据
					current = current.leftChild;
					if(current == null){
						parent.leftChild = newNode;	//把父亲节点的左孩子设为新节点
						return;
					}
				}else{		//如果插入的节点的数据大于当前节点的数据
					current = current.rightChild;
					if(current == null){
						parent.rightChild = newNode;	//把父亲节点的右孩子设为新节点
						return;
					}
				}
			}
		}
	}
	
	public void displayTree(){	//显示整个二叉树
		Stack_BinaryTree globalStack = new Stack_BinaryTree(128);	//用来放置每一层的二叉树
		globalStack.push(root);		//入栈
		int nBlanks = 32;
		boolean isRowEmpty = false;
		System.out.println(".............................................");
		while(isRowEmpty==false){
			Stack_BinaryTree localStack = new Stack_BinaryTree(128);	//用来放置下一层的二叉树
			isRowEmpty = true;
			for(int j=0;j<nBlanks;j++){
				System.out.print(' ');
			}
			
			while(globalStack.isEmpty()==false){			//当globalStack不为空，就一直出栈
				Node temp = (Node)globalStack.pop();		//temp等于globalStack出栈的节点
				if(temp!=null){
					System.out.print(temp.iData);		//当当前的节点不为空的时候，输出节点的值
					localStack.push(temp.leftChild);	//入栈globalStack的左孩子到下一层
					localStack.push(temp.rightChild);	//入栈globalStack的右孩子到下一层
					if(temp.leftChild != null || temp.rightChild != null){
						isRowEmpty = false;		//只要有一个子节点不为空，就把isRowEmpty置为false
					}
				}
				else{						//否则输出--，并把下一层置为空
					System.out.print("--");
					localStack.push(null);
					localStack.push(null);
				}
				for(int j=0;j<nBlanks*2-2;j++){
					System.out.print(' ');
				}
			}
			
			System.out.println();
			nBlanks /= 2;					//输出的空格数减半
			while(localStack.isEmpty() == false){
				globalStack.push(localStack.pop());	//还原本来的层
			}
		}
		System.out.println(".............................................");
	}
	
	public void preOrder(Node localRoot){		//前序遍历
		if(localRoot != null){
			System.out.print(localRoot.iData+" ");
			preOrder(localRoot.leftChild);
			preOrder(localRoot.rightChild);
		}
	}
	
	public void inOrder(Node localRoot){		//中序遍历
		if(localRoot != null){
			inOrder(localRoot.leftChild);
			System.out.print(localRoot.iData+" ");
			inOrder(localRoot.rightChild);
		}
	}
	
	public void postOrder(Node localRoot){		//后序遍历
		if(localRoot != null){
			postOrder(localRoot.leftChild);
			postOrder(localRoot.rightChild);
			System.out.print(localRoot.iData+" ");
		}
	}
	
	public Node minimum(){		//找到最小的节点
		Node current;
		Node last = null;
		current = root;
		while(current != null){
			last = current;
			current = current.leftChild;
		}
		return last;
	}
	
	public Node maxmum(){		//找到最大的节点
		Node current;
		Node last = null;
		current = root;
		while(current != null){
			last = current;
			current = current.rightChild;
		}
		return last;
	}
	
	public boolean delete(int key){
		Node current = root;
		Node parent = root;
		boolean isLeftChild = true;
		
		while(current.iData != key){//查找要删除的节点，并把其置为current，如果没有返回null
			parent = current;
			if(key<current.iData){
				current = current.leftChild;
				isLeftChild = true;			//当前current节点的parent节点有左孩子节点
			}else{
				current = current.rightChild;
				isLeftChild = false;			//当前current节点的parent节点没有左孩子节点
			}
			if(current == null){
				return false;
			}
		}
		//进入以下的时候，说明current已经匹配到要删除的节点
		//如果匹配的current节点没有孩子节点
		if(current.leftChild == null &amp;&amp; current.rightChild == null){
			if(current == root){		//如果这个节点就是根节点
				root = null;
			}else if(isLeftChild){
				parent.leftChild = null;		//父节点断开左孩子节点
			}else{
				parent.rightChild = null;	//父节点断开右孩子节点
			}
		}
		//如果current没有右孩子，则要把左子树上移
		else if(current.rightChild == null){	
			if(current == root){							//如果是根节点
				root = current.leftChild;
			}else if(isLeftChild){	//如果current节点是左孩子，则把current的左孩子放到parent的左孩子位置
				parent.leftChild = current.leftChild;
			}else{								//如果current节点是右孩子，则把current的左孩子放到parent的右孩子位置
				parent.rightChild = current.leftChild;
			}
		}
		//如果current没有左孩子，则要把右子树上移
		else if(current.leftChild == null){	
			if(current == root){							//如果是根节点
				root = current.rightChild;
			}else if(isLeftChild){	//如果current节点是左孩子，则把current的右孩子放到parent的左孩子位置
				parent.leftChild = current.rightChild;
			}else{								//如果current节点是右孩子，则把current的右孩子放到parent的右孩子位置
				parent.rightChild = current.rightChild;
			}
		}
		//如果current有左右孩子
		else{
			Node successor = getSuccessor(current);
			if(current == root){		//如果要删除的节点是根节点
				root = successor;
			}else if(isLeftChild){		//如果要删除的节点是左孩子
				parent.leftChild  = successor;
			}else{									//如果要删除的节点是右孩子
				parent.rightChild  = successor;
			}
			successor.leftChild = current.leftChild;//把最小的值的节点连接到要删除节点的左子树上
		}
		return true;
	}
	
	private Node getSuccessor(Node delNode){
		Node successorParent = delNode;
		Node successor = delNode;
		Node current = delNode.rightChild;
		while(current != null){							//循环，直到返回右子树中最小的值
			successorParent = successor;
			successor = current;
			current = current.leftChild;
		}
		if(successor != delNode.rightChild){
			successorParent.leftChild = successor.rightChild;	//把最小的值的右孩子放到该最小值的位置
			successor.rightChild = delNode.rightChild;				//把最小的值连接到要删除的节点的右子树上
		}
		return successor;
	}
		
}

public class BinaryTree {

	public static void main(String[] args) throws Exception{
		// TODO 自动生成的方法存根
		int value;
		Tree theTree = new Tree();
		theTree.insert(50, 1.5);
		theTree.insert(25, 1.4);
		theTree.insert(75, 1.3);
		theTree.insert(12, 1.6);
		theTree.insert(37, 1.7);
		//theTree.insert(43, 1.2);
		theTree.insert(60, 1.1);
		theTree.insert(85, 1.1);
		theTree.insert(77, 1.1);
		theTree.displayTree();
		
		System.out.println("查找节点的值："+theTree.find(77).iData);
		
		theTree.preOrder(theTree.root);
		System.out.println();
		theTree.inOrder(theTree.root);
		System.out.println();
		theTree.postOrder(theTree.root);
		System.out.println();
		System.out.println("最小的节点："+theTree.minimum().iData);
		System.out.println("最大的节点："+theTree.maxmum().iData);
		
		theTree.delete(75);
		theTree.displayTree();
	}

}

 

3.树、森林和二叉树之间的转换

树转换为二叉树

  1. 加线

     在所有兄弟结点之间加一条连线。

  1. 去线

    全文 >>

Java排序算法——快速排序

tonglin0325

输入是List

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
package com.interview.sort;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class QuickSort2 {        //输入是List<Integer>

    public static void main(String[] args) {
        // TODO 自动生成的方法存根
        List<Integer> list = new ArrayList<Integer>();
        list.add(-1);
        list.add(3);
        list.add(-0);
        list.add(-2);
        list.add(-7);
        list.add(-5);
        QuickSort2 qs = new QuickSort2();
        qs.quickSort(list);
        Iterator<Integer> i = list.iterator();
        while (i.hasNext()) {
            int num = (Integer) i.next();
            System.out.println(num);
        }

    }

    public void quickSort(List<Integer> list) {
        if (list.size() > 1) {
            List<Integer> smaller = new ArrayList<Integer>();
            List<Integer> same = new ArrayList<Integer>();
            List<Integer> larger = new ArrayList<Integer>();
            Integer mid = list.get(list.size() >> 1);
            for (Integer i : list) {
                if (i < mid) {
                    smaller.add(i);
                } else if (i > mid) {
                    larger.add(i);
                } else {
                    same.add(i);
                }
            }
            quickSort(smaller);
            quickSort(larger);
            list.clear();
            list.addAll(smaller);
            list.addAll(same);
            list.addAll(larger);
        }
    }

}

输入是Array

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
import java.util.Arrays;

class Arrays_Quick{
	private int[] arrays;
	private int curNum;

	public Arrays_Quick(int max) {			//建立一个max长度的空数组
		super();
		arrays = new int[max];
		curNum = 0;
	}
	
	public void insert(int value){					//往空的数组里面增加元素
		arrays[curNum] = value;
		curNum++;
	}
	
	public void display(){									//显示数组
		System.out.println(Arrays.toString(arrays));
	}
	
	public void QuickSort(){
		int i=0;
		int j=arrays.length-1;
		
		recQuickSort(i, j);
	}
	
	public void recQuickSort(int i,int j){
		// 结束条件
        if(i == j )
        	return;
         
        int key = arrays[i];
        int stepi = i; 			// 记录开始位置
        int stepj = j; 			// 记录结束位置
         
        while(j > i){
            // j <<-------------- 向前查找
            if(arrays[j] >= key){
                j--;
            }else{
                arrays[i] = arrays[j];
                //i++ ------------>>向后查找
                while(j > ++i){
                    if(arrays[i] > key){
                        arrays[j] = arrays[i];
                        break;
                    }
                }
            }
        }
         
        // 如果第一个取出的 key 是最小的数
        if(stepi == i){
        	recQuickSort(++i, stepj);
            return;
        }
         
        // 最后一个空位留给 key
        arrays[i] = key;
         
        // 递归
        recQuickSort(stepi, i);
        recQuickSort(j, stepj);
    }
}

public class QuickSort {

	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		int maxSize = 5;
		Arrays_Quick arrays_demo = new Arrays_Quick(maxSize);
		arrays_demo.insert(4);
		arrays_demo.insert(5);
		arrays_demo.insert(3);
		arrays_demo.insert(1);
		arrays_demo.insert(2);
		arrays_demo.display();
		arrays_demo.QuickSort();
		arrays_demo.display();
	}

}

 

Java排序算法——归并排序

tonglin0325

 

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
import java.util.Arrays;

class Arrays_Merge{
    private int[] arrays;
    private int curNum;
    //int[] workSpace;
 
    public Arrays_Merge(int max) {         //建立一个max长度的空数组
        super();
        arrays = new int[max];
        curNum = 0;
    }
     
    public void insert(int value){                  //往空的数组里面增加元素
        arrays[curNum] = value;
        curNum++;
    }
     
    public void display(){                                  //显示数组
        System.out.println(Arrays.toString(arrays));
    }
    
    public void mergeSort(){
    	int[] arrays = new int[curNum];
    	recMergeSort(arrays, 0, curNum-1);
    }
    
    public void recMergeSort(int[] workSpace,int lowerBound,int upperBound){
    	if(lowerBound == upperBound)
    		return;
    	else
    	{
    		int mid = (lowerBound+upperBound)/2;
    		recMergeSort(workSpace,lowerBound,mid);
    		recMergeSort(workSpace,mid+1,upperBound);
    		merge(workSpace,lowerBound,mid+1,upperBound);
    		System.out.println("mid="+mid);
    	}
    }
     
    public void merge(int[] workSpace,int lowPtr,int highPtr,int upperBound){
    	int j=0;
    	int lowerBound = lowPtr;
    	int mid = highPtr-1;
    	int n = upperBound-lowerBound+1;
    	
    	while(lowPtr<=mid &amp;&amp; highPtr<=upperBound){
    		if(arrays[lowPtr]<arrays[highPtr]){			//如果后面的小，就先放进新的数组中
    			workSpace[j++] = arrays[lowPtr++];		//如果运行第一行，就运行下面的第二个
    			System.out.println("1lowPtr="+(lowPtr-1)+" "+workSpace[j-1]);
    		}else{
    			workSpace[j++] = arrays[highPtr++];	//如果运行第二行，就运行下面的第一个
    			System.out.println("1highPtr="+(highPtr-1)+" "+(j-1)+"="+workSpace[j-1]);
    		}
    	}
    	
    	while(lowPtr<=mid){						//以下两个只可能运行一个
    		workSpace[j++] = arrays[lowPtr++]; 
    		System.out.println("lowPtr="+(lowPtr-1)+" "+workSpace[j-1]);
    	}
    	
    	while(highPtr<=upperBound){
    		workSpace[j++] = arrays[highPtr++];
    		System.out.println("highPtr="+(highPtr-1)+" "+workSpace[j-1]);
    	}
    	
    	for(j=0;j<n;j++){
    		arrays[lowerBound+j] = workSpace[j];
    	}
    }
}

public class MergeSort {

	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		int maxSize=10;
		Arrays_Merge arr;
		arr = new Arrays_Merge(maxSize);
		arr.insert(9);
		arr.insert(8);
		arr.insert(7);
		arr.insert(6);
		arr.insert(5);
		arr.insert(4);
		arr.insert(3);
		arr.insert(2);
		arr.insert(1);
		arr.display();
		arr.mergeSort();
		arr.display();
	}

}

 

Java递归算法——二分查找

tonglin0325
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
import java.lang.reflect.Array;
import java.nio.Buffer;
import java.util.Arrays;
import java.util.Random;

class Rec_Find{
	private int[] temp;
	private int searchKey;
	//private int lowerBound = 0;			//下界
	//private int upperBound ;				//上界
	private int nElement;
	
	public int[] getTemp() {
		return temp;
	}

	public void setTemp(int[] temp) {
		this.temp = temp;
	}

	public Rec_Find(int[] temp) {//构造函数
		this.temp = temp;
		//this.upperBound = temp.length-1;
	}

	public int find(int searchKey,int lowerBound,int upperBound){
			int curNum;
			this.searchKey = searchKey;
			curNum = (lowerBound+upperBound)/2;
			if(temp[curNum]==this.searchKey){
				return curNum;							//find
			}
			else if(lowerBound>upperBound){
				return -1;										//没有find
			}
			else{
				if(temp[curNum]<this.searchKey){
					return find(searchKey,curNum+1,upperBound);
				}
				else{
					return find(searchKey,lowerBound,curNum-1);
				}
			}
	}	
}

class RandomArray{					//生成随机数组，有Num个
	
	private int[] Arrays;
	
	public int[] getArrays(int Num){
//		int[] Arrays = new int[Num];
		Arrays = new int[Num];
		Random r = new Random();
		
		for(int i=0;i<Num;i++){
			Arrays[i] = r.nextInt(1000);
//			System.out.print(Arrays[i]+"、");
		}
		return Arrays;
	}
}

class OrderedArray{			//生成有序数组，从0开始到Num
	
	public int[] getArrays(int Num){
		int[] Arrays = new int[Num];
		
		for(int i=0;i<Num;i++){
			Arrays[i] = i;
//			System.out.print(Arrays[i]+"、");
		}
		return Arrays;
	}
}

public class RecFind {
	
	public static void main(String[] args) {

//		RandomArrays array_demo = new RandomArrays();
//		BinarySearch_Find arrays = new BinarySearch_Find(array_demo.getArrays(100));
		
		OrderedArray array_demo = new OrderedArray();
		Rec_Find arrays = new Rec_Find(array_demo.getArrays(100));
		System.out.println(Arrays.toString(arrays.getTemp()));
		System.out.println(arrays.find(55,0,100));
	}
}

 

Java递归算法——汉诺塔问题

tonglin0325
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Tower_demo {
	
	static int nDisks = 3;
	
	public static void main(String[] args) {
		doTower(nDisks, 'A', 'B', 'C');
	}

	public static void doTower(int topN,char from,char inter,char to){
		if(topN == 1)
			System.out.println("Disk 1 from "+from+" to "+to);
		else{
			doTower(topN-1, from, to, inter);
			System.out.println("Disk "+topN+" from "+from+" to "+to);
			doTower(topN-1, inter, from, to);
		}
	}
	
}

 

通过二叉树的中序遍历过程来分析汉诺塔问题：

考虑A、B、C三根柱子，A上从上到下有1、2、3三个数，要把A上的数移动到C上，其过程应该是

**　　　　  A　　B　　C**

初始　　123

A->C　  23　　　　 1

A->B　  3　　2　　 1

C->B　  3　  12　　

A->C　  　　 12　　3

B->A　  1　　2　　 3

B->C　  1　　　　  23

A->C　    　　　　 123

 

可以写成下图二叉树的中序遍历

在程序中有两个输出语句，

结束条件中的数据语句输出的是二叉树中的叶子结点

递归左子树和递归右子树中间的输出语句输出是所有的非叶子结点

所有左孩子和右孩子输出语句中得到的实际参数都是其父结点传递的，根节点输出语句得到的参数是初始传递的参数

 

全文 >>

Java递归算法——变位字

tonglin0325

轮换的含义

1.c ats –> 2.ca st

3.c tsa –> 4.ct as

5.c sat –> 6.cs ta

  1. atsc

 

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Anagram_demo {
	
	static int Size;
	static int count=0;
	static char[] arrChar = new char[100];
	
	public static void main(String[] args) throws Exception{
		// TODO 自动生成的方法存根
		System.out.println("请输入一个单词：");
		String input = getString();
		Size = input.length();
		for(int i=0;i<Size;i++){
			arrChar[i] = input.charAt(i);
		}
		doAnagram(Size);
	}
	
	public static void doAnagram(int newSize){
		if(newSize == 1)		//只有一个就不做任何处理
			return;
		for(int i=0;i<newSize;i++){
			doAnagram(newSize - 1);
			if(newSize == 2){
				displayWord();
			}
			rorate(newSize);
		}
	}
	
	public static void displayWord(){
		System.out.print(++count);
		for(int i=0;i<Size;i++){
			System.out.print(arrChar[i]);
		}
		System.out.println("、");
	}
	
	public static void rorate(int newSize){		//轮换函数
		
		int position = Size - newSize;
		char temp = arrChar[position];
		for(int i=position;i<Size-1;i++){
			arrChar[i] = arrChar[i+1];
		}
		arrChar[Size-1] = temp;
	}
	
	//输出方法
			public static String getString() throws IOException{
				InputStreamReader isr = new InputStreamReader(System.in);
				BufferedReader br = new BufferedReader(isr);
				String s = br.readLine();
				return s;
			}
			
			//输出方法
			public static int getInt() throws IOException{
				String s = getString();
				return Integer.parseInt(s);
				
			}
}

 

全文 >>

Java递归算法——阶乘

tonglin0325
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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;

public class Factorial_demo {

	public static void main(String[] args) throws Exception{
		// TODO 自动生成的方法存根
		System.out.println("输入数字：");
		int theNumber = getInt();
		int theAnswer = factorial(theNumber); 
		System.out.println("阶乘："+theAnswer);
	}
	
	public static int factorial(int n){		//递归
		if(n == 1)
			return 1;
		else
			return (n*factorial(n-1));
	}
	
	//输出方法
		public static String getString() throws IOException{
			InputStreamReader isr = new InputStreamReader(System.in);
			BufferedReader br = new BufferedReader(isr);
			String s = br.readLine();
			return s;
		}
		
		//输出方法
		public static int getInt() throws IOException{
			String s = getString();
			return Integer.parseInt(s);
		}
}

 

Java递归算法——三角数字（递归和非递归）

tonglin0325

 1.递归法#

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;

public class triangle_demo {
	
	//static int theNumber;
	
	public static void main(String[] args) throws Exception{
		// TODO 自动生成的方法存根
		System.out.println("输入数字：");
		int theNumber = getInt();
		int theAnswer = triangle(theNumber); 
		System.out.println("三角上每一行的数量："+theAnswer);
	}
	
	public static int triangle(int n){		//递归输出1 3 6 10....
		if(n==1)
			return 1;
		else
			return (n + triangle(n-1));
	}
	
	
	//输出方法
	public static String getString() throws IOException{
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(isr);
		String s = br.readLine();
		return s;
	}
	
	//输出方法
	public static int getInt() throws IOException{
		String s = getString();
		return Integer.parseInt(s);
		
	}

}

 

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
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
import java.io.*;                 // for I/O

class Params     //这个类的对象被压入栈中
   {
   public int n;							//用来存放键盘输入的数字
   public int returnAddress;	//返回的地址

   public Params(int nn, int ra)
      {
      n=nn;
      returnAddress=ra;
      }
   }  // end class Params

class StackX
   {
   private int maxSize;         // size of StackX array
   private Params[] stackArray;
   private int top;             // top of stack
//--------------------------------------------------------------
   public StackX(int s)         // constructor
      {
      maxSize = s;              // set array size
      stackArray = new Params[maxSize];  // create array
      top = -1;                 // no items yet
      }
//--------------------------------------------------------------
   public void push(Params p)   // put item on top of stack
      {
      stackArray[++top] = p;    // increment top, insert item
      }
//--------------------------------------------------------------
   public Params pop()          // take item from top of stack
      {
      return stackArray[top--]; // access item, decrement top
      }
//--------------------------------------------------------------
   public Params peek()         // peek at top of stack
      {
      return stackArray[top];
      }
//--------------------------------------------------------------
   }  // end class StackX

class stackTriangle
   {
   static int theNumber;		//用于接收输入的int
   static int theAnswer;
   static StackX theStack;
   static int codePart;				//用于switch选择
   static Params theseParams;

   public static void main(String[] args) throws IOException
      {
      System.out.print("Enter a number: ");
      theNumber = getInt();		//接收键盘输入的int
      recTriangle();
      System.out.println("Triangle="+theAnswer);
      }  // end main()

   public static void recTriangle()
      {
      theStack = new StackX(10000);
      codePart = 1;
      while( step() == false)  // call step() until it's true
         ;                     // null statement
      }
//-------------------------------------------------------------
   public static boolean step()
      {
      switch(codePart)
         {
         case 1:                              // initial call
        	 System.out.println("进入1");
            theseParams = new Params(theNumber, 6);	
            theStack.push(theseParams);
            codePart = 2;
            break;
            
         case 2:                              // method entry
        	 System.out.println("进入2");
            theseParams = theStack.peek();	//对输入的数字一直减1，直到等于1，如果大于1就跳到3中，压入栈中
            if(theseParams.n == 1)            		// n是键盘输入的数字，如果是1，结果是1，codePart跳到5
               {
               theAnswer = 1;
               codePart = 5;   // exit
               }
            else														//如果大于1，就跳到3
               codePart = 3;   // recursive call
            break;
            
         case 3:                              
        	 System.out.println("进入3");
            Params newParams = new Params(theseParams.n - 1, 4);
            theStack.push(newParams);			//把输入的数字减去1，并压入栈中
            codePart = 2;  										//回到2中判断数组减去1后，是否等于1
            break;
            
         case 4:                              // calculation
        	 System.out.println("进入4");
            theseParams = theStack.peek();			//取得2
            theAnswer = theAnswer + theseParams.n;	//1+2
            codePart = 5;
            break;
            
         case 5:                              // method exit
        	 System.out.println("进入5");
            theseParams = theStack.peek();
            codePart = theseParams.returnAddress; //在2和3中交替跳转后，结束时跳到5，此时栈中codePart除了栈底是6，其他都是4
            theStack.pop();				//在取得了下次跳转的位置后，出栈，第一次出栈的是（1,4）
            break;
            
         case 6:                              // return point
        	 System.out.println("进入6");
            return true;
         }  // end switch
      return false;
      }  // end triangle

   public static String getString() throws IOException
      {
      InputStreamReader isr = new InputStreamReader(System.in);
      BufferedReader br = new BufferedReader(isr);
      String s = br.readLine();
      return s;
      }

   public static int getInt() throws IOException
      {
      String s = getString();
      return Integer.parseInt(s);
      }

   }

 

tonglin0325

标签

标签云

AWS Airbnb Android CDH Doris ELK Flink Git Grafana HAProxy HBase Hadoop Hive Hudi InfluxDB JDBC JMeter JVM Java LaTex Linkedin Linux ML ML Infra MPP Maven MySQL Nexus OpenTSDB Paper Play Prometheus Python React Redis RocksDB Scala Solr Spark SpringBoot SpringMVC Thrift YARN antlr arthas avro cassandra clickhouse confluent docker filebeat flume golang google gradle hexo impala jenkins k8s kafka kerberos kudu ldap mac mongo mybatis nginx nlp open-falcon openwrt parquet presto ranger rocketmq scyllaDB twitter zookeeper 刷题 前端 图存储及计算 多线程 广告系统 开发工具 数据结构 杂谈 算法 系统设计 计算机基础 设计模式

文章归档

最近文章