概念与编码实现

二叉树的定义：

1. 可以没有根结点，作为一颗空树
2. 如果不是空树，必须由根结点，左子树和右子树组成，而且左右子树都是二叉树

js 中使用对象来实现二叉树，由三部分组成：

1. 数据域
2. 左结点引用（左子树根结点）
3. 右结点引用（右子树根结点）

在创建二叉树结点时，先把左右结点引用预置为 null

// 二叉树结点构造函数
function TreeNode(val){
    this.val = val
  this.left = this.right = null
}
// 创建一个结点
nodeA = new TreeNode("A")

一个二叉树的结构如图：

这个二叉树的对象表示和创建过程如下：

// 对象表示
const tree = {
  val:'A',
  left:{
    val: 'B',
    left:{
      val: 'D',
    },
    right:{
      val:'E'
    }
  },
  right:{
    val: 'C',
    right: {
      val: 'F'
    }
  }
}
// 创建：先创建结点，再连接引用
function TreeNode(val){
  this.val = val
  this.left = this.right = null
}
const root = new TreeNode('A')
const B = new TreeNode('B')
const C = new TreeNode('C')
const D = new TreeNode('D')
const E = new TreeNode('E')
const F = new TreeNode('F')
root.left = B
root.right = C
B.left = D
B.right = E
C.right = F