跳到文档正文
数据结构 / 二叉树
08 / 18
我们的可视化工具通过直观的图形界面为二叉树操作注入生命力。每个节点都表示为一个圆圈，其中显示节点值，通过线条表示父子关系。这种层次化的可视化使得一眼就能理解树结构和操作。
我们工具的一个关键特性是动态节点跟踪。当您的代码遍历树时，无论是在插入、删除还是搜索操作期间，该工具都会突出显示当前节点及其连接。这种视觉反馈对于学习树操作概念或调试树相关算法特别有用。
让我们看看一些常见的二叉树算法及其可视化：
function inorderTraversal(root) {
const result = [];
// @ignore-function-tree
function traverse(node) {
if (node === null) return;
traverse(node.left);
result.push(node.val);
traverse(node.right);
}
traverse(root);
return result;
}
// 使用示例：
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
inorderTraversal(root); // [2, 1, 3]
function preorderTraversal(root) {
const result = [];
// @ignore-function-tree
function traverse(node) {
if (node === null) return;
result.push(node.val);
traverse(node.left);
traverse(node.right);
}
traverse(root);
return result;
}
// 使用示例：
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
preorderTraversal(root); // [1, 2, 3]
function postorderTraversal(root) {
const result = [];
// @ignore-function-tree
function traverse(node) {
if (node === null) return;
traverse(node.left);
traverse(node.right);
result.push(node.val);
}
traverse(root);
return result;
}
// 使用示例：
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
postorderTraversal(root); // [2, 3, 1]
function levelOrderTraversal(root) {
if (!root) return [];
const result = [];
const queue = new Queue();
queue.enqueue(root);
while (queue.size > 0) {
const levelSize = queue.size;
const currentLevel = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.dequeue();
currentLevel.push(node.val);
if (node.left) queue.enqueue(node.left);
if (node.right) queue.enqueue(node.right);
}
result.push(currentLevel);
}
return result;
}
// 使用示例：
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
levelOrderTraversal(root); // [[1], [2, 3]]
// @ignore-function-tree
function insertIntoBST(root, val) {
if (root === null) {
return new TreeNode(val);
}
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
} else {
root.right = insertIntoBST(root.right, val);
}
return root;
}
// 使用示例：
let root = new TreeNode(5);
insertIntoBST(root, 3);
insertIntoBST(root, 7);
// @ignore-function-tree
function searchBST(root, val) {
if (root === null || root.val === val) {
return root;
}
if (val < root.val) {
return searchBST(root.left, val);
}
return searchBST(root.right, val);
}
// 使用示例：
const root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(7);
searchBST(root, 3); // 返回值为3的节点
// @ignore-function-tree
function deleteFromBST(root, val) {
if (root === null) return null;
if (val < root.val) {
root.left = deleteFromBST(root.left, val);
} else if (val > root.val) {
root.right = deleteFromBST(root.right, val);
} else {
// 只有一个子节点或没有子节点的情况
if (root.left === null) return root.right;
if (root.right === null) return root.left;
// 有两个子节点的情况
let minNode = findMin(root.right);
root.val = minNode.val;
root.right = deleteFromBST(root.right, minNode.val);
}
return root;
}
function findMin(node) {
while (node.left !== null) {
node = node.left;
}
return node;
}
// 使用示例：
let root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(7);
deleteFromBST(root, 3);
// @ignore-function-tree
function getHeight(root) {
if (root === null) return 0;
const leftHeight = getHeight(root.left);
const rightHeight = getHeight(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
// 使用示例：
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
getHeight(root); // 3
function isBalanced(root) {
// @ignore-function-tree
function checkHeight(node) {
if (node === null) return 0;
const leftHeight = checkHeight(node.left);
if (leftHeight === -1) return -1;
const rightHeight = checkHeight(node.right);
if (rightHeight === -1) return -1;
if (Math.abs(leftHeight - rightHeight) > 1) return -1;
return Math.max(leftHeight, rightHeight) + 1;
}
return checkHeight(root) !== -1;
}
// 使用示例：
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
isBalanced(root); // true
function isSymmetric(root) {
if (root === null) return true;
// @ignore-function-tree
function isMirror(left, right) {
if (left === null && right === null) return true;
if (left === null || right === null) return false;
return (left.val === right.val) &&
isMirror(left.left, right.right) &&
isMirror(left.right, right.left);
}
return isMirror(root.left, root.right);
}
// 使用示例：
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(2);
isSymmetric(root); // true