javascript - 如何使用深度优先遍历删除节点

Question

       a              
      /|\            
     b f  c           
   /  /   
  d  x
 /\
e  h

我的应用程序中有这种树结构。我想先遍历这棵树的深度，然后先删除深度的节点。节点可以有多个子节点。

我尝试这样做，但它没有按深度第一顺序删除，如 e、h、d、b、x、f、c、a。我的意思是它应该删除子节点然后父节点。

function deleteNode(node) {
    let childs = node.getChildrens();
    if(childs === undefined || childs === null) {
        remove(node);
    } else
        for(int i = 0; i < childs.length; i++) {
            // if childs then 
            deleteNode(childs[i])
        }
    }   
    remove(node);
}   

Answer 1

我无法知道您的设置出了什么问题，但也许您可以尝试将外部 remove(node) 移动到您的 else 处理程序中:

function deleteNode(node) {
    let childs = node.getChildrens();
    if(childs === undefined || childs === null) {
        remove(node);
    } else
        for(int i = 0; i < childs.length; i++) {
            // if childs then 
            deleteNode(childs[i])
        }
        remove(node);
    }
}

或者更好的是，进一步简化逻辑:

function deleteNode(node) {
    // recurse through all the children first
    let childs = node.getChildrens();
    for(int i = 0; i < childs.length; i++) {
        deleteNode(childs[i])
    }

    // then delete itself
    remove(node);
}

目前，您的 remove(node) 调用在子节点上执行了两次，这可能是导致错误的原因。