class Node {
public:
    Node(int value):m_value(value), m_mark(false){}
    ~Node() {}
    int getValue();                 //取得節點值
    stack* getNextNode();           //取得Stack m_nextNode成員
    void insertNode(Node* n);       //插入節點方法
    void setMark(bool m);           //標記節點，用以標示該節點已經被走訪過
    bool isMarked();                //確定該節點是否已被標記
private:
    int m_value;                    //類別成員: 節點值
    stack m_nextNode;               //類別成員: Stack存放連結的節點
    bool m_mark;                    //類別成員: 走訪標記
};
                    

int Node::getValue() {
    return m_value;
}
                            
stack* Node::getNextNode() {
    return &m_nextNode;
}
                            
void Node::insertNode(Node* n) {
    m_nextNode.push(n);
}
                            
void Node::setMark(bool m) {
    m_mark = m;
}
                            
bool Node::isMarked() {
    return m_mark;
}
                        

void createTree(Node* root) {
    // New All of Node
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);
    Node* node4 = new Node(4);
    Node* node5 = new Node(5);
    Node* node6 = new Node(6);
                            
    // Inserting Node
    root->insertNode(node2);
    root->insertNode(node3);
    root->insertNode(node4);
    node2->insertNode(node5);
    node3->insertNode(node5);
    node3->insertNode(node6);
}
                        

void visitTree(Node* node) {
    if (!node->isMarked())  //確定該節點標記是否已經被走訪過，若沒有則輸出該節點的值
        cout << node->getValue() << " " << endl;
    node->setMark(true);    //將節點標記為已走訪
    stack* nodeStack = node->getNextNode();  //取得該節點的連接節點堆疊
    if (nodeStack->empty()) //若該節點沒有連接節點，則返回
        return;
    while (!nodeStack->empty()) {   //以遞迴的方式繼續走訪連接節點
        Node* n = nodeStack->top();
        visitTree(n);
        nodeStack->pop();
    }
}

int main()
{
    Node* root = new Node(1);
    createTree(root);
    visitTree(root);

    return 0;
}