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

36次阅读

共计 5621 个字符,预计需要花费 15 分钟才能阅读完成。

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

正文完
 0