[数据结构与算法]JavaScript创建与遍历二叉树

二叉树可以算得上是数据结构和算法的必学项，很多关于树的算法题给的输入直接就是树结构，关于怎么构建一颗二叉树很多关于数据结构的树都说烂了。但是大都是基于c语言讲的，这里主要是想总结一下前端人都在用的JavaScript怎么来构建一颗二叉树。

本文章是基于对象结构构建的二叉树，大致的结构也很简单，二叉树的每个节点无非就是三个属性值val、left、right分别代表节点值，左孩子，右孩子。为什么考虑用对象结构在实现二叉树构建而不是数组结构呢？其实是写这个构建之前考虑到树各个节点之前是通过地址连接的，数组是一个连续存储的结构肯定不适合实现树结构。后来写着写着忽然想起来，js的数组是不定长并且可存储的数据类型也不是拱顶的，那这他是怎么做连续存储的，多奇怪。后来查了一下MDN，js的数组并不是真正的数组，它不是连续存储的结构。🤔 啊。。。这，真是我这个前端人的巨大疏忽，实在是数据结构中对数组的介绍和以前学习Java时对数组的了解先入为主、根深蒂固，我真是一名不合格的前端人。不过这里还是使用对象来实现二叉树的创建和遍历，如果大家想自己尝试数组版的也可以尝试一下。

创建二叉树

节点数据结构

上面也说到了是使用对象来做节点结构的，那么具体的节点实现代码就放在下面了。

// 二叉树节点
class TreeNode{
    constructor(val){
        this.val = val
        this.left = this.right = null
    }
}

插入一个子节点

其实创建树的过程就是不断向父节点插入子节点的一个过程，这里分了两个函数来插入子节点，一个是添加左孩子，一个用来添加右孩子

// 插入左孩子
let insertLNode = function(root, data){
    if(data != null){
        root.left = new TreeNode(data)
        return root.left
    }
}

// 插入右孩子
let insertRNode = function(root, data){
    if(data != null){
        root.right = new TreeNode(data)
        return root.right
    }
}

构建一个二叉树

万事俱备，那么我们该怎么创建一个二叉树呢。因为我们要创建的二叉树并不一定是完全二叉树，所以当某个节点没有左孩子或者右孩子时，我们就用null来表示。比如说：1，2，3，4，5，null，6，null，7构成的二叉树是

       1
     /   \
    2	  3
   / \     \
  4	  5		6
 	   \
	    7

其对应的对象结构是

{
  "value": 1,
  "right": {
    "value": 3,
    "right": {
      "value": 6,
      "right": null,
      "left": null
    },
	"left": null
  },
  "left": {
    "value": 2,
    "right": {
      "value": 5,
      "right": null,
      "left": null
    },
	"left": {
      "value": 4,
		"right": {
        	"value": 7,
			"right": null,
			"left": null
      	},
		"left": null
    }
  }
}

那么具体的代码实现是怎样的呢，我们来看代码

// 构建二叉树
let createTree = function(...nodes){
    let root = new TreeNode(nodes[0])
    let result = [], i = 1
    result.push(root)
    while(result.length <= 0){
        let node = result.shift()
        if(node != null){
            if(i < nodes.length){
                result.push(insertLNode(node,nodes[i]));
                result.push(insertRNode(node,nodes[i+1]));
            }
            i+=2
        }
    }
    return root
}

我们来分析一下这段代码
● 首先我们把传入该函数的所有值处理为一个数组，将数组的第一个元素作为根节点，生成一个treeNode，并推入result数组中
● 我们需要给每一个节点插入左右孩子，这里时使用的wihle循环，我们把result作为一个记录全部节点的队列，当为一个节点插入完了左右节点以后就把这个节点取出来，下一个节点作为一下轮的根节点并为其插入左右孩子。那么循环的条件就是全部的节点都已经插入了左右孩子，也就是result中所有的元素都被取出了，result.length <= 0
● i-1记录存放所有节点数据的nodes数组中已经多少节点被插入到这棵树中了，为下一轮根节点插入的数据就要从i开始
● 最开始result中只有一个根节点，取出第一个根节点，我们需要判断每一轮的根节点是否为空，如果为空说明不需要为其插入左右孩子。如果不为空，将nodes数组中的索引为i的数据生成一个节点，并作为本轮根节点的左孩子，i+1的数组生成一个节点，并作为本轮根节点的右孩子。索引值+2，并将该生成的两个节点push如result中，可能作为某轮的根节点。当result长度为0时，说明全部节点都已经遍历过了，二叉树创建结束。

遍历模板

遍历比较简单，这里我们是通过递归来实现的二叉树遍历。当我们把数据操作放在不同的位置上时，就可以得到前中后序遍历这里直接贴代码

// 递归遍历
function tarverse(root){
    // 前序遍历
    root.left ? tarverse(root.left):''
    //中序遍历
    root.right ? tarverse(root.right):''
    //后序遍历
}

全部代码

附上全部代码

// 二叉树节点
class TreeNode{
    constructor(value){
        this.value = value
        this.left = this.right = null
    }
}

// 构建二叉树
let createTree = function(...nodes){
    let root = new TreeNode(nodes[0])
    let result = [], i = 1
    result.push(root)
    while(result.length != 0){
        let node = result.shift()
        if(node != null){
            if(i < nodes.length){
                result.push(insertLNode(node,nodes[i]));
                result.push(insertRNode(node,nodes[i+1]));
            }
            i+=2
        }
    }
    return root
}

// 插入左节点
let insertLNode = function(root, data){
    if(data != null){
        root.left = new TreeNode(data)
        return root.left
    }
}

// 插入右节点
let insertRNode = function(root, data){
    if(data != null){
        root.right = new TreeNode(data)
        return root.right
    }
}

// 递归遍历
function tarverse(root){
    // 前序遍历
    root.left ? tarverse(root.left):''
    //中序遍历
    root.right ? tarverse(root.right):''
    //后序遍历
    console.log(root)

}
let root = createTree(1,2,4,23,null,23,45,3,124,346,null,1,0,124,null)

tarverse(root)