本文首发于 我的 Github
二叉搜索树
二叉树中的节点最多只能有 2 个子节点:左侧子节点 和 右侧子节点。 二叉搜索树是二叉树的一种,但是它只允许在左侧子节点存储比父节点小的值,在右侧子节点存储大于等于父节点的值。
class Node {
constructor(value) {
this.left = null;
this.value = value;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
/**
* 插入节点
* @param {} value
*/
insert(value) {
const newNode = new Node(value);
if (!this.root) {
this.root = newNode;
} else {
let root = this.root;
insertNode(root, newNode);
function insertNode(node, newNode) {
if (node.value < newNode.value) {
if (node.right === null) {
node.right = newNode;
} else {
insertNode(node.right, newNode);
}
} else {
if (node.left === null) {
node.left = newNode;
} else {
insertNode(node.left, newNode);
}
}
}
}
return true;
}
/**
* 按值查找节点
* @param {*} value
*/
search(value) {
const _search = (node, value) => {
if (node === null) {
return false;
}
if (node.value > value) {
return _search(node.left, value);
} else if (node.value < value) {
return _search(node.right, value);
} else {
return node;
}
};
return _search(this.root, value);
}
}
先序遍历
先序遍历的顺序是:根 -> 左 -> 右。
递归版
function preTraverse(bsTree) {
const traverse = (node, queue) => {
if (!node) {
return queue;
} else {
queue.push(node);
traverse(node.left, queue);
traverse(node.right, queue);
}
};
const queue = [];
traverse(bsTree.root, queue);
return queue;
}
循环版
function preTraverse(bsTree) {
let stack = [];
let queue = [];
let node = bsTree.root;
stack.push(node);
while (stack.length > 0) {
let currentNode = stack.pop();
queue.push(currentNode);
if (currentNode.right) {
stack.push(currentNode.right);
}
if (currentNode.left) {
stack.push(currentNode.left);
}
}
return queue;
}
中序遍历
中序遍历的顺序是:左 -> 根 -> 右。
递归版
function inorderTraverse(bsTree) {
const traverse = (node, queue) => {
if (!node) {
return;
}
traverse(node.left, queue);
queue.push(node);
traverse(node.right, queue);
};
const queue = [];
traverse(bsTree.root, queue);
return queue;
}
循环版
function inorderTraverse(bsTree) {
const stack = [];
const queue = [];
let currentNode = bsTree.root;
while (currentNode || stack.length > 0) {
if (currentNode != null) {
stack.push(currentNode);
currentNode = currentNode.left;
} else {
currentNode = stack.pop();
queue.push(currentNode);
currentNode = currentNode.right;
}
}
return queue;
}
循环版的思路:
- 首先将所有左节点压入栈中
- 将栈弹出到队列中
- 当前节点回归到跟节点,依次入列右节点
function inorderTraverse(bsTree) {
const stack = [];
const queue = [];
let currentNode = bsTree.root;
while (currentNode) {
currentNode = currentNode.left;
stack.push(currentNode);
}
while (stack.length) {
queue.push(stack.pop());
}
currentNode = bsTree.root;
while (currentNode) {
queue.push(currentNode);
currentNode = currentNode.right;
}
return queue;
}
后序遍历
后序遍历的顺序是:左 -> 右 -> 根。
递归版
function postorderTraverse(bsTree) {
const traverse = (node, queue) => {
if (!node) {
return;
}
traverse(node.left, queue);
traverse(node.right, queue);
queue.push(node);
};
const queue = [];
traverse(bsTree.root, queue);
return queue;
}
循环版
function postorderTraverse(bsTree) {
let stack = []
let queue = []
let node = bsTree.root
stack.push(node)
while (stack.length) {
node = stack.pop()
if (node.left) {
stack.push(node.left)
}
if (node.right) {
stack.push(node.right)
}
queue.unshift(node)
}
return queue
}
题目
1. 层级遍历
问题描述
给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。
例如:
11
/ \
7 15
/ \ / \
3 6 12 16
层级遍历结果:
[
[11],
[7, 15],
[3, 6, 12, 16]
]
解题思路
- 建立一个queue
- 先把根节点放进去,这时候找根节点的左右两个子节点
- 去掉根节点,此时queue里的元素就是下一层的所有节点
- 用for循环遍历,将结果存到一个一维向量里
- 遍历完之后再把这个一维向量存到二维向量里
- 以此类推,可以完成层序遍历
function levelTraverse(bsTree) {
let queue = []
let ret = []
let node = bsTree.root
queue.push(node)
while (queue.length) {
const count = queue.length
const subRet = []
while (count > 0) {
node = queue.pop()
subRet.push(node)
if (node.left) queue.push(node.left)
if (node.right) queue.push(node.right)
}
ret.push(subRet)
}
return subRet
}