Есть ли какие-то алгоритмы для обратного фильтрования узлов дерева N'ary?

Question

У меня есть 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(); 
} 

Answer 1

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; 
} 

Называйте это, как dfs(root, false);. Узлы с keep = true - это те, которые вы хотели бы сохранить.