c++ - 使用访问者设计模式重复访问 N 叉树中的子节点值

Question

这棵树长什么样:

          A
       /   \    \
     AA   AB    AC
     /     \     \
   AAA    ABA     ABB

目前，使用数组我能够得到这个输出:

A AA AAA AAA AAA AA AA A AB ABA ABA ABA AB ABB ABB ABB AB A AC AC AC

输出应该是这样的:

A AA AAA AB ABA AC ABB

使用硬编码，我只能得到这个输出:

A AA AAA AB ABA ABB

这个问题有什么建议吗？如何停止重复已读取的子节点？任何帮助将非常感激!

这里是代码文件，如果你想运行和测试的话。

主要.cpp

#include "pch.h"
#include <iostream>
#include "NTree.h"
#include <string>
using namespace std;
int main()
{
    string A("A");
    string A1("AA");
    string A2("AB");
    string A3("AC");
    string AA1("AAA");
    string AB1("ABA");
    string AB2("ABB");
    typedef NTree<string, 3> NS3Tree;

    NS3Tree root(A);

    NS3Tree nodeA1(A1);
    NS3Tree nodeA2(A2);
    NS3Tree nodeA3(A3);
    NS3Tree nodeAA1(AA1);
    NS3Tree nodeAB1(AB1);
    NS3Tree nodeAB2(AB2);
    root.attachNTree(0, &nodeA1);
    root.attachNTree(1, &nodeA2);
    root.attachNTree(2, &nodeA3);
    root[0].attachNTree(0, &nodeAA1);
    root[1].attachNTree(0, &nodeAB1);
    root[1].attachNTree(1, &nodeAB2);

    cout << "root: " << root.key() << endl;
    cout << "root[0]: " << root[0].key() << endl;
    cout << "root[1]: " << root[1].key() << endl;
    cout << "root[2]: " << root[2].key() << endl;
    cout << "root[0][0]: " << root[0][0].key() << endl;
    cout << "root[1][0]: " << root[1][0].key() << endl;
    cout << "root[1][1]: " << root[1][1].key() << endl;


    //test traversal
    PreOrderVisitor<string> v1;
    PostOrderVisitor<string> v2;
    cout << "Pre-order traversal:" << endl;
    root.transverseDepthFirst(v1);
    cout << endl;
    cout << "Post-order traversal:" << endl;
    root.transverseDepthFirst(v2);
    return 0;
}

树.h

#pragma once
#include <stdexcept>
#include "TreeVisitor.h"
template<class T,int N>
class NTree {
private:
    const T* fKey;
    NTree<T, N>* fNodes[N];
    NTree() :fKey((T*)0) {
        for (int i = 0; i < N; i++) {
            fNodes[i] = &NIL;
        }
    };
public:
    static NTree<T, N> NIL;
    NTree(const T& aKey);
    ~NTree();

    bool isEmpty() const;
    const T& key() const;

    NTree& operator[](int aIndex) const;
    void attachNTree(int aIndex, NTree<T, N>* aNTree);
    NTree* detachNTree(int aIndex);
    void transverseDepthFirst(const TreeVisitor<T>& aVisitor)const;
};

template<class T,int N>
void NTree<T, N>::transverseDepthFirst(const TreeVisitor<T>& aVisitor)const {
    /*for (int i = 0; i < N ; i++) {
        if (!isEmpty()) {
            aVisitor.preVisit(key());
            fNodes[i]->transverseDepthFirst(aVisitor);
            aVisitor.postVisit(key());
        }
    }*/
    if (!isEmpty()) {
        aVisitor.preVisit(key());
        fNodes[0]->transverseDepthFirst(aVisitor);
        aVisitor.postVisit(key());
        fNodes[1]->transverseDepthFirst(aVisitor);
    }

}
template<class T,int N>
NTree<T, N>::~NTree() {
    for (int i = 0; i < N; i++) {
        if (fNodes[i] != &NIL) {
            delete fNodes[i];
        }
    }
}
template<class T,int N>
NTree<T, N>::NTree(const T& aKey) :fKey(&aKey){
    for (int i = 0; i < N; i++) {
        fNodes[i] = &NIL;
    }
}
template<class T,int N>
void NTree<T, N>::attachNTree(int aIndex, NTree<T, N>* aNTree) {
    if (isEmpty()) {
        throw std::domain_error("Empty NTree");
    }
    if (fNodes[aIndex] != &NIL) {
        throw std::domain_error("Non-empty sub tree");
    }
    fNodes[aIndex] = new NTree<T, N>(*aNTree);
}

template<class T,int N>
NTree<T, N>* NTree<T, N>::detachNTree(int aIndex) {
    if (isEmpty()) {
        throw std::domain_error("Empty NTree");
    }
    NTree<T, N>& Result = *fNodes[aIndex];
    fNodes[aIndex] = &NIL;
    return &Result;
}

template<class T,int N>
NTree<T, N>& NTree<T, N>::operator[](int aIndex) const {
    return *fNodes[aIndex];
}


template<class T,int N>
bool NTree<T,N>::isEmpty() const {
    return this == &NIL;
}

template<class T,int N>
const T& NTree<T, N>::key() const {
    if (isEmpty()) {
        throw std::domain_error("Empty NTree");
    }
    return *fKey;
}

template<class T,int N>
NTree<T,N> NTree<T,N>::NIL;

TreeVisitor.h

#pragma once
#include<iostream>

template <class T>
class TreeVisitor {
public:
    virtual ~TreeVisitor(){}
    virtual void preVisit(const T& aKey) const{}
    virtual void postVisit(const T& aKey) const{}
    virtual void inVisit(const T& aKey) const{}

    virtual void visit(const T& aKey)const 
    {
        std::cout << aKey << " ";
    }
};

template<class T>
class PostOrderVisitor :public TreeVisitor<T> {
public:
    virtual void postVisit(const T& aKey) const {
        this->visit(aKey);
    }
};

template<class T>
class PreOrderVisitor :public TreeVisitor<T> {
public:
    virtual void preVisit(const T& aKey) const {
        this->visit(aKey);
    }
};

template<class T>
class InOrderVisitor :public TreeVisitor<T> {
public:
    virtual void inVisit(const T& aKey) const {
        this->visit(aKey);
    }
};

Answer 1

template<class T,int N> void NTree<T, N>::transverseDepthFirst(const TreeVisitor<T>& aVisitor)

必须是:

template<class T,int N>
void NTree<T, N>::transverseDepthFirst(const TreeVisitor<T>& aVisitor)const {
    if (!isEmpty()) {
      aVisitor.preVisit(key());
      for (int i = 0; i < N ; i++) {
         fNodes[i]->transverseDepthFirst(aVisitor);
      }
      aVisitor.postVisit(key());
    }
}

结果如预期:

root: A
root[0]: AA
root[1]: AB
root[2]: AC
root[0][0]: AAA
root[1][0]: ABA
root[1][1]: ABB
Pre-order traversal:
A AA AAA AB ABA ABB AC 
Post-order traversal:
AAA AA ABA ABB AB AC A

警告你的树不是

          A
       /   \    \
     AA   AB    AC
     /     \     \
   AAA    ABA     ABB

但是

          A
       /  |  \
     AA   AB  AC
    /    /  \
   AAA  ABA ABB

因为 ABB 附加到 AB 而不是 AC:root[1][1]: ABB而不是 root[2][0]: ABB