c++ - 是否有某种算法可以反向过滤N个二叉树节点？

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 的节点是您想要保留的节点。