使用 javascript 的递归堆栈跟踪解释

发布于08月28日

// Recursive javascript program for level
// order traversal of Binary Tree

// Class containing left and right child of current
// node and key value
class Node {
  constructor(val) {
    this.data = val;
    this.left = null;
    this.right = null;
  }
}


// Root of the Binary Tree
var root = null;

// Function to print level order traversal of tree
function printLevelOrder() {
  var h = height(root);
  var i;
  // for (i = 1; i <= h; i++)
  printCurrentLevel(root, h);
}

// Compute the "height" of a tree -- the number
// of nodes along the longest path
// from the root node down to the farthest leaf node.
function height(root) {
  if (root == null)
    return 0;
  else {
    // Compute height of each subtree
    var lheight = height(root.left);
    var rheight = height(root.right);

    // Use the larger one
    if (lheight > rheight)
      return (lheight + 1);
    else
      return (rheight + 1);
  }
}

// Print nodes at the current level
function printCurrentLevel(root, level) {

  //  alert("root data = "+root.data+" : level = "+level);


  document.getElementById("demo").innerHTML = document.getElementById("demo").innerHTML + "<br/>" + "root data = " + root.data + " : level = " + level + "";



  if (root == null)
    return;
  if (level == 1) {
    //alert(root.data);

  } else if (level > 1) {

    printCurrentLevel(root.left, level - 1);
    printCurrentLevel(root.right, level - 1);
  }
}

// Driver program to test above functions

root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);

root.left.left.left = new Node(8);
root.left.left.right = new Node(9);



console.log("Level order traversal of  binary tree is ");
printLevelOrder();

<!DOCTYPE html>
<html>

<body>

  <h2>My First JavaScript</h2>


  <p id="demo"></p>

</body>

</html>

为什么上面的代码的输出是

root data = 1 : level = 4
root data = 2 : level = 3
root data = 4 : level = 2
root data = 8 : level = 1
root data = 9 : level = 1
root data = 5 : level = 2

当使用递归时，它不打印root data = 3: level = 3

如果注释如下所示的代码，则输出将为root data = 1 : level = 4

if (root == null)
       //   return ;

请帮助我理解这一点.

参考资料: https://www.geeksforgeeks.org/level-order-tree-traversal/个

document.getElementById("demo").innerHTML = document.getElementById("demo").innerHTML + "<br/>" + "root data = " + root.data + " : level = " + level + ""; if (root == null) return;

if (root == null) return; document.getElementById("demo").innerHTML = document.getElementById("demo").innerHTML + "<br/>" + "root data = " + root.data + " : level = " + level + "";

root data = 1 : level = 4 root data = 2 : level = 3 root data = 4 : level = 2 root data = 8 : level = 1 root data = 9 : level = 1 root data = 5 : level = 2 root data = 3 : level = 3 root data = 6 : level = 2 root data = 7 : level = 2

级别顺序

要实现级别顺序，通常使用队列而不是堆栈，因此递归不是可行的方法.

下面是一个级别顺序遍历的实现，输出到控制台.它使用一个生成器函数，该函数非常适合于此目的:

class Node {
  constructor(val) {
    this.data = val;
    this.left = null;
    this.right = null;
  }
}

// Generator function for level order traversal of tree
function* generateLevelOrder(root) {
    const queue = [root];
    for (const node of queue) {
        if (!node) continue;
        yield node.data;
        queue.push(node.left, node.right);
    }
}

// Driver program to test above functions

var root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.left.left = new Node(8);
root.left.left.right = new Node(9);

// Print level order:
for (const data of generateLevelOrder(root)) {
    console.log(data);
}

使用 javascript 的递归堆栈跟踪解释

推荐答案

备注

级别顺序

Javascript相关问答推荐

如何在react-Router-dom 6中Forking 路由？

React redux状态未在React-Router库中呈现

如何在非独立组件中使用独立组件？

React状态变量在使用++前置更新时引发错误

设置默认值后动态更新japbox或调色板

添加/删除时React图像上传重新渲染上传的图像

GrapeJS -如何保存和加载自定义页面

网页自检测外部元素无法加载

使用Java脚本根据按下的按钮更改S文本

无法检测卡片重叠状态的问题

使用JQuery单击元素从新弹出窗口获取值

变量的值在Reaction组件中的Try-Catch语句之外丢失

更新动态数据中对象或数组中的所有值字符串

在Matter.js中添加从点A到另一个约束的约束

触发异步函数后不能显示数据

为什么延迟在我的laravel项目中不起作用？

在JavaScript中，有没有一种方法可以迭代字符串的词法标记？

如何在下一个js中更改每个标记APEXCHARTS图表的 colored颜色

更改管线时不渲染组件的react

KeyboardEvent：检测到键具有打印的表示形式