二叉树
子节点数<=2
非线性的数据结构
节点和节点的线，叫边
从一个节点到另一个节点的一组边，叫路径
树的层数，叫树的深度
以某种顺序遍历树，叫树的遍历
没有子节点的节点，叫叶子节点
二叉查询树
较小的数，放左节点，较大的数放右节点
二叉查询树的遍历方式：先序、中序、后序
先序：中、左、右
中序：左、中、右
后序：左、右、中
//节点
function Node(data) {
this.data = data
this.left = null
this.right = null
this.count = 1
this.show = () => {
return this.data
}
}
//二叉树查询树
function bst() {
this.root = null
this.insert = insert
this.remove = remove
this.find = find
this.len = 0
}
// bst的插入节点的方法
function insert(data) {
const newNode = new Node(data)
this.len++
if (this.root == null) {
this.root = newNode
return
}
let current = this.root
while (true) {
if (data < current.data) {
if (current.left == null) {
current.left = newNode;
break;
}
current = current.left
} else {
if (current.right == null) {
current.right = newNode;
break;
}
current = current.right
}
}
}
//bst的删除节点的方法
function remove(data) {
removeNode(this.root, data)
}
function removeNode(node, data) {
if (node.data == null) {
return null
}
if (data == node.data) {
//1.无子节点
if (node.left == null && node.right == null) {
return null
}
//无左子节点
if (node.left == null) {
return node.right
}
//无右子节点
if (node.right == null) {
return node.left
}
//有左右节点
//找右节点树的最小，作为替换节点
const rightMinNode = getMin(node.right)
node.data = rightMinNode.data
node.right = removeNode(node.right, rightMinNode.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
}
}
//查找
function find(data) {
if (this.root == null) return
let current = this.root
while (current) {
if (data == current.data) {
return current
} else if (data < current.data) {
if (!current.left) return null
current = current.left
} else {
if (!current.right) return null
current = current.right
}
}
}
//以数组为源数据创建bst，重复项计数
function createTreeCount(arr) {
const tree = new bst()
arr.forEach(val => {
const node = tree.find(val)
if (node) {
node.count++
} else {
tree.insert(val)
}
});
return tree
}
//以数组为源数据创建bst，不查重
function createTree(arr) {
const tree = new bst()
arr.forEach(val => {
tree.insert(val)
});
return tree
}
//先序遍历
function preOrder(node) {
if (node != null) {
console.log(node.data + ' ');
preOrder(node.left)
preOrder(node.right)
}
}
//中序遍历
function midOrder(node) {
if (node != null) {
midOrder(node.left)
console.log(node.data + ' ');
midOrder(node.right)
}
}
//后序遍历
function behindOrder(node) {
if (node != null) {
behindOrder(node.left)
behindOrder(node.right)
console.log(node.data + ' ');
}
}
//计算节点数
function countNode(node, count = 0) {
if (node != null) {
count = countNode(node.left, count)
count++;
count = countNode(node.right, count)
}
return count
}
//从 1开始算，找第几大的节点
function findIndex(node, num) {
let current = null
function findN(node, count = 0) {
if (node != null && !current) {
count = findN(node.left, count)
count++;
if (count == num) current = node
count = findN(node.right, count)
}
return count
}
findN(node)
return current
}
//查找最小值
function getMin(node) {
let current = node
while (current.left) {
current = current.left
}
return current
}
//查找最大值
function getMax(node) {
let current = node
while (current.right) {
current = current.right
}
return current
}
//计算边数
function countPath(node) {
const count = countNode(node, 0)
return count >= 0 && count - 1 || 0
}
// 所有的叶子节点
function findLeafNode(node, arr = []) {
if (node != null) {
if (node.left == null && node.right == null) {
arr.push(node)
}
if (node.left) {
findLeafNode(node.left, arr)
}
if (node.right) {
findLeafNode(node.right, arr)
}
}
return arr
}
const arr = [3, 5, 22, 6, 14, 7, 1, 8, 35, 45, 26, 15, 95, 14, 0, 44, 66, 88]
const tree1 = createTree(arr)
const tree2 = createTreeCount(arr)
midOrder(tree2.root)
const number = 11
console.log('第'+ number+'大的节点：', findIndex(tree2.root, number));
// const num = countNode(tree1.root)
// console.log('tree.length', num);
// console.log('tree.length', tree1.len);
// console.log('tree2.length', tree2.len);
// const min = getMin(tree1.root)
// console.log('min', min);
// const max = getMax(tree1.root)
// console.log('max', max);
// tree1.remove(22)
// midOrder(tree1.root)
// const leaves = findLeafNode(tree1.root)
// console.log('leaves',leaves);
// console.log('tree1.root', tree1.root);
// console.log('95', tree1.find(95));