在树状结构中搜索节点

Question

我需要帮助查找和返回一般树结构中的“节点”。每个节点可以有两个以上的子节点，因此它不是二叉树。我已经得到了下面的代码，这个Element对象有一个列表来包含它的子元素，我在main中创建了一个元素节点指针，并使用它来添加和搜索子元素。这是一个学校项目，但我不寻找答案（答案不会受伤）。有关如何解决此问题的任何建议将非常感谢，谢谢！

#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

我会给你用于搜索在root根的树有一个值val一个节点的伪代码：

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