JavaScript算法套路之二叉树理论基础

学习算法，数据结构必须了解。据说二叉树是在学习算法路上的第一道要突破的屏障。那么就来总结一下二叉的一些简单理论：

二叉树的定义

二叉树是树的一种，二叉树最多只能有俩个节点，分为左孩子和右孩子。

二叉树的分类

• 满二叉树
• 完全二叉树
• 二叉搜索树
• 平衡二叉搜索树
  …
  等等，种类很多，这里就不一一细数。

二叉树的存储方式

二叉树的存储方式，可以是链式存储，也可以是顺序存储。

链式存储

链式存储就是用指针，就是类似于链表，但是二叉树会比链表多一个指针，树有俩个指针，左和右，分别指向自己的左孩子和右孩子。

顺序存储

顺序存储就是用数组的方式来存储二叉树。一层一层的存储。

     1
  /     \
  2       5
/   \      \
3    4       6

用数组的方式存储就是：

const tree = [1, 2, 5, 3, 4, null, 6];

二叉树的遍历

二叉树的遍历方式有俩种：

1. 深度优先：先往深了走，遇到叶子节点再往回走（中间节点的遍历顺序）
   • 前序遍历
   • 中序遍历
   • 后续遍历
     实现深度优先的遍历，我们一般都是通过递归的方式实现的。
2. 广度优先：一层一层的遍历
   • 层序遍历
     实现广度优先的遍历一般都是通过队列的方式实现的，因为队列先进先出的特点能一层一层的遍历二叉树。
     接下来，就是我们如何实现了。。。

JavaScript创建二叉查找树

function TreeNode (data, left, right) {
	this.val = data;
	this.left = left;
	this.right = right;
}

function BST() {
	//	保存二叉树的节点
	this.root = null;
	this.insert = insert;
}
function insert(data) {
	let node = new TreeNode(data, null, null);
	if (!this.root) {
		this.root = node;
	} else {
		let current = this.root;
		let parent = null;
		while (true) {
			parent = current
			if (data < current.val) {
				current = current.left;
				if (current === null) {
					parent.left = node;
					break;
				}
			} else {
				current = current.right;
				if (current === null) {
					parent.right = node;
					break;
				}
			}
		}
	}
}