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

《java实现遍历、排序、查找算法及简要说明》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、1.遍历算法（遍历二叉树6种方法）1.1.概述遍历算法针对二叉树而言的，主要有先序、中序、后序三种遍历顺序，三种顺序又分别有递归和常规算法，二叉树遍历的主要思想是：遍历左子树，遍历右子树，访问根节点，由这三者的遍历顺序来确定是先序、中序还是后序。下面只要求掌握递归遍历算法，常规遍历算法见附录一。1.2.先序遍历算法遍历顺序：访问根节点，遍历左子树，遍历右子树。代码如下：voidpreOrder(BinaryTreeNodebt){if(bt==null)//如果当前树为空，则终止递归return;System.out.print(bt.g

2、etData());//先访问根节点preOrder(bt.getLeftChild());//再遍历左子树preOrder(bt.getRightChild());//再遍历右子树}1.3.中序遍历算法遍历顺序：遍历左子树，访问根节点，遍历右子树。代码如下：voidmidOrder(BinaryTreeNodebt){if(bt==null)//如果当前树为空，则终止递归return;preOrder(bt.getLeftChild());//先遍历左子树System.out.print(bt.getData());//再访问根节点pr

3、eOrder(bt.getRightChild());//再遍历右子树}1.4.后序遍历算法遍历顺序：遍历左子树，遍历右子树，访问根节点。代码如下：voidpostOrder(BinaryTreeNodebt){if(bt==null)//如果当前树为空，则终止递归return;preOrder(bt.getLeftChild());//先遍历左子树preOrder(bt.getRightChild());//再遍历右子树System.out.print(bt.getData());//再访问根节点}1.5.层次遍历算法voidlevel

4、Order(BinaryTreeNodebt){if(bt==null)return;Queueq=newArrayQueue();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.enqu

5、eue(bt.getRightChild());//如果右节点存在，放入队列中}}}1.排序算法（9种排序算法）1.1.概述将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。1.2.插入类排序基本思想是：逐个考察每个待排序元素，将每一个新元素插入到前面已经排好序的序列中适当的位置上，使得新序列仍然是一个有序序列。主要介绍三种：直接插入排序、折半插入排序和希尔排序。1.2.1.直接插入排序思路：仅有一个元素的序列总是有序的，因此，对n个记录的序列，可从第二个元素开始直到第n个元素，逐个向有序序列中执行插入操作，从而得到n个元素按关

6、键字有序的序列。代码如下：voidinsert(int[]a){for(inti=1;i=0&&tmp

7、+1即为待插入位置}}}1.1.1.折半插入排序思路：可以不断二分有序序列来确定插入位置，即搜索插入位置的方法可以使用折半查找实现。代码如下：voidbinaryInsert(int[]a){for(inti=1;i

8、