什么是二叉树?

菜园前端
• 阅读 460

原文链接:https://note.noxussj.top/?source=helloworld


什么是二叉树?

树中每个节点最多只能有两个子节点,在 JavaScript 中一般都是通过 Object 来模拟二叉树。

常用操作

  • 前序遍历
  • 中序遍历
  • 后序遍历

前序遍历

根左右。

口诀:

  1. 访问根节点
  2. 对根节点的左子树进行前序遍历
  3. 对根节点的右子树进行前序遍历

什么是二叉树?

通过递归方式实现

function preorder(root) {
    if (!root) return

    console.log(root.val)
    preorder(root.left)
    preorder(root.right)
}

通过迭代方式实现

function preorder(root) {
    if (!root) return

    const stack = [root]

    while (stack.length) {
        const n = stack.pop()

        console.log(n)
        if (n.right) stack.push(n.right)
        if (n.left) stack.push(n.left)
    }
}

中序遍历

左根右。

口诀:

  1. 对根节点的左子树进行中序遍历
  2. 访问根节点
  3. 对根节点的右子树进行中序遍历

什么是二叉树?

通过递归方式实现

function inorder(root) {
    if (!root) return

    inorder(root.left)
    console.log(root.val)
    inorder(root.right)
}javascript

通过迭代方式实现

function inorder(root) {
    if (!root) return

    const stack = [root]

    while (stack.length) {
        const n = stack.pop()

        console.log(n)
        if (n.right) stack.push(n.right)
        if (n.left) stack.push(n.left)
    }
}

后序遍历

左右根。

口诀:

  1. 对根节点的左子树进行后序遍历
  2. 对根节点的右子树进行后序遍历
  3. 访问根节点

什么是二叉树?

通过递归方式实现

function postorder(root) {
    if (!root) return

    postorder(root.left)
    postorder(root.right)
    console.log(root.val)
}

通过迭代方式实现

function postorder(root) {
    if (!root) return

    const outputStack = []
    const stack = [root]

    while (stack.length) {
        const n = stack.pop()

        outputStack.push(n)
        if (n.left) stack.push(n.left)
        if (n.right) stack.push(n.right)
    }

    while (outputStack.length) {
        const n = outputStack.pop()
        console.log(n.val)
    }
}
点赞
收藏
评论区
推荐文章
白茶清欢 白茶清欢
3年前
js实现二叉树、二叉查找树
树是一种数据结构,该章节讨论二叉树(二叉树的每个节点的子节点不允许超过两个),二叉树中有又分为完全二叉树和不完全二叉树.....不在本章节赘述相关概念,感兴趣可以去查阅《数据结构》。你将会获得:1.如何使用js实现二叉查找树。2.学会前、中、后序遍历。3.了解相关实现原理阅读时长5min,可选择直接调试代码特点    二叉查找树中序遍历后
九路 九路
3年前
前端学数据结构与算法:二叉树的四种遍历方式及其应用
前言上一章我们从0到1的实现了一颗二叉搜索树,以及理解了二叉搜索树的特性与基本操作,这一章介绍关于二叉树的更多操作,也就是树的遍历,对树的每个节点进行访问。主要包括前序遍历、中序遍历、后序遍历、层序遍历,前面三种也叫深度优先遍历(DFS),最后的层序遍历也叫广度优先遍历(BFS),理解这四种遍历方式的不同,再遇到树相关的算法问题时,也就能更加游刃有余。这
Wesley13 Wesley13
3年前
B树与B+树的区别?
1.B树简介B树是一种多路平衡搜索树。它由二叉树变换而来的。定义如下:1.1每个节点最多有m1个关键字1.2根节点最少有1个关键字1.3非根节点至少有m/2个关键字1.4每个节点的关键字都是按照从小到大的顺序排列,每个关键字的左子树中的关键字都小于它,而右子树中所有关键字都大于它。1.5所有的叶子节点都处于同
Wesley13 Wesley13
3年前
JAVA递归实现线索化二叉树
JAVA递归实现线索化二叉树基础理论首先,二叉树递归遍历分为先序遍历、中序遍历和后序遍历。先序遍历为:根节点左子树右子树中序遍历为:左子树根节点右子树后序遍历为:左子树右子树根节点(只要记住根节点在哪里就是什么遍历,且都是先左再右)线索化现在有这么一棵二叉树,它的数据结
Wesley13 Wesley13
3年前
Java实现二叉树的前序、中序、后序、层序遍历(非递归方法)
Java实现二叉树的前序、中序、后序、层序遍历(非递归方法)(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fwww.cnblogs.com%2Fliuyang0%2Fp%2F6271331.html)
Wesley13 Wesley13
3年前
PHP数据结构与算法:二叉树
一、定义二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(leftsubtree)和“右子树”(rightsubtree)。二、特性1.在二叉树的第i层上至多有2^(i1)个结点(i0)2.深度为k的二叉树至多有2^k1个结点(k0)3.对于任意一棵二叉树,如果其叶结点数为N0,而
Wesley13 Wesley13
3年前
04.重建二叉树 (Java)
题目描述输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。(https://www.oschina.net/action/GoToLink?urlht
Wesley13 Wesley13
3年前
6.重建二叉树(代码未完成)
 题目:输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建出图2.6所示的二叉树并输出它的头结点。!(https://static.oschina.net/uploads
Wesley13 Wesley13
3年前
JZ18 二叉树镜像
JZ18二叉树镜像题目操作给定的二叉树,将其变换为源二叉树的镜像。思路先遍历,节点入栈,再依次出栈调换左右节点遍历的过程中调换左右节点代码coding:utf8classTreeNode:def__init__
菜园前端 菜园前端
1年前
什么是堆?
原文链接:什么是堆?堆是一种特殊的完全二叉树。完全二叉树的含义就是每层节点都完全填满,除了最后一层外只允许最右边缺少若干个节点。在JavaScript中通常用数组表示堆(按照广度优先遍历顺序)。最大堆最小堆特性所有的节点都大于等于它的子节点(最大堆)或者所