Поиск узла в древовидной структуре

Question

Мне нужна помощь в поиске и возврате «узла» в общую древовидную структуру. Каждый узел может иметь более двух детей, поэтому он не является двоичным деревом. Мне был предоставлен следующий код: этот элемент Element имеет список, содержащий его дочерние элементы, я создаю указатель на один элемент узла и использую его, чтобы добавить и найти детей. Это для школьного проекта, но я не ищу ответов (ответ не помешает). Любые советы о том, как решить эту проблему, будут очень благодарны, спасибо!

#pragma once 
#include <iostream> 
#include <list> 
#include <sstream> 

using namespace std; 

class Element 
{ 
    private: 
    list<Element*> children; 
    char* _tag; 
    int _value; 
    // private methods 
    public: 
    // default constructor 
    Element(); 
    // non-default constructors 
    Element(char* name); // value is set to -99 if not given 
    Element(char* name, char* value); 
    // destructor, must recursively destruct its children 
    // and release the memory allocated for _tag 
    ~Element(); 
    // ostream operator (pre-order traversal) 
    friend ostream& operator << (ostream& out, const Element& E); 
    void display_xml(); // print out the tree in xml-- format 
    void addChild(Element* child); // add a child 
    // Find the first element such that _tag == tag 
    // returns “this” pointer of this element 
    Element* findTag(char* tag); 
    char* getName(); 
    int getValue(); 
    void setName(char* name); 
    void setValue(int value); 
    int height(); //b return the height 
    int size(); // return the size 
    // other methods 
}; 

это моя лучшая попытка решения, имеет очевидные проблемы, но я новичок во всем этом и некоторое объяснение на правильное решение, или какой-либо образец кода будет очень полезно!

Element* Element::findTag(char* tag) 
{ 
    list<Element*> temp = children; 
    int s = temp.size(); 

    if(getName() == tag) 
    { 
     return this; 
    } 
    else 
    { 
     for(int i = 0; i < s; i++) 
     { 
      findTag((*temp.front()).getName()); 
      temp.pop_front(); 
     } 
    } 

} 

Answer 1

Я дам вам псевдо-код для поиска узла, который имеет значение val в дереве с корнем root:

find(Node root, val) 
    if(root.value == val) return root   //-- if the recursion found the node we are searching for 
else 
    for every child x of root    //-- re-cursing on the children of root 
     if(find(x, val) != null) return x //-- if one of the calls found the node we are searching for 
    return null        //-- if we did not find the node we want in the sub-tree rooted at root