树的各种遍历总结

转载 作者：知者 更新时间：2024-03-13 05:47:19 25 4

数据可以整理为：
const tree = {
  val: 'a',
  children: [{
      val: 'b',
      children: [{
          val: 'd',
          children: [],
        },
        {
          val: 'e',
          children: [],
        }
      ],
    },
    {
      val: 'c',
      children: [{
          val: 'f',
          children: [],
        },
        {
          val: 'g',
          children: [],
        }
      ],
    }
  ],
};

const dfs = (root) => {
  console.log(root.val)
  root.children.forEach(item => {
    dfs(item)
  })
}

dfs(tree)

const bfs = (node) => {
  let queue = [node]
  while(queue.length > 0) {
    let curNode = queue.shift()
    console.log(curNode.val)
    let child = curNode.children
    if(child && child.length > 0) {
      child.forEach(item => {
        queue.push(item)
      })
    }   
  }
}

bfs(tree)

const dbs = {
  val: 4,
  left: {
    val: 3,
    left: {
      val: 2,
      left: null,
      right: null
    },
    right: {
      val: 1,
      left: null,
      right: null
    }
  },
  right: {
    val: 5,
    left: {
      val: 6,
      left: null,
      right: null
    },
    right: {
      val: 7,
      left: null,
      right: null
    }
  }
}

const preorder = (root) => {
  if(!root) return
  console.log(root.val)
  if(root.left) preorder(root.left)
  if(root.right) preorder(root.right)
}
preorder(dbs)

const midorder = (root) => {
  if(!root) return 
  if(root.left) midorder(root.left)
  console.log(root.val)
  if(root.right) midorder(root.right)
}
midorder(dbs)

const afterorder = (root) => {
  if(!root) return
  if(root.left) afterorder(root.left)
  if(root.right) afterorder(root.right)
  console.log(root.val)
}

afterorder(dbs)

const preorder = (root) => {
  if (!root) return
  let stack = [root]
  while (stack.length > 0) {
    let cur = stack.pop()
    console.log(cur.val)
    if(cur.right) stack.push(cur.right)
    if(cur.left) stack.push(cur.left)
  }
}
preorder(dbs)

const midorder = (root) => {
  if(!root) return 
  let stack = []
  let p = root
  while(stack.length > 0 || p) {
    while(p) {
      stack.push(p)
      p = p.left
    }
    let cur = stack.pop()
    console.log(cur.val)
    p = cur.right
  }
}

midorder(dbs)

const postorder = (root) => {
  if(!root) return
  let stack1 = [root]
  let stack2 = []
  while(stack1.length > 0) {
    let cur = stack1.pop()
    stack2.push(cur)
    if(cur.left) stack1.push(cur.left)
    if(cur.right) stack1.push(cur.right)
  }
  while(stack2.length > 0) {
    let cur = stack2.pop()
    console.log(cur.val)
  }
}
postorder(dbs)

25 4 0

• 【网络流】总结

  1、定义 设 \(u\) 和 \(v\) 为一张图上的任意两个节点。令 \(c(u, v)\) 为它们之间的边的容量， \(f(u, v)\) 为它们之间的流量，则需要满足以

• linux下判断文件和目录是否存在的方法(总结)

  1、前言 工作中涉及到文件系统，有时候需要判断文件和目录是否存在。我结合apue第四章文件和目录，总结一下如何正确判断文件和目录是否存在，方便以后查询。 2、stat系列函数 stat函数用来

• c语言数据结构之并查集 总结

  并查集(Union-Find Set)： 一种用于管理分组的数据结构。它具备两个操作：(1)查询元素a和元素b是否为同一组 (2) 将元素a和b合并为同一组。 注意：并查集不能将在同一组的元素拆

• Mybatis常见注解有哪些(总结)

  当下，注解非常流行，以前很长篇的代码，现在基本上一个注解就能搞定。 那，在Mybatis中又有哪些注解呢？ Mybatis中的注解基本上都在org.apache.ibatis.annotat

