二叉树及其遍历方法：JavaScript实践
二叉树
常见的数组，栈，列表都是线性结构
常见的树型结构有：文件夹目录，dom结构，路由的配置...
二叉树
二叉树是每个结点最多有两个子树的树形结构，每个结点的度最多是2。左边的称为 左子树 , 右边的称为 右子树 , 左子树 , 右子树 是有顺序的。
实现二叉搜索树
class Node {
constructor(element, parent) {
this.element = element; //当前节点
this.parent = parent; //节点的父亲
this.left = null; //节点的左侧是什么
this.rigth = null; //节点的右侧是什么
}
}
class Tree {
constructor(compare) {
//比较器，可以用户自己配置比较规则
this.compare = compare || this.compare;
//根节点
this.root = null;
//总共有多少个节点
this.size = 0;
}
//内部实现的比较规则，如果用户自己配置了比较规则，则用用户自己的比较规则
compare(e1, e2) {
return e1 > e2;
}
//向树中添加节点
add(element) {
//判断根节点是否存在
if (this.root == null) {
//添加为根节点
this.root = new Node(element, null);
this.size++;
} else { //已经存在根节点了
//获取对比的参照物
let currentNode = this.root;
//父亲节点
let parent = null;
//对比的结果
let compare = null;
while (currentNode) {
parent = currentNode;
compare = this.compare(currentNode.element, element);
if (compare) {
//小于参照物
currentNode = currentNode.left;
} else {
//大于参照物
currentNode = currentNode.rigth;
}
}
//将节点挂到树上
const node = new Node(element, parent);
if (compare) {
parent.left = node;
} else {
parent.rigth = node;
}
this.size++;
}
}
}
const t = new Tree((e1, e2) => {
return e1.id > e2.id;
});
//自定义比较规则
t.add({
id: 10,
name: '章三1'
});
t.add({
id: 8,
name: '章三2'
});
t.add({
id: 6,
name: '章三3'
});
t.add({
id: 19,
name: '章三4'
});
t.add({
id: 15,
name: '章三5'
});
t.add({
id: 22,
name: '章三6'
});
t.add({
id: 20,
name: '章三7'
});
console.dir(t, {
depth: 1000
});二叉树的遍历
常见的四种遍历方式
前序：
preorder traversal, 先根节点，再左子树，最后右子树中序：
inorder traversal, 先左子树，再根节点，最后右子树，遍历出来的结果是有序的后序：
postorder traversal, 先左子树，再右子树，最后根节点层序：
levelorder traversal, 从上到下，从左到有一次遍历
前序遍历
递归实现
preOrderTraversal(cb) {
const traversal = node => {
if (node == null) return;
//先抛出根节点
cb(node);
//先遍历左边，再遍历右边
traversal(node.left);
traversal(node.rigth);
}
traversal(this.root);
}循环实现
preOrderTraversal(cb) {
const queue = [this.root];
while (queue.length) {
const node = queue.pop();
cb(node);
if (node.rigth) {
queue.push(node.rigth);
}
if (node.left) {
queue.push(node.left);
}
}
}中序遍历
inOrderTraversal(cb) {
const traversal = node => {
if (node == null) return;
traversal(node.left);
cb(node);
traversal(node.rigth);
}
traversal(this.root)
}后序遍历
postOderTraversal(cb) {
const traversal = node => {
if (node == null) return;
traversal(node.left);
traversal(node.rigth);
cb(node);
}
traversal(this.root)
}层序遍历
levelOrderTraversal(cb) {
const stack = [this.root];
while (stack.length) {
const node = stack.shift();
cb(node);
if (node.left) {
stack.push(node.left);
}
if (node.rigth) {
stack.push(node.rigth);
}
}
}树的反转
reversalTree() {
if (this.root == null) return;
const stack = [this.root];
let currentNode = null;
let index = 0
while (currentNode = stack[index++]) {
const temp = currentNode.left;
currentNode.left = currentNode.rigth;
currentNode.rigth = temp;
if (currentNode.left) {
stack.push(currentNode.left);
}
if (currentNode.rigth) {
stack.push(currentNode.rigth)
}
}
return this.root;
}完整代码
class Node {
constructor(element, parent) {
this.element = element; //当前节点
this.parent = parent; //节点的父亲
this.left = null; //节点的左侧是什么
this.rigth = null; //节点的右侧是什么
}
}
class Tree {
constructor(compare) {
//比较器，可以用户自己配置比较规则
this.compare = compare || this.compare;
//根节点
this.root = null;
//总共有多少个节点
this.size = 0;
}
//内部实现的比较规则，如果用户自己配置了比较规则，则用用户自己的比较规则
compare(e1, e2) {
return e1 > e2;
}
//向树中添加节点
add(element) {
//判断根节点是否存在
if (this.root == null) {
//添加为根节点
this.root = new Node(element, null);
this.size++;
} else { //已经存在根节点了
//获取对比的参照物
let currentNode = this.root;
//父亲节点
let parent = null;
//对比的结果
let compare = null;
while (currentNode) {
parent = currentNode;
compare = this.compare(currentNode.element, element);
if (compare) {
//小于参照物
currentNode = currentNode.left;
} else {
//大于参照物
currentNode = currentNode.rigth;
}
}
//将节点挂到树上
const node = new Node(element, parent);
if (compare) {
parent.left = node;
} else {
parent.rigth = node;
}
this.size++;
}
}
// preOrderTraversal(cb) {
// const traversal = node => {
// if (node == null) return;
// //先抛出根节点
// cb(node);
// //先遍历左边，再遍历右边
// traversal(node.left);
// traversal(node.rigth);
// }
// traversal(this.root);
// }
preOrderTraversal(cb) {
const queue = [this.root];
while (queue.length) {
const node = queue.pop();
cb(node);
if (node.rigth) {
queue.push(node.rigth);
}
if (node.left) {
queue.push(node.left);
}
}
}
inOrderTraversal(cb) {
const traversal = node => {
if (node == null) return;
traversal(node.left);
cb(node);
traversal(node.rigth);
}
traversal(this.root)
}
postOderTraversal(cb) {
const traversal = node => {
if (node == null) return;
traversal(node.left);
traversal(node.rigth);
cb(node);
}
traversal(this.root)
}
levelOrderTraversal(cb) {
const stack = [this.root];
while (stack.length) {
const node = stack.shift();
cb(node);
if (node.left) {
stack.push(node.left);
}
if (node.rigth) {
stack.push(node.rigth);
}
}
}
reversalTree() {
if (this.root == null) return;
const stack = [this.root];
let currentNode = null;
let index = 0
while (currentNode = stack[index++]) {
const temp = currentNode.left;
currentNode.left = currentNode.rigth;
currentNode.rigth = temp;
if (currentNode.left) {
stack.push(currentNode.left);
}
if (currentNode.rigth) {
stack.push(currentNode.rigth)
}
}
return this.root;
}
}
const t = new Tree((e1, e2) => {
return e1.id > e2.id;
});
//自定义比较规则
t.add({ id: 10, name: '章三1' });
t.add({ id: 8, name: '章三2' });
t.add({ id: 6, name: '章三3' });
t.add({ id: 19, name: '章三4' });
t.add({ id: 15, name: '章三5' });
t.add({ id: 22, name: '章三6' });
t.add({ id: 20, name: '章三7' });
console.dir(t.reversalTree(), { depth: 1000 });
// t.levelOrderTraversal((node) => {
// console.log(node.element)
// })
