是否有某种逆向过滤N'ary树节点的算法？

• Z时代
• 2024-01-10
• 分类：问答

我有这样限定的N'ary树：是否有某种逆向过滤N'ary树节点的算法？

typedef struct node_t 
{ 
    wstring val; 
    vector <node_t *> subnodes; 
    node_t* parent; 
    BOOL bRed; 
}*pnode, node; 

树中的每个节点具有bRed属性。我的问题是我可以过滤树节点，所以只有红色节点（bRet == TRUE）及其所有父节点（根节点的路径）和子节点可以保留？有没有某种算法可以实现这一点？

原树：

过滤树：

节点解释：

这里是代码到目前为止：

#include <stdlib.h> 
#include <string> 
#include <iostream> 
#include <vector> 
#include <stack> 
#include <windows.h> 
#include <tchar.h> 
using namespace std; 
typedef struct node_t 
{ 
    wstring val; 
    vector <node_t *> subnodes; 
    node_t* parent; 
    BOOL bRed; 
}*pnode, node; 
node* nd; 
pnode ndparent = NULL; 
pnode ndroot = NULL; 
void log(LPCTSTR lpRecordStr, ...) 
{ 
    TCHAR  tszLogFile[MAX_PATH]  = {0}; 
    TCHAR  pInfo[1024]     = {0}; 
    HRESULT  hr       = S_FALSE; 
    TCHAR  szProgramDataPath[MAX_PATH] = {0}; 
    BOOL  bExists      = TRUE; 
    do 
    { 
     SYSTEMTIME LocalTime ; 
     GetLocalTime(&LocalTime); 
     _stprintf_s(pInfo,_T("[test] [%04d-%02d-%02d,%02d:%02d:%02d:%03d]"), 
      LocalTime.wYear, 
      LocalTime.wMonth, 
      LocalTime.wDay, 
      LocalTime.wHour, 
      LocalTime.wMinute, 
      LocalTime.wSecond, 
      LocalTime.wMilliseconds 
      ); 
     va_list argList; 
     va_start(argList, lpRecordStr); 
     _vsntprintf_s(pInfo + _tcslen(pInfo) , 1024 - _tcslen(pInfo) - 1 , 1024, lpRecordStr, argList); 
     va_end(argList); 
     _tcscat_s(pInfo , _T("\n")); 
     OutputDebugString(pInfo); 
    } while (FALSE); 
} 
VOID SearchFile(TCHAR *Path, pnode xxx) 
{ 
    HANDLE     hFind; 
    WIN32_FIND_DATA   wfd; 
    TCHAR     tszPathTemp[512]  = {0}; 
    TCHAR     tszParam[512]  = {0}; 
    ZeroMemory(&wfd,sizeof(WIN32_FIND_DATA)); 
    memset(tszPathTemp,0,sizeof(tszPathTemp)); 
    _stprintf_s(tszPathTemp, MAX_PATH, _T("%s\\*.*"),Path); 
    hFind=FindFirstFile(tszPathTemp,&wfd); 
    if(INVALID_HANDLE_VALUE==hFind) 
    { 
     return; 
    } 
    do 
    { 
     if(_tcscmp(wfd.cFileName,_T("."))==0|| _tcscmp(wfd.cFileName,_T(".."))==0) 
     { 
      continue; 
     } 
     if(wfd.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY) 
     { 
      _stprintf_s(tszPathTemp, MAX_PATH, _T("%s\\%s"),Path,wfd.cFileName); 
//   log(_T("dir: %s"), tszPathTemp); 
      nd->subnodes.push_back(new node()); 
      ndparent = nd; 
      nd = nd->subnodes[nd->subnodes.size()-1]; 
      nd->val = wfd.cFileName; 
      nd->parent = ndparent; 
      SearchFile(tszPathTemp, xxx); 
     } 
     else 
     { 
      _stprintf_s(tszPathTemp, MAX_PATH, _T("%s\\%s"),Path, wfd.cFileName); 
//   log(_T("filename:%s"), wfd.cFileName); 
      nd->subnodes.push_back(new node()); 
      nd->subnodes[nd->subnodes.size()-1]->val = wfd.cFileName; 
     } 
    }while(FindNextFile(hFind,&wfd)); 
    FindClose(hFind); 
    if (nd->parent != ndroot) 
    { 
     nd = nd->parent; 
    } 
} 
void travel(pnode pnd) 
{ 
    if (pnd == NULL) 
    { 
     return; 
    } 
    for (UINT i=0 ; i < pnd->subnodes.size(); i++) 
    { 
     //save the current node poiter 
     pnode pnd_save = pnd; 
     pnode pnd_temp = pnd->subnodes[i]; 
     std::stack<wstring> path; 
     wstring path_str; 
     while(pnd != NULL) 
     { 
      path.push(pnd->val.c_str()); 
      pnd = pnd->parent; 
     } 
     while(!path.empty()) 
     { 
      path_str = path_str + L"\\" + wstring(path.top()); 
      path.pop(); 
     } 
     pnd = pnd_save; 
//  log(_T("travel:%s"), path_str.c_str()); 
     travel(pnd_temp); 
    } 
} 
int main() 
{ 
    vector<wstring> file; 
    nd = new node(); 
    ndroot = nd; 
    nd->parent = NULL; 
    SearchFile(_T("D:"), nd); 
    while(nd != ndroot) 
    { 
     nd = nd->parent; 
    } 
// travel(nd); 
    getchar(); 
} 

回答：

typedef struct node_t { 
    wstring val; 
    vector<node_t *> subnodes; 
    node_t* parent; 
    bool red; 
    bool keep; 
}*pnode, node; 
bool dfs(node_t *curr, bool parent_was_red) { 
    // flag: some of the child nodes is red 
    bool red_in_subtree = curr->red; 
    // flag: some of the parent nodes is red 
    parent_was_red = parent_was_red || curr->red; 
    for (auto & child : curr->subnodes) { 
     red_in_subtree = red_in_subtree || dfs(child, parent_was_red); 
    } 
    if (parent_was_red || red_in_subtree) { 
     curr->keep = true; 
    } 
    return red_in_subtree; 
} 

以上是 是否有某种逆向过滤N'ary树节点的算法？ 的全部内容， 来源链接： utcz.com/qa/265553.html