二叉树是一个每个节点最多有两个子树的树结构,通常分为左子树、右子树。二叉树有多种遍历方式,包括先序遍历、中序遍历和后序遍历。
其中,
在 JavaScript 中,我们可以用基本的数据结构来表示一棵二叉树。二叉树节点的结构通常包含一个值、左子树和右子树三个属性。
下面是一个基本的二叉树节点结构的 JavaScript 代码表示:
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
下面是一个生成二叉树的函数,通过数组 inputArr 生成一棵二叉树:
const buildBinaryTree = (inputArr) => {
const root = new TreeNode(inputArr[0]);
const queue = [root];
let index = 1;
while (index < inputArr.length) {
const currNode = queue.shift();
if (inputArr[index] !== null) {
currNode.left = new TreeNode(inputArr[index]);
queue.push(currNode.left);
}
index++;
if (index >= inputArr.length) break;
if (inputArr[index] !== null) {
currNode.right = new TreeNode(inputArr[index]);
queue.push(currNode.right);
}
index++;
}
return root;
};
先序遍历按照“根结点-左子树-右子树”的方式遍历二叉树。步骤如下:
以下是先序遍历的 JavaScript 实现:
const preorderTraversal = (root, result = []) => {
if (!root) return result;
result.push(root.val);
root.left && preorderTraversal(root.left, result);
root.right && preorderTraversal(root.right, result);
return result;
};
以下是一个简单的示例:
const inputArr = [1, 2, 3, 4, 5, 6, 7];
const root = buildBinaryTree(inputArr);
console.log(preorderTraversal(root)); // [1, 2, 4, 5, 3, 6, 7]
中序遍历按照“左子树-根结点-右子树”的方式遍历二叉树。步骤如下:
以下是中序遍历的 JavaScript 实现:
const inorderTraversal = (root, result = []) => {
if (!root) return result;
root.left && inorderTraversal(root.left, result);
result.push(root.val);
root.right && inorderTraversal(root.right, result);
return result;
};
以下是一个简单的示例:
const inputArr = [1, 2, 3, 4, 5, 6, 7];
const root = buildBinaryTree(inputArr);
console.log(inorderTraversal(root)); // [4, 2, 5, 1, 6, 3, 7]
后序遍历按照“左子树-右子树-根结点”的方式遍历二叉树。步骤如下:
以下是后序遍历的 JavaScript 实现:
const postorderTraversal = (root, result = []) => {
if (!root) return result;
root.left && postorderTraversal(root.left, result);
root.right && postorderTraversal(root.right, result);
result.push(root.val);
return result;
};
以下是一个简单的示例:
const inputArr = [1, 2, 3, 4, 5, 6, 7];
const root = buildBinaryTree(inputArr);
console.log(postorderTraversal(root)); // [4, 5, 2, 6, 7, 3, 1]
以上是 JavaScript 实现二叉树的先序、中序及后序遍历方法的详细攻略。
本文链接:http://task.lmcjl.com/news/10806.html