javascript - 如何使用递归函数在Javascript中遍历树
问题描述
我正在构建一个树遍历函数,它必须使用递归。
我想要的输出是
'{"value":9,"left":{"value":4,"left":{"value":1},"right":{"value":6}},"right":{"value":20,"left":{"value":15},"right":{"value":170}}}'
有人能弄清楚如何在traverse
函数中使用递归来获取输出吗?
这是我的 JS:
class Node {
constructor(value){
this.left = null;
this.right = null;
this.value = value;
}
}
class BinarySearchTree {
constructor(){
this.root = null;
}
insert(value){
const newNode = new Node(value);
if (this.root === null) {
this.root = newNode;
} else {
let currentNode = this.root;
while(true){
if(value < currentNode.value){
//Left
if(!currentNode.left){
currentNode.left = newNode;
return this;
}
currentNode = currentNode.left;
} else {
//Right
if(!currentNode.right){
currentNode.right = newNode;
return this;
}
currentNode = currentNode.right;
}
}
}
}
}
const tree = new BinarySearchTree();
tree.insert(9)
tree.insert(4)
tree.insert(6)
tree.insert(20)
tree.insert(170)
tree.insert(15)
tree.insert(1)
JSON.stringify(traverse(tree.root))
// 9
// 4 20
//1 6 15 170
function traverse(node) {
const tree = { value: node.value };
tree.left=node.left
if(node.left===null) {
return null
}else{
traverse(node.left);
}
tree.right=node.right
if(node.right===null) {
return null
}else{
traverse(node.right);
}
}
解决方案
你在正确的轨道上;我看到您的结果字符串中需要特殊格式的对象。我建议首先检查当前节点是否为空;如果是这样,则不返回任何内容(调用函数将忽略此键)。否则,创建一个节点对象,准备返回并遍历左右子节点。递归遍历两个子树后,返回根节点。这将从叶子开始构建结果结构并以根结束。
在您的代码中,
if(node.left===null) {
return null
例如,有点为时过早。如果node
有右子树,我们不想放弃遍历它。除了空子之外,在所有情况下都需要向调用者返回一些东西。
此外,您可以考虑放入traverse
该类BinaryTree
并使其对其成员字段进行操作;我在下面的示例中保持原样。
最后,这是一个前序遍历;先访问根,再访问左右子树。
function traverse(node) {
if (node) {
const left = traverse(node.left);
const right = traverse(node.right);
return {
value: node.value,
[left&&"left"]: left,
[right&&"right"]: right
};
}
}
class Node {
constructor(value, left=null, right=null) {
this.value = value;
this.left = left;
this.right = right;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new Node(value);
if (this.root === null) {
this.root = newNode;
}
else {
let currentNode = this.root;
while (true) {
if (value < currentNode.value) {
if (!currentNode.left) {
currentNode.left = newNode;
return this;
}
currentNode = currentNode.left;
}
else {
if (!currentNode.right) {
currentNode.right = newNode;
return this;
}
currentNode = currentNode.right;
}
}
}
}
}
const tree = new BinarySearchTree();
tree.insert(9);
tree.insert(4);
tree.insert(6);
tree.insert(20);
tree.insert(170);
tree.insert(15);
tree.insert(1);
console.log(JSON.stringify(traverse(tree.root)));
console.log(traverse(tree.root));
// 9
// 4 20
// 1 6 15 170
推荐阅读
- html - 垂直滚动条位置不同的两个 IFrame
- linux - 无法加载redis模块,RedisJSON
- c# - 如何对内部调用许多已经单独单元测试的内部或私有方法的公共方法进行单元测试
- tomcat9 - Tomcat9 - HTTP 状态 404 - 未找到 - Ubuntu
- java - 如何使反射在 JDK 16 及更高版本上工作?
- javascript - React Bootstrap 选项卡 - 尝试控制选项卡但失败
- azure - 在一天中的特定时间打开功能(资源)
- reactjs - 反应范围滑块没有使用正确的值
- azure - 如何加快缓慢的 Azure App Service Zip 部署?
- python - 在python中获取Freight Index的数据