精华内容
下载资源
问答
  • 针对扩展递归技术的局限性,本文提出基于树的递归算法分析技术。借助于分析树,可直观地、清晰地描述递归算法的分析过程,从而有效地解决递归算法时间复杂性的分析问题。
  • 工作中常用的关于树的递归算法

    千次阅读 2021-02-04 21:57:46
    递归算法在计算机科学中是指一种通过重复将问题分解为同类子问题而解决问题方法。众所周知数据结构快速排序算法就是基于递归实现。递归这是一种很重要算法思想,在C语言,Java中普遍应用,大学期间参加...

    递归介绍

    • 递归算法在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。众所周知的数据结构的快速排序算法就是基于递归实现的。递归这是一种很重要的算法思想,在C语言,Java中普遍应用,大学期间参加算法竞赛递归算法在所难免。
    • 根据我个人的理解,一个递归程序就是方法自身调用自身,一个递归函数中主要包含三个部分,第一递归出口,第二执行的逻辑代码,第三子问题递归执行

    案例介绍

    递归获取菜单树

    第一种: stream流实现(推荐)

    /**
         * stream流获取菜单树
         * @param parentId
         * @param list
         * @return
         */
        public List<Menu> selectTree(Long parentId,List<Menu> list) {
            List<Menu> leve1Menus = list.stream().filter(treeEntity ->
                treeEntity.getPid().equals(parentId)
            ).map((root) -> {
                root.setChildren(getChildNode(root,list));
                return root;
            }).collect(Collectors.toList());
            return leve1Menus;
        }
        /**
         * 递归子节点
         * @param root   当前单个菜单
         * @param allListTree   表中的所有菜单集合
         * @return
         */
        private List<Menu> getChildNode(Menu root, List<Menu> allListTree){
            List<Menu> ChildNodeList = allListTree.stream().filter((treeEntity) -> {
                return treeEntity.getPid().equals(root.getId());
            }).map((treeEntity)->{
                treeEntity.setChildren(getChildNode(treeEntity,allListTree));
                return treeEntity;
            }).collect(Collectors.toList());
            return ChildNodeList;
        }
    

    第二种: 普通递归实现

    /**
         * 递归返回菜单树
         * @param list
         * @return
         */
        public static List<Menu> getListMenu(Long parentId,List<Menu> list) {
    
            List menuListTree = new ArrayList<>();
            for (Menu menu : list) {
                if (menu.getPid() == parentId) { //如果是根节点(存在多个根)
                    List<Menu> children = getListMenu(menu.getId(), list);
                    if (!children.isEmpty()){
                        menu.setChildren(children);
                    }
                    menuListTree.add(menu);
                }
            }
            return menuListTree;
        }
    

    第三种 :

    @Override
        @Transactional(readOnly = true)
        public List<TreeNodeV2> queryTreeNode() {
            //根节点集合
            List<TreeNodeV2> tops = new ArrayList<>();
            //非跟节点集合
            List<TreeNodeV2> subs = new ArrayList<>();
            //所有节点集合
            List<TreeNodeV2> all = new ArrayList<>();
            List<TbContentCategory> categories = contentCategoryMapper.selectAll();
            //获取根节点
            for(TbContentCategory category : categories) {
                TreeNodeV2 node = new TreeNodeV2(category.getId(),category.getParentId(), category.getName(), category.getIsParent()==1?false:true, new ArrayList<>());
                if (category.getParentId() == 0) {
                    tops.add(node);
                } else {
                    subs.add(node);
                }
                all.add(node);
            }
            //遍历所有的非根节点
            for (TreeNodeV2 node : subs) {
                //根据父节点id在all找当前节点的父节点
                /*
                for (TreeNodeV2 n : all) {
                    if (n.getId() == node.getParentId()) {
                        n就是parent
                    }
                }
                 */
                //node的父节点
                TreeNodeV2 parent = all.stream().filter(n -> node.getParentId().equals(n.getId())).findFirst().orElse(null);
                //将当前节点存放到parent的children中
                if (parent != null) {
                    parent.getChildren().add(node);
                }
    
            }
    
            return tops;
        }
    

    遍历当前节点到根节点的路径信息

    private static List<Menu> pathList = new ArrayList<>();
        /**
         * 组装当前节点到根节点的路径信息保存到pathList
         * @param menu 当前节点编号
         * @param parentId 根节点编号
         * @param list 所有节点数据
         */
        public void assumbleParentMenu (Menu menu,Long parentId,List<Menu> list) {
            if(menu.getId().equals(parentId)) {
                return;
            }
            pathList.add(menu);
            Menu menu1 = list.stream().filter(item -> item.getId().equals(menu.getPid())).findFirst().orElse(null);
            assumbleParentMenu(menu1,parentId,list);
        }
    

    递归获取当前节点(不包含自身)的所有孩子节点

    private static List<Long> menuIds = new ArrayList<>();
        /**
         * 获取当前节点(不包含自身)的所有孩子节点的物理主键
         * @param menu 当前节点
         * @param list 所有节点数据
         */
        public static void getMenuChildren(Menu menu,List<Menu> list) {
            List<Menu> collect = list.stream().filter(item -> item.getPid().equals(menu.getId())).collect(Collectors.toList());
            if (!collect.isEmpty()) {
                menuIds.addAll(collect.stream().map(Menu::getId).collect(Collectors.toList()));
                for(Menu temp : collect) {
                    getMenuChildren(temp,list);
                }
            } else {
                return;
            }
        }
    

    踩坑记录–不断补充

    Java 栈溢出

    • 首先查看数据库的数据是否存在不断相互调用的,因为JVM中Java的执行的压栈执行,这样不断压栈,就会导致最后的栈溢出。
    展开全文
  • ExtJs树的递归算法(Java),Json格式 首先先建立Node模型 [java] view plaincopy public class Node {   private int id;   private int parentId;   Node...
     

    ExtJs树的递归算法(Java),Json格式


    首先先建立Node模型

    [java] view plaincopy
    1. public class Node {    
    2.     private int id;    
    3.     private int parentId;    
    4.     Node(){}    
    5.     Node(int id,int parentId){    
    6.         this.id=id;    
    7.         this.parentId = parentId;    
    8.     }    
    9.     public int getId() {    
    10.         return id;    
    11.     }    
    12.     public void setId(int id) {    
    13.         this.id = id;    
    14.     }    
    15.     public int getParentId() {    
    16.         return parentId;    
    17.     }    
    18.     public void setParentId(int parentId) {    
    19.         this.parentId = parentId;    
    20.     }    
    21. }    

    下面这个类先手工建立List,在实际应用中是从数据库读取List,然后再Main方法里调用递归方法,得到Json字符串

    [java] view plaincopy
    1. import java.util.ArrayList;    
    2. import java.util.Iterator;    
    3. import java.util.List;    
    4.     
    5.     
    6. public class Recursion {    
    7.     List nodeList =new ArrayList();    
    8.     Recursion(){//构造方法里初始化模拟List    
    9.         Node node1 = new Node(1,0);      
    10.         Node node2 = new Node(2,1);      
    11.         Node node3 = new Node(3,1);      
    12.         Node node4 = new Node(4,2);      
    13.         Node node5 = new Node(5,2);      
    14.         Node node6 = new Node(6,2);      
    15.         Node node7 = new Node(7,6);      
    16.         Node node8 = new Node(8,6);      
    17.               
    18.         nodeList.add(node1);      
    19.         nodeList.add(node2);      
    20.         nodeList.add(node3);      
    21.         nodeList.add(node4);      
    22.         nodeList.add(node5);      
    23.         nodeList.add(node6);      
    24.         nodeList.add(node7);      
    25.         nodeList.add(node8);      
    26.     }    
    27.     StringBuffer returnStr=new StringBuffer();      
    28.     public void recursionFn(List list , Node node){      
    29.         if(hasChild(list,node)){      
    30.             returnStr.append("{id:");    
    31.             returnStr.append(node.getId());    
    32.             returnStr.append(",parentId:");    
    33.             returnStr.append(node.getParentId());    
    34.             returnStr.append(",children:[");      
    35.             List childList = getChildList(list,node);      
    36.             Iterator it = childList.iterator();      
    37.             while(it.hasNext()){      
    38.                 Node n = (Node)it.next();      
    39.                 recursionFn(list,n);      
    40.             }      
    41.             returnStr.append("]},");      
    42.         }else{      
    43.             returnStr.append("{id:");    
    44.             returnStr.append(node.getId());    
    45.             returnStr.append(",parentId:");    
    46.             returnStr.append(node.getParentId());    
    47.             returnStr.append(",leaf:true},");      
    48.         }      
    49.               
    50.     }      
    51.     public boolean hasChild(List list, Node node){  //判断是否有子节点    
    52.         return getChildList(list,node).size()>0?true:false;    
    53.     }    
    54.     public List getChildList(List list , Node node){  //得到子节点列表    
    55.         List li = new ArrayList();      
    56.         Iterator it = list.iterator();      
    57.         while(it.hasNext()){      
    58.             Node n = (Node)it.next();      
    59.             if(n.getParentId()==node.getId()){      
    60.                 li.add(n);      
    61.             }      
    62.         }      
    63.         return li;      
    64.     }    
    65.     public String modifyStr(String returnStr){//修饰一下才能满足Extjs的Json格式    
    66.         return ("["+returnStr+"]").replaceAll(",]""]");    
    67.             
    68.     }    
    69.     public static void main(String[] args) {      
    70.         Recursion r = new Recursion();      
    71.         r.recursionFn(r.nodeList, new Node(1,0));      
    72.         System.out.println(r.modifyStr(r.returnStr.toString()));      
    73.     }      
    74. }    

    Main方法运行效果如下:
    [{id:1,parentId:0,children:[{id:2,parentId:1,children:[{id:4,parentId:2,leaf:true},{id:5,parentId:2,leaf:true},{id:6,par
    entId:2,children:[{id:7,parentId:6,leaf:true},{id:8,parentId:6,leaf:true}]}]},{id:3,parentId:1,leaf:true}]}]
    在具体的应用中稍加修改即可


    展开全文
  • 最近在做微软等复试100题,里面有很多树的算法都是使用递归的,个人觉得做了以后加深了对树的理解。 树本身就是递归定义的,这就导致了很多树的算法自然而然用到递归,并且用非递归的话实现起来很不方便, 比如...

    最近在做微软等复试100题,里面有很多树的算法都是使用递归的,个人觉得做了以后加深了对树的理解。

    树本身就是递归定义的,这就导致了很多树的算法自然而然用到递归,并且用非递归的话实现起来很不方便,

    比如二叉树的遍历,如果用非递归就得借用栈等数据结构,其本质就是使用栈进行“递归”。

    具体代码参见http://www.cnblogs.com/2010Freeze/archive/2010/06/01/1749128.html

    下面我们就开始看题目:

    1.把二元查找树转变成排序的双向链表题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。

    4.在二元树中找出和为某一值的所有路径。

    9.判断整数序列是不是二元查找树的后序遍历结果。

    11.求二叉树中节点的最大距离,姑且定义"距离"为两节点之间边的个数。

    15.输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。

    16.输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。

    39.求一个二叉树中任意两个节点间的最大距离,两个节点的距离的定义是这两个节点间边的个数。

    75.二叉树两个结点的最低共同父结。

    86.怎样编写一个程序,把一个有序整数数组放到二叉树中。

    建议自己好好做做,会有帮助的

    答案在http://www.cnblogs.com/v-July-v/archive/2010/12/06/2214143.html

     

     

     

    转载于:https://www.cnblogs.com/2010Freeze/articles/2415910.html

    展开全文
  • 利用递归计算递归算法的复杂度,这里以归并排序(mergesort)为例: 他时间复杂度是t(n)=2t(n/2)+Θ(n),下面将cn替换Θ(n);

    利用递归树计算递归算法的复杂度,这里以归并排序(mergesort)为例:

    他的时间复杂度是t(n)=2t(n/2)+Θ(n),下面将cn替换Θ(n);


    展开全文
  • 27|递归如何借助来求解递归算法的时间复杂度 27|递归如何借助来求解递归算法的时间复杂度 今天我们来讲这种数据结构一种特殊应用递归 我们都知道递归代码时间复杂度分析起来很麻烦我们在第12节排序...
  • 递归求解递归算法的时间复杂度

    千次阅读 2018-07-29 10:28:34
    递归算法时间复杂度计算方程式一个递归方程:    在引入递归之前可以考虑一个例子:  T(n) = 2T(n/2) + n2  迭代2次可以得:  T(n) = n2+ 2(2T(n/4) + (n/2)2)  还可以继续迭代,将其完全展开可得:...
  • 递归分析递归算法的时间复杂度

    千次阅读 2016-09-11 12:29:44
    T(n) = T(n/3) + T(2n/3) + n  其递归如下图所示:   ... 可见每层值都为n,从根到叶节点最长路径是: ... 因为最后递归停止是在(2/3)kn == 1.... 总结,利用此方法解递归算法复杂度:  f
  • (转)递归递归算法的时间复杂度

    千次阅读 2014-07-25 14:05:16
    递归递归算法的时间复杂度,十分清楚.从别人空间转来
  • 递归算法时间复杂度计算方程式一个递归方程:    在引入递归之前可以考虑一个例子:  T(n) = 2T(n/2) + n2  迭代2次可以得:  T(n) = n2+ 2(2T(n/4) + (n/2)2)  还可以继续迭代,将其完全展开可得:...
  • 递归算法时间复杂度计算方程式一个递归方程: 1. 举例 在引入递归之前可以考虑一个例子:,迭代1次可以得: 继续迭代,完全展开可得: 而当时,迭代结束。 将上式中小括号展开,可得: 这恰好是一个形...
  • 递归递归算法时间复杂度

    千次阅读 2015-01-19 11:11:17
    递归算法时间复杂度计算方程式一个递归方程:    在引入递归之前可以考虑一个例子:  T(n) = 2T(n/2) + n2  迭代2次可以得:  T(n) = n2 + 2(2T(n/4) + (n/2) 2)  还可以继续迭代,将其完全展开...
  • 用递归求解递归算法时间复杂度

    千次阅读 2019-07-01 23:27:38
    一般来说有两种分析方法:递推公式和递归树。 1 递推公式法 归并排序递推公式是: merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r)) 终止条件: p >= r 不用再继续分解 我们假设对n个...
  • 文章目录递归树与时间复杂度分析实战一:分析快速排序时间复杂度实战二:分析斐波那契数列时间复杂度实战三:待补充,先学其他... 递归树与时间复杂度分析 我们前面讲过,递归的思想就是,将大问题分解为小...
  • 树的遍历递归算法

    2020-05-02 15:27:06
    C语言森林转换成二叉树和二叉树转换成森林等的递归算法。 (1) 树的先序遍历算法: 代码: Status PreOrderTraverseTree(GenTree tree, void (*Visit)(TElemType data)){ if(!tree) return OK; Visit(tree->data)...
  • 递归算法时间复杂度计算方程式一个递归方程:    在引入递归之前可以考虑一个例子:  T(n) = 2T(n/2) + n2  迭代2次可以得:  T(n) = n2 + 2(2T(n/4) + (n/2) 2)  还可以继续迭代,将其完全展开...
  • 学习笔记(3)--递归递归算法时间复杂度 Having a solid base of algorithm knowledge and technique is one characteristic that separates the truly skilled programmers from the novices.  是否...
  • 树的递归与非递归遍历算法

    千次阅读 2017-10-28 14:01:55
    树的递归与非递归遍历算法 树的递归与非递归遍历算法 树的遍历 实例 树遍历的口诀 树的递归遍历代码 树的先序遍历 树的中序遍历 树的后序遍历 递归遍历思想 树的非递归遍历 树的先序非递归遍历 先序遍历运行结果 树...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,885
精华内容 3,954
关键字:

树的递归算法