#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
 
using std::string;
using std::vector;
using std::cout;
using std::endl;
 
struct Node {
	string name;
	vector<Node*> children;
 
	Node(const string& nodeName) : name(nodeName) {}
	Node* AddChild(const string& childName) {
		Node* child = new Node{ childName };
		children.push_back(child);
		return child;
	}
};
 
void PrintTree(Node* node) {
	static int depth = 0;
	for (int i = 0; i < depth; ++i) {
		cout << "  "; // Indentation for visualizing tree structure
	}
	cout << node->name << endl;
	depth++;
	for (Node* child : node->children) {
		PrintTree(child);
	}
	depth--;
}
 
// 深さ優先探索（DFS）順の出力
void PrintDFSOrder(const Node* node) {
	static int step = 1;
	cout << step++ << ". " << node->name << '\n';
	for (auto* child : node->children) {
		PrintDFSOrder(child);
	}
}
 
Node* FindNodeName(Node* node, const string& targetName) 
{
	if (node->name == targetName) {
		//見つかった
		return node;
	}
	for (Node* child : node->children) {
		//子がいたら再帰的に探す
		Node* result = FindNodeName(child, targetName);
		if (result != nullptr) {
			return result;
		}
	}
	//見つからなかった
	return nullptr;
 
}
 
Node* AddNodeByName(Node* root, const string& parentName, const string& childName)
{
	Node* parentNode = FindNodeName(root, parentName);
	if (parentNode != nullptr) {
		return parentNode->AddChild(childName);
	}
	return nullptr;
}
 
// 再帰用の内部関数
void PrintAsciiTreeImpl(const Node* node, const std::string& prefix, bool isLast)
{
	std::cout << prefix << (isLast ? "└── " : "├── ");
	std::cout << node->name << std::endl;
 
	std::string childPrefix = prefix + (isLast ? "    " : "│   ");
	for (size_t i = 0; i < node->children.size(); ++i) {
		bool childIsLast = (i + 1 == node->children.size());
		PrintAsciiTreeImpl(node->children[i], childPrefix, childIsLast);
	}
}
 
// 公開用（ルート専用）関数
void PrintAsciiTree(const Node* root)
{
	if (!root) return;
 
	// ルートは線を付けず、そのまま出す
	std::cout << root->name << std::endl;
 
	// ルートの子から線付きで描画開始
	for (size_t i = 0; i < root->children.size(); ++i) {
		bool isLast = (i + 1 == root->children.size());
		PrintAsciiTreeImpl(root->children[i], "", isLast);
	}
}
 
 
int main()
{
	Node root("A");
	AddNodeByName(&root, "A", "B");
	AddNodeByName(&root, "A", "C");
	AddNodeByName(&root, "B", "D");
	AddNodeByName(&root, "B", "E");
	AddNodeByName(&root, "C", "F");
	AddNodeByName(&root, "E", "G");
 
	//Node *child1 = root.AddChild("Child1");
	//Node *child2 = root.AddChild("Child2");
	////Node child1("Child1");
	////Node child2{ "Child2" };
	////root.children.push_back(&child1);
	////root.children.push_back(&child2);
	////std::cout << "Root node: " << root.name << std::endl;
	////for (Node* child : root.children) {
	////	std::cout << " Child node: " << child->name << std::endl;
	////}
	//Node* child3 = child1->AddChild("Child3");
	//child1->AddChild("Child4");
	//child2->AddChild("Child5");
	//child2->AddChild("Child6");
	//Node* child7 = child3->AddChild("Child7");
	//Node* child8 = child3->AddChild("Child8");
	//Node* child9 = child3->AddChild("Child9");
 
	//Node child3{ "Child3" };
	//Node child4{ "Child4" };
	//Node child5{ "Child5" };
	//Node child6{ "Child6" };
	//child1.children.push_back(&child3);
	//child1.children.push_back(&child4);
	//child2.children.push_back(&child5);
	//child2.children.push_back(&child6);
 
	//std::cout << "Root node: " << root.name << std::endl;
	//for (Node* child : root.children) {
	//	std::cout << " Child node: " << child->name << std::endl;
	//	for (Node* grandchild : child->children) {
	//		std::cout << "  Grandchild node: " << grandchild->name << std::endl;
	//	}
	//}
 
	//PrintTree(&root);
	PrintAsciiTree(&root);
 
	//cout << "\n=== 深さ優先探索の訪問順 ===\n";
	//PrintDFSOrder(&root);
	//Node* foundNode = FindNodeName(&root, "A");
	//if (foundNode == nullptr) {
	//	cout << "Not found\n";
	//	return 0;
	//}
	//else 
	//	cout << foundNode->name << endl;
 
}