javascript - Javascript中如何使用递归函数遍历树

Question

我正在构建一个树遍历函数，它必须使用递归。

我想要的输出是

'{"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);
            }
       }

Answer 1

您走在正确的轨道上；我看到您的结果字符串中需要特殊格式的对象。我建议首先检查当前节点是否为空；如果是，则不返回任何内容(调用函数将忽略此键)。否则，创建节点对象准备返回并遍历左右 child 。递归遍历两棵子树后，返回根节点。这将从叶开始构建结果结构，并以根结束。

在你的代码中，

   if(node.left===null) {
        return  null

例如，

有点过早。如果 node 有右子树，我们不想放弃遍历它。除了空 child 外，在所有情况下也有必要向调用者返回一些东西。

另外，可以考虑将traverse放在BinaryTree类中，让它对其成员字段进行操作；在下面的示例中，我将其保留原样。

最后，这是一个 pre-order traversal ;先访问根，再访问左右子树。

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