什么是二叉树？
二叉树是树的一种特殊形式，这种树的每个节点最多有2个孩子节点（也可能只有1个或者没有）。二叉树节点的两个孩子节点，一个被称为左孩子，一个被称为右孩子。这两个孩子节点的顺序是不能颠倒或混淆的。
二叉树有两种特殊形式，一个叫满二叉树，另一个叫完全二叉树
- 满二叉树：指树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上
- 完成全叉树：完成二叉树和满二叉树有点像，只不过满二叉树要求所有节点（除叶子节点）都是满的，而完全二叉树只需保证最后一个节点之前的节点都齐全即可
我们知道，所有的数据结构（逻辑结构，包括栈、队列、树、图等）都可以由两种物理结构来实现：数组和链式存储结构
如果是链式存储，其实很容易实现一棵树：
- 有一个data用于存储当前节点值
- 有一个左指针，指向它的左孩子节点
- 有一个右指针，指向它的右孩子节点
// 定义一个二叉树节点，节点包括自身值，一个左指针和一个右指针
function TreeNode(val) {
this.data = val;
this.left = null; // 指向它的左孩子节点
this.right = null; // 指向它的右孩子节点
}
二叉树包含许多特殊形式，每一种形式自己的作用，但是其最主要的应用还在于进行查找操作和维持相对顺序这两方面，比如下面这种二叉查找树：
- 二叉查找树
- 如果左子树不为空，则左子树上的所有节点的值都小于根节点的值
- 如果右子树不为空，则右子树上的所有节点的值都大于根节点的值
- 左、右子树也都是二叉查找树
如其名，其主要作用就是用于查找操作。
二叉树的遍历
二叉树遍历一般归为两大类：深度优先遍历（前、中、后序遍历）和广度优先遍历（层序遍历）
深度优先遍历
深度优先遍历中的前、中、后序的说法，其实是相对于根节点的遍历顺序而言的。先左后右的相对顺序是不会变的，前中后的差别在于根节点的位置在哪，如前序，根在前，后左再右；如中序，左在前，根在中，右在后；如后序，根在最后，前面自然是左右。这样，是不是就很清楚容易记得三者的区别。
- 前序遍历，输出顺序为：根节点 => 左子树 => 右子树
- 中序遍历，输出顺序为：左子树 => 根节点 => 右子树
- 后序遍历，输出顺序为：左子树 => 右子树 => 根节点
注意，这里的左子树和右子树是一个集合，而非单个孩子节点，而是除了根节点和另一边子树外的所有节点的集合。而左子树和右子树中的遍历，输出顺序也是如此的。
按照前序遍历的思想生成一个二叉树
给定一个序列，先生成根节点，再遍历生成左子树的所有节点，最后再生成右子树的所有节点
// javascript实现二叉树
// 创建一个二叉树
function createTree(nodeList) {
// 检测输入是否为一个数组
if(Array.isArray(nodeList)) {
const len = nodeList.length
if(!len) return;
else {
// 获取最前头的节点值
const data = nodeList.shift()
// 构建二叉树
let node = null;
// 如果值不为null，则递归为此节点生成左子树和右子树
if(data) {
node = new TreeNode(data)
node.left = createTree(nodeList)
node.right = createTree(nodeList)
}
return node
}
}else{
throw Error("请输入一个节点序列")
}
}
const tree = createTree([1,2,null,null,3,4,5,null,7])
console.log(tree);
// TreeNode {
// data: 1,
// left: TreeNode { data: 2, left: null, right: null },
// right:
// TreeNode {
// data: 3,
// left: TreeNode { data: 4, left: [TreeNode], right: undefined },
// right: undefined } }
递归实现深度优先遍历（前中序）
// 二叉树前序遍历
function preOrderTraveral(nodeTree) {
if(!nodeTree) return;
else {
console.log(nodeTree.data);
preOrderTraveral(nodeTree.left)
preOrderTraveral(nodeTree.right)
}
}
console.log("前序遍历：");
console.log(preOrderTraveral(tree)); // 1, 2, 3, 4, 5, 7
// 二叉树中序遍历
function middleOrderTreveral(nodeTree) {
if(!nodeTree) return;
else {
middleOrderTreveral(nodeTree.left)
console.log(nodeTree.data);
middleOrderTreveral(nodeTree.right)
}
}
console.log("中序遍历：");
console.log(middleOrderTreveral(tree)); // 2, 1, 5, 7, 4, 3
// 二叉树后序遍历
function postOrderTreveral(nodeTree) {
if(!nodeTree) return;
else {
postOrderTreveral(nodeTree.left)
postOrderTreveral(nodeTree.right)
console.log(nodeTree.data);
}
}
console.log("后序遍历：");
console.log(postOrderTreveral(tree)); // 2, 7, 5, 4, 3, 1
使用栈实现深度优先遍历
绝大多数可以用递归解决的问题，其实都可以用另一种数据结构来解决，即栈。因为递归和栈都有回溯的特性。
使用递归的方式，真的是有手就行，所以面试官往往也不会考查我们递归的实现方式，而是会更倾向于考查我们栈的实现方式。
/*
栈实现深度优先遍历
*/
// 栈方式实现前序遍历
function stackPreTravel(nodeTree) {
if(!nodeTree) return;
let stack = []
let node = nodeTree
// 如果节点不为空，且栈不为空，则继续循环
while(node || stack.length) {
// 如果节点不为空，则继续向左遍历
while(node) {
console.log(node.data);
// 将存在的左节点入栈
stack.push(node)
node = node.left
}
// 当左节点为空时，但栈不为空，遍历右节点子树
if(stack.length) {
node = stack.pop()
node = node.right;
}
}
}
// console.log(stackPreTravel(tree));
// 栈方式实现中序遍历
function stackMiddleTravel(nodeTree) {
if(!nodeTree) return;
let stack = []
let node = nodeTree
while(node || stack.length) {
while(node) {
stack.push(node)
node = node.left
}
if(stack.length) {
node = stack.pop()
console.log(node.data);
node = node.right
}
}
}
// console.log(stackMiddleTravel(tree));
广度优先遍历
如其名字的含义，广度优先遍历，是将树按层级来一层一层遍历的，每一层遍历的顺序是从左往右。因为广度优先是要按顺序排序的，所以与队列的特性是相似的，即先进先出。所以一般使用队列来实现广度优先遍历。
/*
广度优先遍历：使用队列实现
*/
function levelOrderTravel(nodeTree) {
// 如果树为空，结束
if(!nodeTree) return;
// 初始化一个队列
let queue = []
// 将根节点入队
queue.push(nodeTree)
let node = null
// 只要队列不为空，继续循环
while(queue.length) {
// 按顺序取出队列中最早入队的节点
node = queue.shift()
console.log(node.data);
// 如果出队节点存在左孩子，就将其左孩子入队
if(node.left) {
queue.push(node.left)
}
// 如果出队节点存在右孩子，就将其右孩子入队
if(node.right) {
queue.push(node.right)
}
}
}
console.log("广度优先遍历-使用队列实现:");
console.log(levelOrderTravel(tree));
