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

问题描述 投票：0回答：1

// 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/

javascript recursion data-structures tree binary-tree
1个回答
0
投票

使用递归时输出不包含

root data = 3 : level = 3
的原因在于
printCurrentLevel
函数的实现方式。

在 

printCurrentLevel
函数中，您正在检查 level 参数的值以确定是打印当前节点的数据还是继续递归其子节点。

但是，当您到达 

level == 1
的级别时，您可以正确打印数据，但在此之后，
else if (level > 1)
条件会阻止进一步递归，这就是为什么 
printCurrentLevel
函数不会继续到第三级树。

要解决此问题： 您应该修改 

printCurrentLevel
函数以删除 else if 条件。您应该允许递归继续，而不管级别值如何，而不是在 
level > 1
时停止递归。

以下是修改该功能的方法：

function printCurrentLevel(root, level) {
  if (root == null)
    return;
  
  // Print the data at this level
  if (level == 1) {
    document.getElementById("demo").innerHTML +=
      "<br/>" + "root data = " + root.data + " : level = " + level + "";
  }

  // Recurse on left and right children
  printCurrentLevel(root.left, level - 1);
  printCurrentLevel(root.right, level - 1);
}

通过此更改，即使在 

level > 1
时，递归也会继续，并且您应该看到预期输出，包括 
root data = 3 : level = 3
。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.