使用JavaScript完成二叉树的一些基本操作

YPHP 发布于2019-08-23 12:48 / 1026人阅读

摘要：另外，由于篇幅有限，本篇的重点在于二叉树的常见算法以及实现。常见的二叉树实现代码之前写过相关的文章，是关于如何创建及遍历二叉树的，这里不再赘述。同时我们注意到，在二叉树深度比较大的时候，我们光是比较左右是不够的。

本篇为复习过程中遇到过的总结，同时也给准备面试的同学一份参考。另外，由于篇幅有限，本篇的重点在于二叉树的常见算法以及实现。

常见的二叉树实现代码

之前写过相关的文章，是关于如何创建及遍历二叉树的，这里不再赘述。提供链接给各位感兴趣的小伙伴，点此跳转

翻转二叉树

对于一棵二叉树，翻转它的左右子树，如下图所示：

下面来分析具体的实现思路：

对于根结点为空的情况

这种情况需要排除，因为null不是一个对象，不可能存在左右子树并且可以翻转的情况

对于一棵只有一个根结点的二叉树

emmm，这种情况也可以翻转，因为此时根结点左右子树为null，交换左右子树其实也就是在交换两个null，理论上是翻转了，但实际上我们看到的和没有翻转之前的结果是一样的

对于一棵具有两个或两个以上结点的二叉树，此时二叉树可以表示为如下的图像：

可以看出，无论是只有左子树还是只有右子树都可以进行翻转。这句话等价于，为空的子树可以和不为空的子树进行交换，也就是不对为空的子树进行特殊处理

分析过程

其实这样我们还是不知道二叉树是如何翻转的，我们可以用第一张图的二叉树为例子，看一下翻转的具体过程。

首先我们需要对根结点进行判空处理，在根结点不为空的情况下存在左右子树（即使左右子树为空），然后交换左右子树；

把根结点的左子树当成左子树的根结点，对当前根结点进行判空处理，不为空时交换左右子树;

把根结的右子树当成右子树的根结点，对当前根结点进行判空处理，不为空时交换左右子树;

重复步骤2、3，最后二叉树变为原来的镜像结构,结果可以参考文章第一张示意图。

示例代码

根据上面的推理过程我们可以得出如下的代码：

function reverseTree(root){
    if( root !== null){
        [root.left, root.right] = [root.right, root.left]
        reverseTree(root.left)
        reverseTree(root.right)
    }
}

虽然推理过程比较复杂（也可能是写的比较啰嗦。。），但是仔细观察代码，这和遍历的代码似乎也没多大差别，只是把输出结点变为了交换结点。

判断二叉树是否完全对称

一棵左右完全对称的二叉树是这样的：

那到底如何判断呢？

根结点为空时，此时为一棵空二叉树，满足对称条件（-_-||）

只有一个根结点时，左右子树都为null，满足左右对称条件

只有两个结点时，此时左右子树必定有一个为空，不可能存在对称的情况

结点数在三个及三个以上时，二叉树有对称的可能。

按照我们正常的思维，看对称与否，首先看左边，然后看右边，最后比较左右是否相等。同时我们注意到，在二叉树深度比较大的时候，我们光是比较左右是不够的。可以观察到，我们比较完左右以后还需要比较左的左和右的右，比较左的右和右的左

分析过程

这么看是比较绕，接下来我们来看图分析：

先比较根结点左右孩子

将左子树根结点的左孩子与右子树根结点的右孩子进行比较

将左子树根结点的右孩子与右子树根结点的左孩子进行比较

重复以上过程...

示例代码

function isSymmetrical(pRoot)
{
    // write code here
    if(!pRoot){
        return true
    }
    return funC(pRoot.left, pRoot.right)
}
 
function funC(left, right){
     
    if(!left){
        return right === null
    }
     
    if(!right){
        return false
    }
     
    if(left.val !== right.val){
        return false
    }
     
    return funC(left.right, right.left) && funC(left.left, right.right)
}

求二叉树的深度 分析过程

只有一个根结点时，二叉树深度为1

只有左子树时，二叉树深度为左子树深度加1

只有右子树时，二叉树深度为右子树深度加1

同时存在左右子树时，二叉树深度为左右子树中深度最大者加1

示例代码

function deep(root){
    if(!root){
        return 0
    }
    let left = deep(root.left)
    let right = deep(root.right)
    return left > right ? left + 1 : right + 1
}

求二叉树的宽度

二叉树的宽度是啥？我把它理解为具有最多结点数的层中包含的结点数，比如下图所示的二叉树，其实它的宽度就是为4：

分析过程

根据上图，我们如何算出二叉树的宽度呢？其实有个很简单的思路：

算出第一层的结点数，保存

算出第二层的结点数，保存一二层中较大的结点数

重复以上过程

示例代码

根据分析过程，我们可以利用队列这种数据结构来实现这个算法，代码如下：

function width(root){
    if(!root){
        return 0
    }
    let queue = [root], max = 1, deep = 1
    while(queue.length){
        while(deep--){
            let temp = queue.shift()
            if(temp.left){
                queue.push(temp.left)
            }
            if(temp.right){
                queue.push(temp.right)
            }
        }
        deep = queue.length
        max = max > deep ? max : deep
    }
    return max
}

