Java 递归算法的相干实现
递归实质：程序调用本身的编程技巧叫做递归。
递归的三个条件：1.边界条件 2.递归后退段 3.递归返回段
当边界条件不满足时，递归后退；当边界条件满足时，递归返回。
递归是用栈机制实现的，每深刻一层，都要占去一块栈的数据区域。
留神：
1.递归肯定要有条件限定，保障递归能够可能停下来，否则会造成死循环并产生栈内存溢出（StackOverflowError）
2.递归中尽管限定了停止下来的条件，然而递归次数不能太多，否则也会产生栈内存溢出
3.禁止构造方法递归
一：递归阶乘
/**阶乘递归实现*/public static int Factorial(int n){ if (1==n){//边界条件，阶乘到最初一个数时候返回1 return 1; }else { return n*Factorial(n-1); }}//调用int content=Factorial(10);Log.d("aa",content+"");//后果aa: 3628800
二：斐波那契数列
1，1，2，3，5，8，13，21，34，55，89，144和无穷大。这个数列从第3项开始，每一项都等于前两项之和，这一系列数字被称为斐波那契数列，随着数列项数的减少，前一项与后一项之比越来越迫近黄金分割的数值0.6180339887..…
/**斐波那契数列（兔子数列）*/public static int BirthRabbit(int x){ if (x==1||x==2){// return 1; }else { return BirthRabbit(x-1)+BirthRabbit(x-2); }}//调用for (int i=1;i<=20;i++){ System.out.println("兔子第" + i + "个月的总数为:" + BirthRabbit(i));//输入20个月，每一个月的兔子数}int content=BirthRabbit(10);//输入10个月的兔子数Log.d("aa",content+"");//后果aa: 55三：汉罗塔问题
/** * 汉诺塔问题 * * @param dish 盘子个数(也示意名称) * @param from 初始塔座 * @param temp 中介塔座 * @param to 指标塔座 */public static void move(int dish,String from,String temp,String to){ if (dish==1){ System.out.println("将盘子"+dish+"从塔座"+from+"挪动到指标塔座"+to); }else { move(dish-1,from,to,temp);//a为初始塔座，b为指标塔座，c为中介塔座 System.out.println("将盘子"+dish+"从塔座"+from+"挪动到指标"+to);//把a下面的最上面的一个盘子挪动到c move(dish-1,temp,from,to);//b为初始塔座，c为指标塔座，a为中介塔座 }}//调用move(3,"A","B","C");//后果System.out: 将盘子1从塔座A挪动到指标塔座CSystem.out: 将盘子2从塔座A挪动到指标BSystem.out: 将盘子1从塔座C挪动到指标塔座BSystem.out: 将盘子3从塔座A挪动到指标CSystem.out: 将盘子1从塔座B挪动到指标塔座ASystem.out: 将盘子2从塔座B挪动到指标CSystem.out: 将盘子1从塔座A挪动到指标塔座C四：树的遍历
树的遍历：
1.深度优先(DFS)
1.前序遍历
2.中序遍历
3.后序遍历
2.广度优先（BFS）
1.档次遍历
前提：
//定义节点的数据结构public class TreeNode { String value=null; TreeNode leftChildren=null; TreeNode rightChildren=null; public TreeNode(String value, TreeNode leftChildren, TreeNode rightChildren) { this.value = value; this.leftChildren = leftChildren; this.rightChildren = rightChildren; } public TreeNode(String value) { this.value = value; } public String getValue() { return value; } public void setValue(String value) { this.value = value; } public TreeNode getLeftChildren() { return leftChildren; } public void setLeftChildren(TreeNode leftChildren) { this.leftChildren = leftChildren; } public TreeNode getRightChildren() { return rightChildren; } public void setRightChildren(TreeNode rightChildren) { this.rightChildren = rightChildren; }}4.1：前序遍历
思路：先根节点-->左子树-->右子树
实现：
/**创立二叉树*/public TreeNode getTargetTree() { // 叶子节点 TreeNode G = new TreeNode("G"); TreeNode D = new TreeNode("D"); TreeNode E = new TreeNode("E", G, null); TreeNode B = new TreeNode("B", D, E); TreeNode H = new TreeNode("H"); TreeNode I = new TreeNode("I"); TreeNode F = new TreeNode("F", H, I); TreeNode C = new TreeNode("C", null, F); // 结构根节点 TreeNode root = new TreeNode("A", B, C); return root;}/**前序遍历*/public void preorderTreeNode(TreeNode node){ if (null!=node){ System.out.print(node.value); } if (null!=node.leftChildren){ preorderTreeNode(node.leftChildren);//递归实现 } if (null!=node.rightChildren){ preorderTreeNode(node.rightChildren);//递归实现 }}//调用TreeNode tree= getTargetTree();//构建树 System.out.print("前序遍历:"); preorderTreeNode(tree); //后果： System.out: 前序遍历:ABDEGCFHI4.2 末子节点遍历
/**前序遍历拿到末节点信息*/public void endOrderTreeNode(TreeNode node){ if (null!=node&&null==node.leftChildren&&null==node.rightChildren){ System.out.print(node.value); } if (null!=node.leftChildren){ endOrderTreeNode(node.leftChildren); } if (null!=node.rightChildren){ endOrderTreeNode(node.rightChildren); }}或者：/**前序遍历末子节点*/public void preorderTreeNode2(TreeNode node){ if (null==node.leftChildren&&null==node.rightChildren){ System.out.print(node.value); } List<TreeNode> lists=new ArrayList<>(); if (null!=node.leftChildren){ lists.add(node.leftChildren); } if (null!=node.rightChildren){ lists.add(node.rightChildren); } for (int i=0;i<lists.size();i++){ preorderTreeNode2(lists.get(i)); }}//调用TreeNode tree= getTargetTree();System.out.print("末子节点遍历:");endOrderTreeNode(tree);//后果System.out: 末子节点遍历:DGHI4.3 中序遍历
思路：先左子树-->根节点-->右子树
实现：
/** * 中序遍历 */public void inorderTreeNode(TreeNode node){ if(null != node){ if(null != node.leftChildren){ inorderTreeNode(node.leftChildren); } System.out.print(node.value); if(null != node.rightChildren){ inorderTreeNode(node.rightChildren); } }}//调用TreeNode tree= getTargetTree(); System.out.print("中序遍历:"); inorderTreeNode(tree); //后果 中序遍历:DBGEACHFI4.4 后序遍历
思路：先左子树-->右子树-->根节点
/** * 后序遍历 */public void postorderTreeNode(TreeNode node){ if(null != node){ if(null != node.leftChildren){ postorderTreeNode(node.leftChildren); } if(null != node.rightChildren){ postorderTreeNode(node.rightChildren); } System.out.print(node.value); }}//调用TreeNode tree= getTargetTree(); System.out.print("后序遍历:"); postorderTreeNode(tree); //后果 System.out: 后序遍历:DGEBHIFCA4.5 档次遍历
思路：先根节点，而后第二层，第三层，顺次往下走，（同层节点从左往右输入）
/** * 档次遍历 */public void levelorderTreeNode(TreeNode node) { if (null != node) { LinkedList<TreeNode> list = new LinkedList<TreeNode>(); list.add(node);//增加以后节点 list.size()为1，增加的以后节点是A TreeNode currentNode; while (!list.isEmpty()) { currentNode = list.poll(); //获取并移除此列表的头部 System.out.print(currentNode.value);//许可以后节点的值 if (null != currentNode.leftChildren) { list.add(currentNode.leftChildren);//增加左子树到列表尾部 } if (null != currentNode.rightChildren) { list.add(currentNode.rightChildren);//增加右子树到列表的尾部 } } }}//调用TreeNode tree= getTargetTree(); System.out.print("档次遍历:"); levelorderTreeNode(tree); //后果 System.out: 档次遍历:ABCDEFGHI知识点：
1，结点的度： 一个结点含有的子结点的个数称为该结点的度；
2，叶结点或终端结点： 度为0的结点称为叶结点；
3，非终端结点或分支结点： 度不为0的结点；
4，双亲结点或父结点： 若一个结点含有子结点，则这个结点称为其子结点的父结点；
5，孩子结点或子结点： 一个结点含有的子树的根结点称为该结点的子结点；
6，兄弟结点： 具备雷同父结点的结点互称为兄弟结点；
7，树的度： 一棵树中，最大的结点的度称为树的度；
8，结点的档次： 从根开始定义起，根为第1层，根的子结点为第2层，以此类推；
9，树的高度或深度： 树中结点的最大档次；
10，堂兄弟结点： 双亲在同一层的结点互为堂兄弟；
11，结点的先人： 从根到该结点所经分支上的所有结点；
12，子孙： 以某结点为根的子树中任一结点都称为该结点的子孙。
13，森林： 由m（m>=0）棵互不相交的树的汇合称为森林；
14，无序树： 树中任意节点的子结点之间没有程序关系，这种树称为无序树,也称为自在树;
15，有序树： 树中任意节点的子结点之间有程序关系，这种树称为有序树；
16，二叉树： 每个节点最多含有两个子树的树称为二叉树；
17，齐全二叉树： 若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都间断集中在最右边，这就是齐全二叉树
18，满二叉树： 除最初一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。
19，哈夫曼树： 带权门路最短的二叉树称为哈夫曼树或最优二叉树；
END:当你远远注视深渊时，深渊也在注视你