# 二叉树概述

# 二叉树概述

二叉树是非常基础并且是一种非常重要的数据结构, 正和它的名字一样, 二叉树的每个节点最多有两个子树.

我们可以先来看下面的这颗二叉树, 为了方便,我这里将leftL表示, rightR表示:

tree1

# 二叉树与JS

上面的二叉树可以用我们JavaScript的对象来进行表示, 相信大家很容易就能看懂:

var tree = {
    value: "Root",
    left: {
        value: 'L',
        left: {
            value: 'LL'
        },
        right: {
            value: 'LR'
        }
    },
    right: {
        value: 'R',
        left: {
            value: 'RL'
        },
        right: {
            value: 'RR'
        }
    }
}

当前节点的值存放到value这个属性中, 左(右)子树存放到left(right)中.

这样我们很容易就能写出数组[1, null, 2, 3]的二叉树:

img6

# 定义一个二叉树的节点类

通过上面的JS对象,让我们来写一个可以生成单个节点的类:

// 定义一个二叉树的节点类
class Node {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

现在让我们用这个类来生成一颗简单的二叉树吧:

const tree = new Node(
  'Root',
  new Node(
    'L',
    new Node('LL'),
    new Node('LR')
  ),
  new Node(
    'R',
    new Node('RL'),
    new Node('RR')
  )
)
console.log(tree)

(这棵树在后面都会用到,大家知道后面案例的tree表示的是它就行了)

# 二叉搜索树

二叉搜索树(也叫二叉查找树)的特点:

  • 左子树上所有节点的值必定全部小于根节点的值
  • 右子树上所有节点的值必定全部大于根节点的值
  • 左子树和右子树也分别为二叉搜索树

例如二叉搜索树:

const root = new Node(
  2,
  new Node(1),
  new Node(
    5,
    new Node(4),
    new Node(6)
  )
);
[左子树][][右子树]
// 对应为:
[1] [2] [4 5 6]

非二叉搜索树:

const root = new Node(
	2,
	new Node(3),
	new Node(4)
)
[左子树][][右子树]
// 对应为:
[3] [2] [4]
阅读全文