如何使用深度第一遍历删除节点

Question

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

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

我试图这样做，但它并没有在e，h，h，d，b，x，f，c，a中删除一阶的深度一阶。我的意思是它应该删除Childs节点，然后删除父节点。

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)呼叫在儿童节点上被执行两次，这可能是错误的原因。

Answer 2

我相信，当您删除子节点时，儿童阵列的长度会减小。我建议您从当前

更改您的循环

for(int i = 0; i < childs.length; i++) {
            // if childs then 
            deleteNode(childs[i])
        }

to

while( node.getChildrens().length>0) {
            // if childs then 
            deleteNode(childs[0])
        }