一个前端,爱跑步、爱吉他、爱做饭、爱生活、爱编程、爱南芳姑娘,爱我所爱。世间最温暖又无价的是阳光、空气与爱,愿它们能带你去更远的地方。

  • 文章
  • 心情
  • 照片墙
  • 留言板
  • 工具
  • 友链
  • biaoblog

    专注web开发技术分享

    递归的示例以及学习

    技术 184 2020-11-19 15:44

    先来解释下广度和深度的意思:

    广度优先

    所谓广度,就是一层一层的,向下遍历,层层堵截,看下面这幅图


    深度优先

    度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。不全部保留结点,占用空间少;有回溯操作(即有入栈、出栈操作),运行速度慢

    接下来上代码:

     // 模拟数据
        let msg = [
          {
            name: 1,
            children: [
              {
                name: "1-1",
                children: [
                  {
                    name: "1-1-1",
                  },
                  {
                    name: "1-1-2",
                  },
                ],
              },
            ],
          },
          {
            name: 2,
            children: [
              {
                name: "2-1",
              },
              {
                name: "2-2",
              },
            ],
          },
        ];
        // 广度优先
        function wideTraversal(msg, data = []) {
          // console.log(msg.length);
          let nowData = [];
          if (msg != null) {
            for (let i = 0; i < msg.length; i++) {
              // console.log(i);
              data.push(msg[i]);
    
    
              msg[i].children && nowData.push(...msg[i].children);
              if (msg.length == i + 1) {
                // 确保第一层遍历完
                wideTraversal(nowData, data);
              }
              // msg.length == i + 1 && wideTraversal(nowData, data);
            }
          }
          return data;
        }
        let data = wideTraversal(msg);
        console.log(data);
    
        //深度优先遍历
        function deepTraversal(msg, data = []) {
          if (msg != null) {
            for (let i = 0; i < msg.length; i++) {
              data.push(msg[i]);
              msg[i].children && deepTraversal(msg[i].children, data);
            }
          }
          return data;
        }
        let data = deepTraversal(msg);
    
        console.log(data);
    

    上面代码的打印结果的tree 其实就是树结构的渲染顺序 需要这么理解。


    2022/2/22新增:

    react版本简单的递归例子:

    <!DOCTYPE html>
    <html lang="en">
      <head>
        <meta charset="UTF-8" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
        <script src="https://unpkg.com/react@16/umd/react.development.js"></script>
        <script src="https://unpkg.com/react-dom@16/umd/react-dom.development.js"></script>
        <script src="https://unpkg.com/babel-standalone@6.26.0/babel.js"></script>
      </head>
      <body>
        <div id="root"></div>
      </body>
    
      <script type="text/babel">
        function Testr() {
          return <h1>123</h1>;
        }
        class App extends React.Component {
          constructor(props) {
            super(props);
            this.state = {
              testVal: "123",
              tree: [
                {
                  label: "dashboard",
                  key: "dashboard",
                  children: [
                    {
                      label: "User Dashboard",
                      children: [
                        {
                          label: "xxxx",
                          key: "xxxx",
                        },
                        {
                          label: "yyyy",
                          key: "yyyy",
                        },
                      ],
                    },
                    {
                      label: "Onboarding Dashboard",
                      key: "OnboardingDashboard",
                    },
                  ],
                },
                {
                  label: "Timesheets/Expenses",
                  key: "Timesheets",
                  children: [
                    {
                      label: "User Timesheets",
                      children: [
                        {
                          label: "ss",
                          key: "ss",
                        },
                        {
                          label: "qq",
                          key: "qq",
                        },
                      ],
                    },
                    {
                      label: "Onboarding Timesheets",
                      key: "OnboardingTimesheets",
                    },
                  ],
                },
              ],
            };
          }
    
          getMenuNodes = (menuList) => {
            return menuList.map((item) => {
              if (!item.children) {
                return (
                  <li style={{ paddingLeft: 25 }}>
                    <span>{item.label}</span>
                  </li>
                );
              } else {
                return (
                  <li style={{ paddingLeft: 25 }} key={item.key}>
                    <span>{item.label}</span>
                    {this.getMenuNodes(item.children)}
                  </li>
                );
              }
            });
          };
    
          render() {
            const { tree } = this.state;
            return <div>{this.getMenuNodes(tree)}</div>;
          }
        }
        ReactDOM.render(<App />, document.getElementById("root"));
      </script>
    </html>
    


    2022/7/11 新增样例:

    给一个树结构 递归添加一个自定义字段:

    举例:

      {
        id: 'root',
        name: 'Parent',
        children: [
          {
            id: '1',
            name: 'Child - 1',
          },
            ],
          },
        ],
      },
    

      转为:

      {
        id: 'root',
        name: 'Parent',
        checked:false ,
        children: [
          {
            id: '1',
            name: 'Child - 1',
            checked:false
          },
            ],
          },
        ],
      },
    

    下面是代码:

      const setTreeCheckedVal = (treeData) => {
        for (let i = 0; i < treeData.length; i++) {
          treeData[i].checked = false;
          treeData[i].children && this.setTreeCheckedVal(treeData[i].children);
        }
        return treeData;
      };
    
        let data2 = this.setTreeCheckedVal(RadioTreeData);
        console.log(data2);
    


    2022/11/4 新增根据子节点查询相关联的父级节点(默认需要节点有parsentId 字段)


    思路:需要先把全部的树节点平铺到一层,

    然后根据所选择的子节点(这里场景是搜索,可以是多个子节点),


    循环遍历多个所选择的子节点,

    然后写一个递归函数,依次传递所选择节点的parsentid,

    去跟已经平铺到一层的全部节点进行对比,parsentid === id 则添加到父节点的数组中,

    然后再传递 已经匹配上的 全部节点中的 那一个节点 (因为父节点还可能拥有父节点),进行递归。


    具体的方法在下面:

    // selected 是已经搜索出来的节点 是个arr 进行调用
    expanded = findParsent(selected);
      const setSpreadTreeData = (tree, data = []) => {
        for (let i = 0; i < tree.length; i++) {
          let item = tree[i];
          data.push(item);
          item.children && setSpreadTreeData(item.children, data);
        }
        return data;
      };  
    
    const findParsent = (selected) => {
            //把全部的节点都平铺到一层,方便后面遍历
        let spreadTreeData = setSpreadTreeData(data);
        let parsentNodes = [];
           // 执行递归
        let dist = (parentId, arr) => {
          for (let s of spreadTreeData) {
            if (s.id == parentId) {
              arr.push(s);
              if (s.parentId) {
                dist(s.parentId, arr);
              }
            }
          }
          return arr;
        };
        for (let s of selected) {
          parsentNodes = dist(s.parentId, parsentNodes);
        }
        // parsentNodes 是 匹配到的已经选择的子节点 所关联的全部的 父节点 
          return parsentNodes;
        };
    


    2022/12/13 新增根据子节点联动父节点勾选状态

    父节点联动的规则如下:

            第一种情况:全部子节点勾选,则父节点也勾选 即checked = true
            第二种情况:子节点全部取消勾选,则父节点取消勾选 即checked = false
            第三种情况:部分子节点勾选,则父节点也勾选 即checked = true

    实现思路:

    在之前的逻辑上 - 即点击某个节点 其子节点也全部自动勾选,

    得到的一组数据在之后,(不在之前的逻辑上直接设置关联的父节点,因为子节点是从上往下递归,而父节点需要至下而上的寻找)

    单独写一个关联父节点的方法:

    1.首先根据所勾选的节点,查找到它的全部父节点(可能父节点还有父节点所以需要递归)

    两个参数,一个所勾选的节点(多个,单个),一个完整的tree数据


    // 根据树子节点(单个,多个)寻找所有父节点
    export const findParentNodes = (selected, tree) => {
      let spreadTreeData = setSpreadTreeData(tree, false, []);
      let parsentNodes = [];
      let deep = (parentId, parsentNodes) => {
        for (let tree of spreadTreeData) {
          if (tree.id == parentId) {
            parsentNodes.push(tree);
            if (tree.parentId) {
              deep(tree.parentId, parsentNodes);
            }
          }
        }
        return parsentNodes;
      };
    
      // autotemplate 组件传递的seleted是个array需要处理
      if (Array.isArray(selected)) {
        for (let selectedItem of selected) {
          parsentNodes = deep(selectedItem.parentId, parsentNodes);
        }
      } else {
        parsentNodes = deep(selected.parentId, parsentNodes);
      }
    
      return parsentNodes;
    };
    复制代码
    

    还需要一个平铺tree数据的方法:setSpreadTreeData


    // 平铺tree
    // 此函数的作用:拿到树结构后 进行树结构的渲染 同时需要把已经checked的数据 平铺到一层
    // 主要是因为Autocomplete组件需要进行渲染 是个只有一层的array
    // jugdeCheck 这个字段如果平铺不需要判断是否checked 就不需要传递
    export const setSpreadTreeData = (tree, jugdeCheck, data = []) => {
      for (let i = 0; i < tree.length; i++) {
        let item = tree[i];
        if (jugdeCheck) {
          if (item.checked) {
            data.push(item);
          }
        } else {
          data.push(item);
        }
        item.children && setSpreadTreeData(item.children, jugdeCheck, data);
      }
      return data;
    };
    复制代码
    

    2.得到所勾选的子节点的全部父节点之后,再单独写一个方法,传递之前已经处理勾选逻辑的数据,

    进行向上遍历。


    // 根据所勾选的子节点 关联其父节点
    export const cascaderParsent = (parsents, checked, tree) => {
      for (let i = 0; i < tree.length; i++) {
        let item = tree[i];
        for (let parsent of parsents) {
          // console.log('parsent::', parsent);
          if (parsent.id === item.id) {
            let { checkedNodes, activeNodeChildren } = setSpreadTreeDataCascader(
              parsent.children || []
            );
            // 第一种情况:全部子节点勾选,则父节点也勾选 即checked = true
            // 第二种情况:子节点全部取消勾选,则父节点取消勾选 即checked = false
            // 第三种情况:部分子节点勾选,则父节点也勾选 即checked = true
            // console.log('checkedNodes::', checkedNodes);
            // console.log('activeNodeChildren::', activeNodeChildren);
            if (checkedNodes.length === activeNodeChildren.length) {
              item.checked = true;
            } else if (checkedNodes.length === 0 && activeNodeChildren.length > 0) {
              item.checked = false;
            } else {
              item.checked = true;
            }
          }
        }
    
        if (item.children) {
          // 继续往子集找
          cascaderParsent(parsents, checked, item.children);
        }
      }
    
      return tree;
    };
    复制代码
    

    这里判断父节点是是勾选或者是不勾选的逻辑是根据:

    1.父节点全部的子节点

    2.父节点已激活的子节点


    判断逻辑如下:

            第一种情况:全部子节点勾选,则父节点也勾选 即checked = true
            第二种情况:子节点全部取消勾选,则父节点取消勾选 即checked = false
            第三种情况:部分子节点勾选,则父节点也勾选 即checked = true


    这里还有一个平铺的方法:setSpreadTreeDataCascader


    也可以使用之前的setSpreadTreeData ,但是需要递归两次

    像这样:


           // 全部节点 
         let activeNodeChildrenCount = setSpreadTreeData(node.children);
            //获取当前父节点当前所有激活的子节点
          let checkedNodes = setSpreadTreeData(node.children, true);
    复制代码
    

    但是效率很低,理想的状态是一次递归就生成两种所需数据:

    改造一下:


    // tree联动平铺专用
    export const setSpreadTreeDataCascader = (
      tree,
      checkedNodes = [], //已勾选的节点
      activeNodeChildren = [] //全部节点 - 包含已勾选和未勾选
    ) => {
      for (let i = 0; i < tree.length; i++) {
        let item = tree[i];
        if (item.checked) {
          checkedNodes.push(item);
        }
        activeNodeChildren.push(item);
        item.children &&
          setSpreadTreeDataCascader(
            item.children,
            checkedNodes,
            activeNodeChildren
          );
      }
      return { checkedNodes, activeNodeChildren };
    };
    复制代码
    

    然后取值就可以这样做了:


          let { checkedNodes, activeNodeChildren } = setSpreadTreeDataCascader(
            node.children || []
          );
    复制代码
    

    然后就是material chekbox的ui

    横杠的ui其实就是checkbox的indeterminate属性

    判断就行即可(代码为递归的一部分,前置还有treeItem的自定义label):


    判断ui的逻辑为:

           有子集的情况下:
           第一种情况:全部子节点勾选,则父节点也是勾选的样式1 即indeterminate = false
           第二种情况:子节点全部取消勾选,则父节点是勾选的样式1 即即indeterminate = false
           第三种情况:部分子节点勾选,则父节点是勾选的样式2 即indeterminate = true


        // 判断chekbox样式  - 优化方案
        let jugdeIndetermainte = (node) => {
          let { checkedNodes, activeNodeChildren } = setSpreadTreeDataCascader(
            node.children || []
          );
          // 有子集的情况下:
          // 第一种情况:全部子节点勾选,则父节点也是勾选的样式1 即indeterminate = false
          // 第二种情况:子节点全部取消勾选,则父节点是勾选的样式1 即即indeterminate = false
          // 第三种情况:部分子节点勾选,则父节点是勾选的样式2 即indeterminate = true
          // console.log('checkedNodes::', checkedNodes.length);
          // console.log('activeNodeChildren::', activeNodeChildren.length);
          if (
            checkedNodes.length === activeNodeChildren.length ||
            (checkedNodes.length === 0 && activeNodeChildren.length > 0)
          ) {
            return false;
          } else {
            return true;
          }
        };
    
        <Checkbox
              indeterminate={jugdeIndetermainte(node)}
              checked={node.checked}
              color="primary"
              onChange={(e) => {
              	//balabala
              }}
            />
    复制代码
    

    然后没什么了

    有疑问可以留言

    拜拜 各位同学!


    文章评论

    评论列表(0