关于java: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 挪动到指标塔座 C
System.out: 将盘子 2 从塔座 A 挪动到指标 B
System.out: 将盘子 1 从塔座 C 挪动到指标塔座 B
System.out: 将盘子 3 从塔座 A 挪动到指标 C
System.out: 将盘子 1 从塔座 B 挪动到指标塔座 A
System.out: 将盘子 2 从塔座 B 挪动到指标 C
System.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: 前序遍历:ABDEGCFHI

4.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: 末子节点遍历:DGHI

4.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);
 
 // 后果
 中序遍历:DBGEACHFI

4.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: 后序遍历:DGEBHIFCA

4.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: 当你远远注视深渊时，深渊也在注视你

关于java:Java-递归算法的相关实现

Java 递归算法的相干实现

Just My Socks（注册教程内含优惠码）

关于java:Java-递归算法的相关实现

Java 递归算法的相干实现

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）