Бинарное дерево и бинарное дерево поиска
Двоичное дерево — это конечное множество из n (n >= 0) узлов, когда множество пусто, оно называется пустым бинарным деревом, когда оно не пусто, оно состоит из корневого узла, левого поддерева и правое поддерево Дерево и правое поддерево также являются бинарными деревьями.
Из этого описания видно, что существует тесная связь между структурой дерева и рекурсией, и эта тесная связь может быть полностью отражена в обходе дерева.
Двоичное дерево поиска, также известное как двоичное дерево поиска, также известное как упорядоченное двоичное дерево, отсортированное двоичное дерево.
Вот некоторые свойства бинарных деревьев поиска, обобщенные в Википедии:
- Если левое поддерево любого узла не пусто, значение всех узлов левого поддерева меньше значения его корневого узла;
- Если правое поддерево любого узла не пусто, значение всех узлов в правом поддереве больше, чем значение его корневого узла;
- Левое и правое поддеревья любого узла также являются соответственно бинарными деревьями поиска;
- Нет узлов с одинаковыми ключами.
Эта реализация немного отличается, правый узел больше или равен родительскому узлу. Однако это не влияет на пример, и его можно легко изменить, чтобы он был больше, чем родительский узел.
Об изучении структур данных и алгоритмов JavaScript (2-е издание)
Тогда я прочитал первое издание этой книги, а недавно планировал сделать обзор структур данных и алгоритмов, поэтому прочитал второе издание.
Это редкая книга о структурах данных и алгоритмах, реализованных на JavaScript, объяснение очень понятное и относительно высокое, но есть и много проблем. Следует сказать, что содержание первой редакции относительно достоверно, а достоверность вновь добавленного содержания второй редакции значительно хуже. В целом, это книга, которая объясняет структуры данных и алгоритмы с очень простого уровня, если вы хотите получить более полные знания, вам все равно нужно читать больше профессиональных материалов.
Реализация ES5 в этой статье относится к этой книге, потому что я думаю, что это более удобная реализация для изучения и понимания, чем некоторые другие реализации, которые я видел. Основываясь на образце кода оригинальной книги, я внес небольшие коррективы. Второе издание этой книги утверждает, что охватывает ES6, но после прочтения я обнаружил, что по крайней мере глава о деревьях не была изменена на реализацию ES6, поэтому я написал ее сам, просто чтобы попрактиковаться.
Кроме того, методы обхода дерева, упомянутые в этой книге, включаютПорядок, предварительный порядок, обратный обход, которые принадлежатобход в глубину. В код этой статьи я добавилобход в ширинутак же какИерархический обход бинарного деревареализация.
Binary Search Tree - ES5
var BinarySearchTree = function() {
var Node = function(key) {
this.key = key;
this.left = null;
this.right = null;
};
var root = null;
var insertNode = function(node, newNode) {
if (newNode.key < node.key) {
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);
}
}
};
var inOrderTraverseNode = function(node, cb) {
if (node !== null) {
inOrderTraverseNode(node.left, cb);
cb(node.key);
inOrderTraverseNode(node.right, cb);
}
};
var preOrderTraverseNode = function(node, cb) {
if (node !== null) {
cb(node.key);
preOrderTraverseNode(node.left, cb);
preOrderTraverseNode(node.right, cb);
}
};
var postOrderTraverseNode = function(node, cb) {
if (node !== null) {
postOrderTraverseNode(node.left, cb);
postOrderTraverseNode
}
};
var levelOrderTraverseNode = function(node, cb) {
if (node === null) {
return null;
}
var list = [node];
while (list.length > 0) {
node = list.shift();
cb(node.key);
if (node.left) {
list.push(node.left);
}
if (node.right) {
list.push(node.right);
}
}
};
var separateByLevelFn = function(node, cb, separator) {
var list = [];
var END_FLAG = 'END_FLAG';
list.push(node);
list.push(END_FLAG);
separator = separator || '---*---';
while (list.length > 0) {
node = list.shift();
// 遇到结束信号，表示已经遍历完一层；若队列中还有元素，说明它们是刚刚遍历完的这一层的所有子元素。
if (node === END_FLAG && list.length > 0) {
list.push(END_FLAG);
cb(separator);
} else {
cb(node.key);
if (node.left) {
list.push(node.left)
}
if (node.right) {
list.push(node.right);
}
}
}
};
var minNode = function(node) {
if (node) {
while (node.left !== null) {
node = node.left;
}
return node.key;
}
return null;
};
var maxNode = function(node) {
if (node) {
while (node.right !== null) {
node = node.right;
}
return node.key;
}
return null;
};
var searchNode = function(node, val) {
if (node === null) {
return false;
}
if (val < node.key) {
return searchNode(node.left, val);
} else if (val > node.key) {
return searchNode(node.right, val);
} else {
return true;
}
};
var findMinNode = function(node) {
if (node) {
while (node.left !== null) {
node = node.left;
}
return node;
}
return null;
};
var removeNode = function(node, key) {
if (node === null) {
return null;
}
if (key < node.key) {
node.left = removeNode(node.left, key);
return node;
} else if (key > node.key) {
node.right = removeNode(node.right, key);
return node;
} else {
if (node.left === null && node.right === null) {
node = null;
return node;
}
if (node.left === null) {
node = node.right;
return node;
}
if (node.right === null) {
node = node.left;
return node;
}
var aux = findMinNode(node.right);
node.key = aux.key;
node.right = removeNode(node.right, aux.key);
return node;
}
};
this.insert = function(key) {
var newNode = new Node(key);
if (root === null) {
root = newNode;
} else {
insertNode(root, newNode);
}
};
// 中序遍历是一种以上行顺序访问BST所有节点的遍历方式，也就是以从最小到最大的顺序访
// 问所有节点。中序遍历的一种应用就是对树进行排序操作。
this.inOrderTraverse = function(cb) {
inOrderTraverseNode(root, cb);
};
// 先序遍历是以优先于后代节点的顺序访问每个节点的。先序遍历的一种应用是打印一个结构化的文档。
this.preOrderTraverse = function(cb) {
preOrderTraverseNode(root, cb);
};
// 后序遍历则是先访问节点的后代节点，再访问节点本身。后序遍历的一种应用是计算一个目
// 录和它的子目录中所有文件所占空间的大小。
this.postOrderTraverse = function(cb) {
postOrderTraverseNode(root, cb);
};
// Breadth-First-Search
// 可以用来解决寻路径的问题。
this.levelOrderTraverse = function(cb) {
levelOrderTraverseNode(root, cb);
}
// Breadth-First-Search
// 区分层次
this.separateByLevel = function(cb) {
separateByLevelFn(root, cb);
}
this.min = function() {
return minNode(root);
};
this.max = function() {
return maxNode(root);
};
this.search = function(val) {
searchNode(root, val);
};
this.remove = function(key) {
root = removeNode(root, key);
};
};
/* ========== test case ========== */
var tree = new BinarySearchTree();
/**
*
* 11
* / \
* / \
* / \
* / \
* / \
* / \
* 7 15
* / \ / \
* / \ / \
* 5 9 13 20
* / \ / \ / \ / \
* 3 6 8 10 12 14 18 25
*
*/
tree.insert(11);
tree.insert(7);
tree.insert(15);
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);
tree.insert(6);
var printNode = function(val) {
console.log(val);
};
tree.inOrderTraverse(printNode);
console.log('\n')
tree.levelOrderTraverse(printNode);
console.log('\n')
tree.separateByLevel(printNode);
console.log('\n')
tree.remove(7)
tree.inOrderTraverse(printNode);
console.log('\n')
tree.preOrderTraverse(printNode);
console.log('\n')
tree.postOrderTraverse(printNode);
Binary Search Tree - ES6
class Node {
constructor(key) {
this.key = key;
this.left = null;
this.right = null;
}
}
// insert(key):向树中插入一个新的键。
// search(key):在树中查找一个键，如果节点存在，则返回true;如果不存在，则返回false。
// inOrderTraverse:通过中序遍历方式遍历所有节点。
// preOrderTraverse:通过先序遍历方式遍历所有节点。
// postOrderTraverse:通过后序遍历方式遍历所有节点。
// min:返回树中最小的值/键。
// max:返回树中最大的值/键。
// remove(key):从树中移除某个键。
class BinarySearchTree {
constructor() {
this.root = null;
}
static insertNode(node, newNode) {
if (node.key > newNode.key) {
if (node.left === null) {
node.left = newNode;
} else {
BinarySearchTree.insertNode(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
BinarySearchTree.insertNode(node.right, newNode);
}
}
}
static searchNode(node, key) {
if (node === null) {
return false;
}
if (node.key === key) {
return true;
} else if (node.key > key) {
BinarySearchTree.searchNode(node.left, key);
} else if (node.key < key) {
BinarySearchTree.searchNode(node.right, key);
}
}
static inOrderTraverseNode(node, cb) {
if (node === null) {
return;
}
BinarySearchTree.inOrderTraverseNode(node.left, cb);
cb(node.key);
BinarySearchTree.inOrderTraverseNode(node.right, cb);
}
static preOrderTraverseNode(node, cb) {
if (node === null) {
return;
}
cb(node.key);
BinarySearchTree.preOrderTraverseNode(node.left, cb);
BinarySearchTree.preOrderTraverseNode(node.right, cb);
}
static postOrderTraverseNode(node, cb) {
if (node === null) {
return;
}
BinarySearchTree.postOrderTraverseNode(node.left, cb);
BinarySearchTree.postOrderTraverseNode(node.right, cb);
cb(node.key);
}
static levelOrderTraverseNode(node, cb) {
if (node === null) {
return null;
}
const list = [node];
while (list.length > 0) {
node = list.shift();
cb(node.key);
if (node.left) {
list.push(node.left);
}
if (node.right) {
list.push(node.right);
}
}
}
static separateByLevelFn(node, cb, separator = '---*---') {
const list = [];
const END_FLAG = 'END_FLAG';
list.push(node);
list.push(END_FLAG);
while (list.length > 0) {
node = list.shift();
// 遇到结束信号，表示已经遍历完一层；若队列中还有元素，说明它们是刚刚遍历完的这一层的所有子元素。
if (node === END_FLAG && list.length > 0) {
list.push(END_FLAG);
cb(separator);
} else {
cb(node.key);
if (node.left) {
list.push(node.left)
}
if (node.right) {
list.push(node.right);
}
}
}
}
static removeNode(node, key) {
if (node === null) {
return null;
}
if (node.key === key) {
if (node.left === null && node.right === null) {
node = null;
return node;
} else if (node.left === null) {
node = node.right;
return node;
} else if (node.right === null) {
node = node.left;
return node;
} else if (node.left && node.right) {
let rightMinNode = node.right;
while (rightMinNode.left !== null) {
rightMinNode = rightMinNode.left;
}
node.key = rightMinNode.key;
node.right = BinarySearchTree.removeNode(node.right, rightMinNode.key);
return node;
}
} else if (node.key > key) {
node.left = BinarySearchTree.removeNode(node.left, key);
return node;
} else if (node.key < key) {
node.right = BinarySearchTree.removeNode(node.right, key);
return node;
}
}
static printNode(val) {
console.log(val);
}
insert(key) {
const newNode = new Node(key);
if (this.root === null) {
this.root = newNode;
} else {
BinarySearchTree.insertNode(this.root, newNode);
}
}
search(key) {
return BinarySearchTree.searchNode(key);
}
// 中序遍历是一种以上行顺序访问BST所有节点的遍历方式，也就是以从最小到最大的顺序访
// 问所有节点。中序遍历的一种应用就是对树进行排序操作。
inOrderTraverse(cb = BinarySearchTree.printNode) {
BinarySearchTree.inOrderTraverseNode(this.root, cb);
}
// 先序遍历是以优先于后代节点的顺序访问每个节点的。先序遍历的一种应用是打印一个结构化的文档。
preOrderTraverse(cb = BinarySearchTree.printNode) {
BinarySearchTree.preOrderTraverseNode(this.root, cb);
}
// 后序遍历则是先访问节点的后代节点，再访问节点本身。后序遍历的一种应用是计算一个目
// 录和它的子目录中所有文件所占空间的大小。
postOrderTraverse(cb = BinarySearchTree.printNode) {
BinarySearchTree.postOrderTraverseNode(this.root, cb);
}
// Breadth-First-Search
// 可以用来解决寻路径的问题。
levelOrderTraverse(cb = BinarySearchTree.printNode) {
BinarySearchTree.levelOrderTraverseNode(this.root, cb);
}
// Breadth-First-Search
// 区分层次
separateByLevel(cb = BinarySearchTree.printNode) {
BinarySearchTree.separateByLevelFn(this.root, cb);
}
min() {
let node = this.root;
if (node === null) {
return null;
}
while (node.left !== null) {
node = node.left;
}
return node.key;
}
max() {
let node = this.root;
if (node === null) {
return null;
}
while (node.right !== null) {
node = node.right;
}
return node.key();
}
remove(key) {
this.root = BinarySearchTree.removeNode(this.root, key);
}
}
/* ========== test case ========== */
const tree = new BinarySearchTree();
/**
*
* 11
* / \
* / \
* / \
* / \
* / \
* / \
* 7 15
* / \ / \
* / \ / \
* 5 9 13 20
* / \ / \ / \ / \
* 3 6 8 10 12 14 18 25
*
*/
tree.insert(11);
tree.insert(7);
tree.insert(15);
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);
tree.insert(6);
tree.inOrderTraverse();
console.log('\n')
tree.levelOrderTraverse();
console.log('\n')
tree.separateByLevel();
console.log('\n')
tree.remove(7)
tree.inOrderTraverse();
console.log('\n')
tree.preOrderTraverse();
console.log('\n')
tree.postOrderTraverse();