Java實(shí)現(xiàn)遍歷、排序、查找算法及簡(jiǎn)要說明(共11頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上1. 遍歷算法（遍歷二叉樹6種方法）1.1. 概述遍歷算法針對(duì)二叉樹而言的，主要有先序、中序、后序三種遍歷順序，三種順序又分別有遞歸和常規(guī)算法，二叉樹遍歷的主要思想是：遍歷左子樹，遍歷右子樹，訪問根節(jié)點(diǎn)，由這三者的遍歷順序來確定是先序、中序還是后序。下面只要求掌握遞歸遍歷算法，常規(guī)遍歷算法見附錄一。1.2. 先序遍歷算法遍歷順序：訪問根節(jié)點(diǎn)，遍歷左子樹，遍歷右子樹。代碼如下：void preOrder(BinaryTreeNode bt) if (bt = null)/ 如果當(dāng)前樹為空，則終止遞歸return;System.out.print(bt.getData()

2、;/ 先訪問根節(jié)點(diǎn)preOrder(bt.getLeftChild();/ 再遍歷左子樹preOrder(bt.getRightChild();/ 再遍歷右子樹1.3. 中序遍歷算法遍歷順序：遍歷左子樹，訪問根節(jié)點(diǎn)，遍歷右子樹。代碼如下：void midOrder(BinaryTreeNode bt) if (bt = null)/ 如果當(dāng)前樹為空，則終止遞歸return;preOrder(bt.getLeftChild();/ 先遍歷左子樹System.out.print(bt.getData();/ 再訪問根節(jié)點(diǎn)preOrder(bt.getRightChild();/ 再遍歷右子樹1.4

3、. 后序遍歷算法遍歷順序：遍歷左子樹，遍歷右子樹，訪問根節(jié)點(diǎn)。代碼如下：void postOrder(BinaryTreeNode bt) if (bt = null)/ 如果當(dāng)前樹為空，則終止遞歸return;preOrder(bt.getLeftChild();/ 先遍歷左子樹preOrder(bt.getRightChild();/ 再遍歷右子樹System.out.print(bt.getData();/ 再訪問根節(jié)點(diǎn)1.5. 層次遍歷算法void levelOrder(BinaryTreeNode bt) if (bt = null)return;Queue q = new Arra

4、yQueue();q.enqueue(bt);while (!q.isEmpty() bt = (BinaryTreeNode) q.dequeue();/ 取出隊(duì)首元素，訪問之System.out.println(bt.getData();if (bt.hasLeftChild() q.enqueue(bt.getLeftChild();/ 如果左節(jié)點(diǎn)存在，放入隊(duì)列中if (bt.hasRightChild() q.enqueue(bt.getRightChild();/ 如果右節(jié)點(diǎn)存在，放入隊(duì)列中2. 排序算法（9種排序算法）2.1. 概述將一個(gè)數(shù)據(jù)元素的任意序列，重新排列成一個(gè)按關(guān)鍵字有

5、序的序列。2.2. 插入類排序基本思想是：逐個(gè)考察每個(gè)待排序元素，將每一個(gè)新元素插入到前面已經(jīng)排好序的序列中適當(dāng)?shù)奈恢蒙?，使得新序列仍然是一個(gè)有序序列。主要介紹三種：直接插入排序、折半插入排序和希爾排序。2.2.1. 直接插入排序思路：僅有一個(gè)元素的序列總是有序的，因此，對(duì) n 個(gè)記錄的序列，可從第二個(gè)元素開始直到第 n 個(gè)元素，逐個(gè)向有序序列中執(zhí)行插入操作，從而得到 n 個(gè)元素按關(guān)鍵字有序的序列。代碼如下：void insert(int a) for (int i = 1; i a.length; i+) / 從第二個(gè)開始比較插入/ 待插入的元素比之前排好序的元素最大值小才需要插入if (a

6、i = 0 & tmp aj; j-)aj + 1 = aj;aj + 1 = tmp;/ j + 1即為待插入位置2.2.2. 折半插入排序思路：可以不斷二分有序序列來確定插入位置，即搜索插入位置的方法可以使用折半查找實(shí)現(xiàn)。代碼如下：void binaryInsert(int a) for (int i = 1; i a.length; i+) / 從第二個(gè)開始比較插入/ 待插入的元素比之前排好序的元素最大值小才需要插入if (ai ai - 1) int tmp = ai;/ 把當(dāng)前位置騰出來ai = ai - 1;/ 和已排好序的最大值交換順序int low = 0, high = i

7、- 1, mid;/high=已排好序列的長度while (low high) mid = (low + high) / 2;if (tmp high; j-)aj + 1 = aj;ahigh + 1 = tmp;/ high + 1即為待插入位置2.2.3. 希爾排序思路：首先將待排序的元素分為多個(gè)子序列，使得每個(gè)子序列的元素個(gè)數(shù)相對(duì)較少，對(duì)各個(gè)子序列分別進(jìn)行直接插入排序，待整個(gè)待排序序列“基本有序”后，再對(duì)所有元素進(jìn)行一次直接插入排序。static void shell(int a) int d = 1;/ 定義步長值while (d 0; d = (d - 1) / 3) / 還原步長

8、值for (int i = d; i a.length; i+) / 從第1個(gè)步長開始比較插入/ 待插入的元素比之前排好序的元素最大值小才需要插入if (ai = 0 & tmp aj; j -= d)aj + d = aj;aj + d = tmp;/ j + d即為待插入位置2.3. 交換類排序2.3.1. 基本思想交換類排序主要是通過兩兩比較待排元素的關(guān)鍵字，若發(fā)現(xiàn)與排序要求相逆，則“交換”之。2.3.2. 冒泡排序void bubble(int a) for (int i = 0; i a.length; i+) / 先遍歷數(shù)組for (int j = 1; j aj) / 前后比較i

9、nt tmp = aj - 1;aj - 1 = aj;aj = tmp;2.3.3. 快速排序思路：劃分步驟：通過樞軸元素 x 將序列一分為二， 且左子序列的元素均小于 x，右子序列的元素均大于 x；治理步驟：遞歸的對(duì)左、右子序列排序；void quick(int a, int low, int high) if (low high) int part = partition(a, low, high);quick(a, low, part - 1);quick(a, part + 1, high);int partition(int a, int low, int high) int ta

10、r = alow;while (low high) / 循環(huán)該段數(shù)據(jù)while (low high & tar ahigh)/ 先從高端開始查找high-;alow = ahigh;/ 交換數(shù)據(jù)while (low alow)/ 再從低端開始查找low+;ahigh = alow;/ 交換數(shù)據(jù)alow = tar;/ 重新設(shè)置樞軸return low;/ 返回樞軸位置2.4. 選擇類排序2.4.1. 概述每一趟從 n-i+1 (i=1,2,n)個(gè)元素中選取一個(gè)關(guān)鍵字最小的元素作為有序序列中第 i 個(gè)元素。2.4.2. 簡(jiǎn)單選擇排序void recursionSort(int arr, int

11、index) / 遞歸選擇排序if (index arr.length) for (int i = 0; i arr.length; i+) if (arrindex arri) int tmp = arrindex;arrindex = arri;arri = tmp;index+;recursionSort(arr, index);void commonSort(int arr) / 簡(jiǎn)單選擇排序for (int i = 0; i arr.length; i+) for (int j = i + 1; j arrj) int tmp = arrj;arrj = arri;arri = tm

12、p;2.4.3. 樹形選擇排序和堆排序（附錄二）2.5. 并歸排序排序思想：1. 劃分：將待排序的序列劃分為大小相等（或大致相等）的兩個(gè)子序列；2. 治理：當(dāng)子序列的規(guī)模大于 1 時(shí)，遞歸排序子序列，如果子序列規(guī)模為 1 則成為有序序列；3. 組合：將兩個(gè)有序的子序列合并為一個(gè)有序序列。void msort(int a, int low, int high) if (low high) msort(a, low, (high + low) / 2);msort(a, (high + low) / 2 + 1, high);/并歸后半段merge(a, low, (high + low) / 2

13、, high);/并歸前半段void merge(int a, int p, int q, int r) int b = new intr - p + 1;int s = p;/并歸a中p到q，q+1到r兩個(gè)數(shù)組int t = q + 1;int k = 0;while (s = q & t = r)/并歸交叉段if (as at)bk+ = as+;elsebk+ = at+;while (s = q)/并歸剩下的段bk+ = as+;while (t = r)bk+ = at+;for (int i = 0; i b.length; i+)ap + i = bi;2.6. 各種排序之間的比

14、較3. 查找算法（3種查找算法）3.1. 順序查找int order(int array, int tar) for (int i = 0; i high)return -1;mid = (high + low) / 2;if (tar = arraymid)return mid + 1;else if (tar arraymid)binRecursion(array, tar, mid+, high);elsebinRecursion(array, tar, low, mid-);return -1;int bin(int array, int tar) / 二分法查找非遞歸int low

15、= 0, high = array.length - 1, mid;while (low = high) mid = (low + high) / 2;if (arraymid = tar)return mid + 1;else if (arraymid tar)low = mid + 1;elsehigh = mid - 1;return -1;3.3. 二叉樹查找BinaryTreeNode binaryTreeRecusion(BinaryTreeNode bt, Object tar) / 二叉樹遞歸查找算法if (bt = null)return new BinaryTreeNode

16、(null);switch (pare(tar, bt.getData() case -1:/ tar比data小就查找左子樹return binaryTreeRecusion(bt.getLeftChild(), tar);case 1:/ tar比data大就查找右子樹return binaryTreeRecusion(bt.getRightChild(), tar);default:/ 比較結(jié)果是0，tar和data相等就返回return bt;BinaryTreeNode binaryTree(BinaryTreeNode bt, Object tar) / 二叉樹非遞歸查找算法whi

17、le (bt != null) switch (pare(tar, bt.getData() case -1:/ tar比data小就查找左子樹return bt = bt.getLeftChild();case 1:/ tar比data大就查找右子樹return bt = bt.getRightChild();default:/ 比較結(jié)果是0，tar和data相等就返回return bt;return new BinaryTreeNode(null);4. 附錄一void preOrder(BinaryTreeNode p) / 二叉樹先序遍歷非遞歸算法Stack s = new Singl

18、eLinkedStack();while (p != null) while (p != null) System.out.println(p.getData();/ 訪問根節(jié)點(diǎn)if (p.hasRightChild() / 右子樹壓棧s.push(p.getRightChild();p = p.getLeftChild();/ 繼續(xù)訪問左子樹直到為空if (!s.isEmpty() p = (BinaryTreeNode) s.pop();/ 當(dāng)當(dāng)前左子樹遍歷完成，存右子樹的棧退棧BinaryTreeNode goFarLeft(BinaryTreeNode bt, Stack s) / 找

19、到最左節(jié)點(diǎn)if (bt = null)return null;while (bt.hasLeftChild() s.push(bt);bt = bt.getLeftChild();return bt;void midOrder(BinaryTreeNode bt) / 二叉樹中序遍歷的非遞歸算法Stack s = new SingleLinkedStack();BinaryTreeNode p = goFarLeft(bt, s);/ 找到最左節(jié)點(diǎn)/ 如果最左節(jié)點(diǎn)不為空則繼續(xù)查找while (p != null) System.out.println(p.getData();/ 訪問根節(jié)點(diǎn)if

20、 (p.hasRightChild() / 如果有右孩子節(jié)點(diǎn)，則訪問有孩子節(jié)點(diǎn)的最左孩子節(jié)點(diǎn)p = goFarLeft(p.getRightChild(), s); else if (!s.isEmpty() / 如果沒有右孩子節(jié)點(diǎn)且棧不為空，則彈棧往回找上一級(jí)p = (BinaryTreeNode) s.pop(); elsep = null;/ 棧為空則查找完成void lastOrder(BinaryTreeNode p) / 二叉樹后序遍歷非遞歸算法Stack s = new SingleLinkedStack();BinaryTreeNode pre = null;/ 緩存上次訪問節(jié)點(diǎn)/ 如果最左節(jié)點(diǎn)不為空則繼續(xù)查找while (p != null | !s.isEmpty() while (p != null) / 查找最左節(jié)點(diǎn)s.push(p);p = p.getLeftChild();if (!s.isEmpty() / 取出棧頂節(jié)點(diǎn)p = (BinaryTreeNode) s.peek();/ 判斷當(dāng)前節(jié)