二叉树
定义：二叉树是树的一种特殊情况，每个节点最多有有两个子女，分别称为该节点的左子女和右子女，就是说，在二叉树中，不存在度大于2的节点。二叉搜索树(BST)是二叉树的一种，但是它只允许你在左侧节点存储(比父节点)小的值， 在右侧节点存储(比父节点)大(或者等于)的值。二叉搜索树的查找效率取决于树的高度，查找所需的最大次数等同于二叉查找树的高度
特点:
- 同一层，数值从左到右依次增加
- 以某一祖先节点为参考，该节点左侧值均小于节点值，右侧值均大于节点值
- 在二叉树的第i(i>=1)层，最多有2^(i-1)个节点
- 深度为k(k>=1)的二叉树，最少有k个节点，最多有2^k-1个节点
- 对于一棵非空二叉树，叶节点的数量等于度为2的节点数量加1
完全二叉树：在完全二叉树当中，除了最后一层之外，所有层的节点都是满的，且最后一层的节点也是从左到右的。优先填满左边的节点。二叉搜索树的中序遍历一定是从小到大排序的。
1.叶子结点只能出现在最下俩层
2.最下层的叶子一定集中在左部连续位置
3.倒数二层，若有叶子结点，一定都在右部连续位置
4.如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况(度为分支的数目)
5.同样结点数的二叉树，完全二叉树的深度最小
满二叉树：深度为k的满二叉树，是有2^k-1个节点的二叉树，每一层都达到了可以容纳的最大数量的节点。
基础方法： - insert(key): 向树中插入一个新的键；
- inOrderTraverse: 通过中序遍历方式遍历所有节点
- preOrderTraverse: 通过先序遍历方式遍历所有节点
- postOrderTraverse: 通过后序遍历方式遍历所有节点
- getMin: 返回树中最小的值/键
- getMax: 返回树中最大的值/键
- find(key): 在树中查找一个键，如果节点存在则返回该节点不存在则返回null；
- remove(key): 从树中移除某个键
- 深度优先遍历和广度优先遍历
二叉平衡树：AVL树：https://zhuanlan.zhihu.com/p/56066942
实现二叉树的相关操作:https://www.jb51.net/article/207062.htm
class Node { // 创建节点
constructor(data) {
this.root = this;
this.data = data;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null //初始化根节点
}
// 插入节点
insert(data) {
const newNode = new Node(data);
const insertNode = (node, newNode) => {
if (newNode.data < node.data) { // 如果插入的节点值比父节点小则插入到左节点上反之则插入到右节点上 if (node.left === null) { node.left = newNode } else { insertNode(node.left, newNode) // 递归找下一层的左侧节点（重点） } } else { if (node.right === null) { node.right = newNode; } else { insertNode(node.right, newNode) } } } if (!this.root) { this.root = newNode; } else { insertNode(this.root, newNode); } } // 中序遍历所有节点（左根右） inOrderTraverse() { let backs = []; const callback = data => {
return data
}
const inOrderNode = (node, callback) => {
if (node !== null) {
inOrderNode(node.left, callback); // 递归遍历出左节点
backs.push(callback(node.data)); // 将值push到数组里
inOrderNode(node.right, callback) // 递归遍历出右节点
}
}
inOrderNode(this.root, callback)
return backs
}
// 先序遍历所有节点（根左右）
preOrderTraverse() {
let backs = [];
const callback = data => {
return data
}
const inOrderNode = (node, callback) => {
if (node !== null) {
backs.push(callback(node.data)); // 将值push到数组里
inOrderNode(node.left, callback); // 递归遍历出左节点
inOrderNode(node.right, callback) // 递归遍历出右节点
}
}
inOrderNode(this.root, callback)
return backs
}
// 后序遍历所有节点（左右根）
postOrderTraverse() {
let backs = [];
const callback = data => {
return data
}
const inOrderNode = (node, callback) => {
if (node !== null) {
inOrderNode(node.left, callback); // 递归遍历出左节点
inOrderNode(node.right, callback) // 递归遍历出右节点
backs.push(callback(node.data)); // 将值push到数组里
}
}
inOrderNode(this.root, callback)
return backs
}
//查找最小值
// 这里可以利用search 查找指定节点下面的最小值
min(node) {
const minNode = (node) => {
return node ? (node.left ? minNode(node.left) : node) : null
}
return minNode(node || this.root)
}
// 查找最大值
max(node) {
const maxNode = (node) => {
return node ? (node.right ? maxNode(node.right) : node) : null
}
return maxNode(node || this.root)
}
//查找特定值
search(data) {
const searchNode = (node) => {
if (node === null) return false;
if (node.data === data) {
return node;
}
return searchNode(data < node.data ? node.left : node.right, data) } return searchNode(this.root, data) } //从树中移除某个键 remove(data) { // 删除节点复杂之处在于每次删除节点时候二叉树要根据不同情况改变结构 同样也需要递归 const removeNode = (node,data) => {
if(node === null) return null;
if(node.data === data){
if(node.left === null && node.right === null) return null;
if(node.left === null) return node.right;
if(node.right === null) return node.left;
if(node.left !==null && node.right !==null){
let _node = this.min(node.right);
node.data = _node.data;
node.right = removeNode(node.right,data);
return node
}
} else if(data < node.data){ node.left=removeNode(node.left,data); return node } else { node.right=removeNode(node.right,data); return node } }; return removeNode(this.root,data) } } const tree = new BinarySearchTree(); tree.insert(11); tree.insert(7); tree.insert(5); tree.insert(3); tree.insert(9); tree.insert(8); tree.insert(10); tree.insert(13); tree.insert(12); tree.insert(14); tree.insert(20); tree.insert(18); tree.insert(25); console.log(tree.inOrderTraverse()) console.log(tree.preOrderTraverse()) console.log(tree.postOrderTraverse()) console.log(tree.min()); console.log(tree.max()); console.log(tree.search(20)) console.log(tree.remove(7)) 
投递美团等公司10个岗位 >
