Как выглядит дерево:
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
Какие-либо советы по этому вопросу? Как остановить повтор уже прочитанного дочернего узла? Любая помощь приветствуется!
Вот файлы кода, если вы хотите запустить и протестировать.
main.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;
}
NTree.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);
}
};