Java实现遍历、排序、查找算法及简要说明

will_132 贡献于2013-11-20

作者 kangjing  创建于2012-10-15 09:52:00   修改者kangjing  修改于2012-10-18 13:56:00字数7145

文档摘要:遍历算法(遍历二叉树6种方法)概述遍历算法针对二叉树而言的,主要有先序、中序、后序三种遍历顺序,三种顺序又分别有递归和常规算法,二叉树遍历的主要思想是:遍历左子树,遍历右子树,访问根节点,由这三者的遍历顺序来确定是先序、中序还是后序。下面只要求掌握递归遍历算法,常规遍历算法见附录一。先序遍历算法遍历顺序:访问根节点,遍历左子树,遍历右子树。
关键词:

1. 遍历算法(遍历二叉树6种方法) 1.1. 概述 遍历算法针对二叉树而言的,主要有先序、中序、后序三种遍历顺序,三种顺序又分别有递归和常规算法,二叉树遍历的主要思想是:遍历左子树,遍历右子树,访问根节点,由这三者的遍历顺序来确定是先序、中序还是后序。下面只要求掌握递归遍历算法,常规遍历算法见附录一。 1.2. 先序遍历算法 遍历顺序:访问根节点,遍历左子树,遍历右子树。代码如下: void preOrder(BinaryTreeNode bt) { if (bt == null)// 如果当前树为空,则终止递归 return; System.out.print(bt.getData());// 先访问根节点 preOrder(bt.getLeftChild());// 再遍历左子树 preOrder(bt.getRightChild());// 再遍历右子树 } 1.3. 中序遍历算法 遍历顺序:遍历左子树,访问根节点,遍历右子树。代码如下: void midOrder(BinaryTreeNode bt) { if (bt == null)// 如果当前树为空,则终止递归 return; preOrder(bt.getLeftChild());// 先遍历左子树 System.out.print(bt.getData());// 再访问根节点 preOrder(bt.getRightChild());// 再遍历右子树 } 1.4. 后序遍历算法 遍历顺序:遍历左子树,遍历右子树,访问根节点。代码如下: void postOrder(BinaryTreeNode bt) { if (bt == null)// 如果当前树为空,则终止递归 return; preOrder(bt.getLeftChild());// 先遍历左子树 preOrder(bt.getRightChild());// 再遍历右子树 System.out.print(bt.getData());// 再访问根节点 } 1.5. 层次遍历算法 void levelOrder(BinaryTreeNode bt) { if (bt == null) return; Queue q = new ArrayQueue(); q.enqueue(bt); while (!q.isEmpty()) { bt = (BinaryTreeNode) q.dequeue();// 取出队首元素,访问之 System.out.println(bt.getData()); if (bt.hasLeftChild()) { q.enqueue(bt.getLeftChild());// 如果左节点存在,放入队列中 } if (bt.hasRightChild()) { q.enqueue(bt.getRightChild());// 如果右节点存在,放入队列中 } } } 2. 排序算法(9种排序算法) 2.1. 概述 将一个数据元素的任意序列,重新排列成一个按关键字有序的序列。 2.2. 插入类排序 基本思想是:逐个考察每个待排序元素,将每一个新元素插入到前面已经排好序的序列中适当的位置上,使得新序列仍然是一个有序序列。主要介绍三种:直接插入排序、折半插入排序和希尔排序。 2.2.1. 直接插入排序 思路:仅有一个元素的序列总是有序的,因此,对 n 个记录的序列,可从第二个元素开始直到第 n 个元素,逐个向有序序列中执行插入操作,从而得到 n 个元素按关键字有序的序列。代码如下: void insert(int[] a) { for (int i = 1; i < a.length; i++) {// 从第二个开始比较插入 // 待插入的元素比之前排好序的元素最大值小才需要插入 if (a[i] < a[i - 1]) { int tmp = a[i];// 把当前位置腾出来 a[i] = a[i - 1];// 和已排好序的最大值交换顺序 int j = i - 2;// 遍历之前i-2个元素找出要插入的位置 // 如果待插入元素小于已排好序中的第j位并j不小于0则继续遍历 for (; j >= 0 && tmp < a[j]; j--) a[j + 1] = a[j]; a[j + 1] = tmp;// j + 1即为待插入位置 } } } 2.2.2. 折半插入排序 思路:可以不断二分有序序列来确定插入位置,即搜索插入位置的方法可以使用折半查找实现。代码如下: void binaryInsert(int[] a) { for (int i = 1; i < a.length; i++) {// 从第二个开始比较插入 // 待插入的元素比之前排好序的元素最大值小才需要插入 if (a[i] < a[i - 1]) { int tmp = a[i];// 把当前位置腾出来 a[i] = a[i - 1];// 和已排好序的最大值交换顺序 int low = 0, high = i - 1, mid;//high=已排好序列的长度 while (low < high) { mid = (low + high) / 2; if (tmp < a[mid]) high = mid - 1; else low = mid + 1; } int j = i - 2;// 遍历之前i-2个元素找出要插入的位置 // 取high是因为经过while循环后high一定是不大于low的 for (; j > high; j--) a[j + 1] = a[j]; a[high + 1] = tmp;// high + 1即为待插入位置 } } } 2.2.3. 希尔排序 思路:首先将待排序的元素分为多个子序列,使得每个子序列的元素个数相对较少,对各个子序列分 别进行直接插入排序,待整个待排序序列“基本有序”后,再对所有元素进行一次直接插入排序。 static void shell(int[] a) { int d = 1;// 定义步长值 while (d <= a.length / 3) d = d * 3 + 1;// 根据数组长度生成步长终值 for (; d > 0; d = (d - 1) / 3) {// 还原步长值 for (int i = d; i < a.length; i++) {// 从第1个步长开始比较插入 // 待插入的元素比之前排好序的元素最大值小才需要插入 if (a[i] < a[i - d]) { int tmp = a[i];// 把当前位置腾出来 a[i] = a[i - d];// 和已排好序的最大值交换顺序 int j = i - d - 1;// 遍历之前i-d-1个元素找出要插入的位置 // 如果待插入元素小于已排好序中的第j位并j不小于0则继续遍历 for (; j >= 0 && tmp < a[j]; j -= d) a[j + d] = a[j]; a[j + d] = tmp;// j + d即为待插入位置 } } } } 2.3. 交换类排序 2.3.1. 基本思想 交换类排序主要是通过两两比较待排元素的关键字,若发现与排序要求相逆,则“交换”之。 2.3.2. 冒泡排序 void bubble(int[] a) { for (int i = 0; i < a.length; i++) {// 先遍历数组 for (int j = 1; j < a.length - i; j++) {// 遍历未排好序的len-i个元素 if (a[j - 1] > a[j]) {// 前后比较 int tmp = a[j - 1]; a[j - 1] = a[j]; a[j] = tmp; } } } } 2.3.3. 快速排序 思路:划分步骤:通过枢轴元素 x 将序列一分为二, 且左子序列的元素均小于 x,右子序列的元素均大于 x;治理步骤:递归的对左、右子序列排序; 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 tar = a[low]; while (low < high) {// 循环该段数据 while (low < high && tar < a[high])// 先从高端开始查找 high--; a[low] = a[high];// 交换数据 while (low < high && tar > a[low])// 再从低端开始查找 low++; a[high] = a[low];// 交换数据 } a[low] = tar;// 重新设置枢轴 return low;// 返回枢轴位置 } 2.4. 选择类排序 2.4.1. 概述 每一趟从 n-i+1 (i=1,2,…,n)个元素中选取一个关键字最小的元素作为有序序列中第 i 个元素。 2.4.2. 简单选择排序 void recursionSort(int[] arr, int index) {// 递归选择排序 if (index < arr.length) { for (int i = 0; i < arr.length; i++) { if (arr[index] < arr[i]) { int tmp = arr[index]; arr[index] = arr[i]; arr[i] = tmp; } } index++; recursionSort(arr, index); } } void commonSort(int[] arr) {// 简单选择排序 for (int i = 0; i < arr.length; i++) { for (int j = i + 1; j < arr.length; j++) { if (arr[i] > arr[j]) { int tmp = arr[j]; arr[j] = arr[i]; arr[i] = tmp; } } } } 2.4.3. 树形选择排序和堆排序(附录二) 2.5. 并归排序排序 思想: 1. 划分:将待排序的序列划分为大小相等(或大致相等)的两个子序列; 2. 治理:当子序列的规模大于 1 时,递归排序子序列,如果子序列规模为 1 则成为有序序列; 3. 组合:将两个有序的子序列合并为一个有序序列。 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, high);//并归前半段 } } void merge(int[] a, int p, int q, int r) { int[] b = new int[r - p + 1]; int s = p;//并归a中p到q,q+1到r两个数组 int t = q + 1; int k = 0; while (s <= q && t <= r)//并归交叉段 if (a[s] < a[t]) b[k++] = a[s++]; else b[k++] = a[t++]; while (s <= q)//并归剩下的段 b[k++] = a[s++]; while (t <= r) b[k++] = a[t++]; for (int i = 0; i < b.length; i++) a[p + i] = b[i]; } 2.6. 各种排序之间的比较 3. 查找算法(3种查找算法) 3.1. 顺序查找 int order(int[] array, int tar) { for (int i = 0; i < array.length; i++) { if (tar == array[i]) return i + 1; } return -1; } 3.2. 折半查找 int binRecursion(int[] array, int tar, int low, int high) {// 二分法查找递归 int mid; if (low > high) return -1; mid = (high + low) / 2; if (tar == array[mid]) return mid + 1; else if (tar > array[mid]) binRecursion(array, tar, mid++, high); else binRecursion(array, tar, low, mid--); return -1; } int bin(int[] array, int tar) {// 二分法查找非递归 int low = 0, high = array.length - 1, mid; while (low <= high) { mid = (low + high) / 2; if (array[mid] == tar) return mid + 1; else if (array[mid] < tar) low = mid + 1; else high = mid - 1; } return -1; } 3.3. 二叉树查找 BinaryTreeNode binaryTreeRecusion(BinaryTreeNode bt, Object tar) {// 二叉树递归查找算法 if (bt == null) return new BinaryTreeNode("null"); switch (strategy.compare(tar, bt.getData())) { case -1:// tar比data小就查找左子树 return binaryTreeRecusion(bt.getLeftChild(), tar); case 1:// tar比data大就查找右子树 return binaryTreeRecusion(bt.getRightChild(), tar); default:// 比较结果是0,tar和data相等就返回 return bt; } } BinaryTreeNode binaryTree(BinaryTreeNode bt, Object tar) {// 二叉树非递归查找算法 while (bt != null) { switch (strategy.compare(tar, bt.getData())) { case -1:// tar比data小就查找左子树 return bt = bt.getLeftChild(); case 1:// tar比data大就查找右子树 return bt = bt.getRightChild(); default:// 比较结果是0,tar和data相等就返回 return bt; } } return new BinaryTreeNode("null"); } 4. 附录一 void preOrder(BinaryTreeNode p) {// 二叉树先序遍历非递归算法 Stack s = new SingleLinkedStack(); while (p != null) { while (p != null) { System.out.println(p.getData());// 访问根节点 if (p.hasRightChild()) {// 右子树压栈 s.push(p.getRightChild()); } p = p.getLeftChild();// 继续访问左子树直到为空 } if (!s.isEmpty()) { p = (BinaryTreeNode) s.pop();// 当当前左子树遍历完成,存右子树的栈退栈 } } } BinaryTreeNode goFarLeft(BinaryTreeNode bt, Stack s) {// 找到最左节点 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);// 找到最左节点 // 如果最左节点不为空则继续查找 while (p != null) { System.out.println(p.getData());// 访问根节点 if (p.hasRightChild()) { // 如果有右孩子节点,则访问有孩子节点的最左孩子节点 p = goFarLeft(p.getRightChild(), s); } else if (!s.isEmpty()) { // 如果没有右孩子节点且栈不为空,则弹栈往回找上一级 p = (BinaryTreeNode) s.pop(); } else p = null;// 栈为空则查找完成 } } void lastOrder(BinaryTreeNode p) {// 二叉树后序遍历非递归算法 Stack s = new SingleLinkedStack(); BinaryTreeNode pre = null;// 缓存上次访问节点 // 如果最左节点不为空则继续查找 while (p != null || !s.isEmpty()) { while (p != null) {// 查找最左节点 s.push(p); p = p.getLeftChild(); } if (!s.isEmpty()) { // 取出栈顶节点 p = (BinaryTreeNode) s.peek(); // 判断当前节点是否是父亲节点的右子节点,如果是 // 只需访问其父节点即可完成以p的父节点为根节点的子树的访问 if (!p.hasRightChild() || p.getRightChild() == pre) { list.insertLast(p); s.pop(); pre = p; p = null; } else p = p.getRightChild(); } } } 5. 附录二 堆排序: // 已知 r[low..high]中除 r[low]之外,其余元素均满足堆的定义 private void heapAdjust(int[] r, int low, int high) { int tmp = r[low]; for (int j = 2 * low; j <= high; j = j * 2) { // 沿关键之较大的元素向下进行筛选 if (j < high && r[j] > r[j + 1])// j 指向关键之较大的元素 j++; if (tmp >= r[j])// 若 temp 比其孩子都大,则插入到 low 所指位置 break; r[low] = r[j]; low = j; // 向下筛选 } r[low] = tmp; } public void heapSort(int[] r) { int n = r.length - 1; for (int i = n / 2; i >= 1; i--) // 初始化建堆 heapAdjust(r, i, n); for (int i = n; i > 1; i--) { // 不断输出堆顶元素并调整 r[1..i-1]为新堆 int tmp = r[1]; // 交换堆顶与堆底元素 r[1] = r[i]; r[i] = tmp; heapAdjust(r, 1, i - 1); // 调整 } }

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 5 金币 [ 分享文档获得金币 ] 2 人已下载

下载文档