关闭

Js二叉树与多叉树的遍历

时间: 2019-05-28阅读: 865标签: 遍历

二叉树的顺序存储结构就是用一维数组存储二叉树中的各个结点,并且结点的存储位置能体现结点之间的逻辑关系。


二叉树的遍历

二叉树的遍历有三种方式,如下:

(1)先序遍历(DLR),首先访问根结点,然后遍历左子树,最后遍历右子树。简记根-左-右。

(2)中序遍历(LDR),首先遍历左子树,然后访问根结点,最后遍历右子树。简记左-根-右。

(3)后序遍历(LRD),首先遍历左子树,然后遍历右子树,最后访问根结点。简记左-右-根。


假设dom结构如下:

<div id="tree">

    <div>

      <div>
        <div></div>
        <div></div>
      </div>

      <div>
        <div></div>
        <div></div>
      </div>

    </div>

    <div>

      <div>
        <div></div>
        <div></div>
      </div>

      <div>
        <div></div>
        <div></div>
      </div>

    </div>
  </div>


遍历方式:  

var arr = [];
  // 递归先序遍历
  function recurDLR(node) {
    if (!node) {
      return;
    }
    arr.push(node);
    recurDLR(node.firstElementChild);
    recurDLR(node.lastElementChild);
  }
  // 递归中序遍历
  function recurLDR(node) {
    if (!node) {
      return;
    }
    recurLDR(node.firstElementChild);
    arr.push(node);
    recurLDR(node.lastElementChild);
  }
  // 递归后序遍历
  function recurLRD(node) {
    if (!node) {
      return;
    }
    recurLRD(node.firstElementChild);
    recurLRD(node.lastElementChild);
    arr.push(node);   
  }


多叉树结构遍历  

// 递归先序遍历 先遍历子节点 再遍历根节点
  function recurDLR(node) {
    if (!node) {
      return;
    }
    arr.push(node);
    for (let i = 0; i < node.children.length; i++) {
      if (node.children[i].nodeName.toLowerCase() === 'div') {
        recurDLR(node.children[i]);
      }      
    }   
  } 
  // 递归后序遍历 先遍历根节点 再遍历子节点
  function recurLRD(node) {
    if (!node) {
      return;
    }
    for (let i = 0; i < node.children.length; i++) {
      if (node.children[i].nodeName.toLowerCase() === 'div') {
        recurLRD(node.children[i]);
      }
    }
    arr.push(node);
  }

  // 层序遍历 从根节点一层一层向下遍历
  // 原理就是利用数组的后进先出 存储dom节点
  function recurLDR(node) {
    var stack = [];
    stack.push(node);
    var del = stack.shift();
    while (del) {    
      for (let i = 0; i < del.children.length; i++) {
        if (del.children[i].nodeName.toLowerCase() === 'div') {
          stack.push(del.children[i]);
        }
      }
      arr.push(del);
      del = stack.shift();
    }        
  }


站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

2.广告联盟: 整理了目前主流的广告联盟平台,如果你有流量,可以作为参考选择适合你的平台点击进入

链接: http://www.fly63.com/article/detial/3457

关闭

Js数组遍历方法总汇

for in语句用于遍历数组或者对象的属性(对数组或者对象的属性进行循环操作);For循环可以将代码块执行指定的次数。forEach按照原始数组元素顺序依次处理元素.

PHP遍历二叉树

遍历二叉树,这个相对比较复杂。二叉树的便利,主要有两种,一种是广度优先遍历,一种是深度优先遍历。什么是广度优先遍历?就是根节点进入,水平一行一行的便利。

为什么 JS 对象内部属性遍历的顺序乱了

查阅了 ECMA-262 3rd edition ,如下文 It is an unordered collection of properties 就说到 ES3 标准的对象不排序,插入是啥顺序,遍历就是啥顺序

javascript如何遍历对象?

javascript遍历对象的方法:1、使用Object.keys()遍历。2、使用for..in.遍历。3、使用Object.getOwnPropertyNames(obj)遍历。4、使用Reflect.ownKeys(obj)遍历。

js数组、对象、字符串的遍历

数组遍历:for --使用变量将数组长度缓存起来,在数组较长时性能优化效果明显,forEach --ES5语法;对象遍历:for...in --以任意顺序遍历一个对象自有的、继承的、可枚举的

Js中forEach跳出循环体

在forEach中,不能使用 continue 和 break ,可以使用 return 或 return false 跳出循环,效果与 for 中 continue 一样。注意该方法无法一次结束所有循环。

javascript如何循环遍历对象?

在JavaScript中有多种循环遍历对象的方法,下面本篇文章就来给大家介绍一下使用JavaScript循环遍历对象的方法,希望对大家有所帮助。

Js中常见的几种循环遍历

项目开发中,不管是建立在哪个框架基础上,对数据的处理都是必须的,而处理数据离不开各种遍历循环。javascript中循环遍历有很多种方式,记录下几种常见的js循环遍历。

JavaScript中,数组和对象的遍历方法总结

循环遍历是写程序很频繁的操作,JavaScript 提供了很多方法来实现。这篇文章将分别总结数组和对象的遍历方法,新手可以通过本文串联起学过的知识。

JS中map与forEach的用法

相同点:都是循环遍历数组中的每一项;每次执行匿名函数都支持三个参数,参数分别为item(当前每一项),index(索引值),arr(原数组)

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!