javascript - 二叉树 - 深度优先遍历

Question

我想对这棵二叉树进行深度优先遍历:

          1
         / \
        4   5
       / \   \
      4   4   5

这是节点结构:

function TreeNode(data){
    this.data = data
    this.left = this.right = []

    this.addLeft = function(node){
        this.left.push(node)
    }

    this.addRight = function(node){
        this.right.push(node)
    }
}

访问函数(只是为了打印出节点数据):

function visit(node){
    console.log(node.data)
}

遍历函数:

function traverse(node){
   if(node === null) return

   visit(node)

   //visit left branch
   for(node of node.left) traverse(node)

   //visit right branch
   for(node of node.right) traverse(node)
}

添加二叉树结构:

let rootNode = new TreeNode(1)
let node_4A = new TreeNode(4)
let node_4B = new TreeNode(4)
let node_4C = new TreeNode(4)
let node_5A = new TreeNode(5)
let node_5B = new TreeNode(5)

//add root node branches
rootNode.addLeft(node_4A)
rootNode.addRight(node_5A)

node_4A.addLeft(node_4B)
node_4A.addRight(node_4C)
node_5A.addRight(node_5B)

输出:

1
4
4
4
5
5
5

所以它正确地打印出了节点数据，但是总是有一个额外的最右边的节点被打印了两次(即最后一个 5)。您知道为什么会这样吗？

我不太熟悉 Javascript 调用堆栈，可能是因为我在递归函数中运行了 2 个 for 循环吗？

谢谢。

Answer 1

您对左侧和右侧采用相同的对象引用。

this.left = this.right = []

你需要独立的数组:

this.left = [];
this.right = [];

为了获取正确的节点，取与 node 不同的名称进行迭代。

function traverse(node) {
    if (!node) return;  // you never have a value of null for a node
    visit(node)

    //visit left branch
    for (let n of node.left) {
        traverse(n);
    }
    //visit right branch
    for (let n of node.right) {
        traverse(n);
    }
}

function TreeNode(data) {
    this.data = data
    this.left = [];
    this.right = [];

    this.addLeft = function (node) {
        this.left.push(node)
    }

    this.addRight = function (node) {
        this.right.push(node)
    }
}

function visit(node) {
    console.log(node.data)
}

function traverse(node) {
    if (!node) return; // you never have a value of null for a node

    visit(node)

    for (let n of node.left) {
        traverse(n);
    }

    for (let n of node.right) {
        traverse(n);
    }
}

let rootNode = new TreeNode(1)
let node_4A = new TreeNode(4)
let node_4B = new TreeNode(4)
let node_4C = new TreeNode(4)
let node_5A = new TreeNode(5)
let node_5B = new TreeNode(5)

//add root node branches
rootNode.addLeft(node_4A)
rootNode.addRight(node_5A)

node_4A.addLeft(node_4B)
node_4A.addRight(node_4C)
node_5A.addRight(node_5B)
traverse(rootNode);