重建二叉树 常见的遍历

前序遍历：

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。

中序遍历：

中序遍历首先访问左子树然后遍历根节点，最后遍历右子树。

后序遍历：

后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点

题目描述

根据前序遍历产生的序列和中序遍历产生的序列生成一颗二叉树

思路分析

假如有这么一棵二叉树：

可以看出它前序遍历序列为：8 6 5 7 10 9 11，中序遍历序列为：5 6 7 8 9 10 11
其中有个很明显的特征，根结点的值为前序遍历序列的第一个值，而且我们在中序遍历序列中很容易看出，根结点左右两边的结点分别为构成左子树和右子树的结点，所以我们可以得到一种解决问题的思路：

获取前序遍历的第一个值，构建根结点

生成左子树的前序遍历序列和中序遍历序列

生成右子树的前序遍历序列和中序遍历序列

重复以上过程...

示例代码

function reConstructBinaryTree(pre, vin)
{
    if(!pre || !vin || !pre.length || !vin.length){
        return null
    }
    let root = new TreeNode(pre[0]),
        tIndex = vin.indexOf(pre[0]),
        leftIn = [],leftPre = [],rightIn = [],rightPre = []
    
    for(let i = 0; i < tIndex; i++){
        leftIn.push(vin[i])
        leftPre.push(pre[i+1])
    }
    for(let i = tIndex+1; i < pre.length; i++){
        rightIn.push(vin[i])
        rightPre.push(pre[i])
    }
    //递归
    root.left = reConstructBinaryTree(leftPre, leftIn)
    root.right = reConstructBinaryTree(rightPre, rightIn)
    return root
}

以上思路、代码有错漏请在评论区指出！

总结

代码部分来自牛客网--剑指offer，相应的题目也都可以在上面找到。

扫描下方的二维码或搜索「tony老师的前端补习班」关注我的微信公众号，那么就可以第一时间收到我的最新文章。

云服务器 GPU云服务器二叉树的遍历二叉树的存储二叉树的存储结构 java二叉树的构建

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/99012.html

学习javascript数据结构(四)——树

摘要：原文博客地址学习数据结构四树知乎专栏简书专题前端进击者知乎前端进击者简书博主博客地址的个人博客人之所能，不能兼备，弃其所短，取其所长。通常子树被称作左子树和右子树。敬请期待数据结构篇最后一篇文章学习数据结构五图参考文章树数据结构二叉树前言总括：本文讲解了数据结构中的[树]的概念，尽可能通俗易懂的解释树这种数据结构的概念，使用javascript实现了树，如有纰漏，欢迎批评指正。 ...

Dean 2019-08-20 13:47 评论0 收藏0
LeetCode 之 JavaScript 解答第94题 —— 二叉树的中序遍历

摘要：小鹿题目二叉树中序遍历给定一个二叉树，返回它的中序遍历。通常递归的方法解决二叉树的遍历最方便不过，但是我还是喜欢增加点难度，用一般的迭代循环来实现。 Time：2019/4/25Title:Binary Tree Inorder TraversalDifficulty: MediumAuthor:小鹿题目：Binary Tree Inorder Traversal（二叉树中序遍历...

Jason 2019-08-23 17:19 评论0 收藏0
使用javascript实现排序二叉树（2）

摘要：使用实现排序二叉树上一篇文章我们构造了基本的一个排序二叉树的数据结构，但是仅仅是定义了一个方法去创建二叉排序树，今天我们来给我们的数据结构添加一些遍历的功能。使用javascript实现排序二叉树（2）上一篇文章我们构造了基本的一个排序二叉树的数据结构，但是仅仅是定义了一个insert方法去创建二叉排序树，今天我们来给我们的数据结构添加一些遍历的功能。二叉树的三种遍历方式（以根节...

susheng 2019-08-23 11:33 评论0 收藏0
使用javascript实现排序二叉树（1）

摘要：使用实现排序二叉树排序二叉树的定义二叉树的基础上，左节点比父节点要小，右节点比父节点要大的二叉树，叫排序二叉树。下期内容实现排序二叉树的中序前序后续遍历实现二叉树的节点查找功能实现排序二叉树的删除节点功能应用排序二叉树实现一个小游戏使用javascript实现排序二叉树（1）排序二叉树的定义：二叉树的基础上，左节点比父节点要小，右节点比父节点要大的二叉树，叫排序二叉树。 show...

Caicloud 2019-08-23 11:29 评论0 收藏0
JS递归与二叉树的遍历

摘要：貌似大部分语言中的递归都差不多，之所以在标题加是因为搜了下后感觉网上用来描述这概念的不多，简单地说递归就是函数调用自己的过程。貌似大部分语言中的递归都差不多，之所以在标题加JS是因为搜了下后感觉网上用js来描述这概念的不多，简单地说递归就是函数调用自己的过程。下面的栗子可以很直观地展示递归的执行过程： function rec(x){ if(x!==1){ console....

church 2019-08-21 10:48 评论0 收藏0