• 指针操作数组的两种方法(总结)

  指针操作数组，方法一是p+index，方法二是p[index]，第二种方法跟数组访问方法是一样的。 数组引用返回的是数组的第一个元素的指针地址。 可以将指针指向数组的任意元素，然后从那里开始访问

• php安全配置记录和常见错误梳理(总结)

  通常部署完php环境后会进行一些安全设置，除了熟悉各种php漏洞外，还可以通过配置php.ini来加固PHP的运行环境，PHP官方也曾经多次修改php.ini的默认设置。 下面对php.ini中一

• PHP检测数据类型的几种方法(总结)

  在JavaScript中，使用typeof可以检测基本数据类型，使用instanceof可以检测引用数据类型。在PHP中，也有检测数据类型的方法，具体如下： 1、输出变量的数据类型（gettype

• iOS把图片缓存到本地的几种方法(总结)

  把图片缓存到本地，在很多场景都会用到，如果只是存储文件信息，那建一个plist文件，或者数据库就能很方便的解决问题，但是如果存储图片到沙盒就没那么方便了。这里简单介绍两种保存图片到沙盒的方法。 

• Docker容器使用jenkins部署web项目(总结)

  （1）需要安装docker容器，在docker容器内安装jenkins，gogs，tomcat。   新建maven项目，添加findbugs plugin。 使用docker

• 基于并发服务器几种实现方法(总结)

  今天主题是实现并发服务器，实现方法有多种版本，先从简单的单进程代码实现到多进程，多线程的实现，最终引入一些高级模块来实现并发TCP服务器。 说到TCP，想起吐槽大会有个段子提到三次握手，也只有程序

• 超实用的Java快捷键(总结)

  如下所示： Ctrl+1或F2快速修复 Ctrl+D快捷删除行 Shift+Enter 快速切换到下一行，在本行的任何位置都可 Ctrl+F11快速运行代码 Alt+上下键 快速移动行（可

• 浅谈JSP与Servlet传值及对比(总结)

  JSP是Servlet技术的扩展，本质上是Servlet的简易方式，更强调应用的外表表达。 JSP编译后是”类servlet”。 Servlet和JSP最主要的不同点在于，Servlet的应用逻辑

• Java中实现多线程关键词整理(总结)

  Java中的Runable,Callable,Future,FutureTask,ExecutorService,Excetor,Excutors,ThreadPoolExcetor在这里对这些关键

• 读取Java文件到byte数组的三种方法(总结)

  读取Java文件到byte数组的三种方法(总结) ? 1

• java实现二叉树的创建及5种遍历方法(总结)

  用java实现的数组创建二叉树以及递归先序遍历，递归中序遍历，递归后序遍历，非递归前序遍历，非递归中序遍历，非递归后序遍历，深度优先遍历，广度优先遍历8种遍历方式：

• Mysql字符串处理函数详细介绍、总结

  1、简明总结 ASCII(char)　　　　　　　　返回字符的ASCII码值 BIT_LENGTH(str)　　　　　　返回字符串的比特长度 CONCAT(s1,s2…,sn)　　　　 

• 十大java应用服务器(webserver)总结

  java应用服务器(web server)，是指运行java程序的web应用服务器软件，不包括nginx、Apache等通用web服务器软件。 一、Tomcat Tomcat是Apache 软件基

• 精通Java事务编程(9)-总结

  事务作为抽象层，允许应用忽略DB 内部一些复杂并发问题和某些硬件、软件故障，简化应用层的处理逻辑：事务中止（transaction abort），而应用仅需重试。对复杂访问模式，事务可大大减少需要考虑

• 10、DTD 总结

  我们在本教程学习了如何描述 XML 文档的结构 我们学习到了如何使用 DTD 来定义一个 XML 文档的合法元素，以及如何在我们的 XML 内部或者作为一个外部引用来声明 DTD 我们学习了如何为

• 08、XPath 总结

  在这个XPath 基础教程中我们讲解了如何在 XML 文档中查找信息 我们可以使用 XPath 的元素和属性在 XML 文档中进行导航 我们也学习了如何使用 XPath 中内建的某些标准函数 如