C++ -實作資料結構-樹

用指標、類別、template 製作的樹資料結構，功能較基本，可依需求更改和添加。

tree.h

#ifndef __TREE_H
#define __TREE_H

#include <map>
#include <vector>
using namespace std;

template<class T>
class TreeNode
{
private:
	TreeNode(int nNodeID);
	~TreeNode();
private:
	int m_nNodeID;
	TreeNode<T>* m_pParent;
	vector<TreeNode<T>*> m_vecChild;
	T m_Data;
public:
	int GetNodeID();
	int GetChildNum();
	TreeNode<T>* GetChild(int id);
	bool AddChild(TreeNode<T>* pNewChild);
	bool SetParent(TreeNode<T>* pParent);
	TreeNode<T>* GetParent();
	void SetData(T data);
	T GetData();
	void Print(int nLevel);

	template<class T>
	friend class Tree;
};
template<class T>
class Tree
{
public:
	Tree();
	~Tree();
private:
	TreeNode<T>* m_pRoot;
	map<int, TreeNode<T>*> m_mapNode;
private:
	TreeNode<T>* GetNode(int nNodeID);	//取得節點
public:
	bool AddChild(int nParent, int nChild);	//加入節點
	int GetLeafNum();	//取得葉子節點的數量
	int GetRoot();		//取得根節點
	int GetChildNum(int nNodeID);	//取得某節點的孩子數量
	int Distance(int nNodeID);	//取得某節點的高度
	void PrintTree(int nNodeID);	//印出
	void SetData(int nNodeID, T data);
	T GetData(int nNodeID);
	void Destroy();
};

#endif

tree.cpp

#include <iostream>
#include "tree.h"


template<class T>
TreeNode<T>::TreeNode(int nNodeID)
{
	m_pParent = 0;
	m_nNodeID = nNodeID;
}
template<class T>
TreeNode<T>::~TreeNode()
{

}
template<class T>
int TreeNode<T>::GetNodeID()
{
	return m_nNodeID;
}
template<class T>
bool TreeNode<T>::AddChild(TreeNode<T>* pNewChild)
{
	bool bHave = false;		//是否已經有這個子節點

	TreeNode<T>* pChild = 0;
	typename vector<TreeNode<T>*>::iterator it;
	for (it = m_vecChild.begin(); it != m_vecChild.end(); it++)
	{
		pChild = *it;
		if (pChild->GetNodeID() == pNewChild->GetNodeID())
		{
			bHave = true;
			break;
		}
	}

	if (bHave)
		return false;

	m_vecChild.push_back(pNewChild);
	return true;
}
template<class T>
bool TreeNode<T>::SetParent(TreeNode<T>* pParent)
{
	if (GetParent() != 0)	//已經有父節點了
		return false;		//error

	m_pParent = pParent;
	return true;
}
template<class T>
TreeNode<T>* TreeNode<T>::GetParent()
{
	return m_pParent;
}
template<class T>
int TreeNode<T>::GetChildNum()
{
	return (int)m_vecChild.size();
}
template<class T>
TreeNode<T>* TreeNode<T>::GetChild(int id)
{
	if (id < 0 || id >= (int)m_vecChild.size())
		return 0;

	return m_vecChild[id];
}
template<class T>
void TreeNode<T>::SetData(T data)
{
	m_Data = data;
}
template<class T>
T TreeNode<T>::GetData()
{
	return m_Data;
}
template<class T>
void TreeNode<T>::Print(int level)
{
	for (int i = 0; i < level; i++)
		std::cout << "-";

	std::cout << m_nNodeID << std::endl;

	TreeNode<T>* pChild = 0;
	typename vector<TreeNode<T>*>::iterator it;
	for (it = m_vecChild.begin(); it != m_vecChild.end(); it++)
	{
		pChild = *it;
		pChild->Print(level + 1);
	}
}
//
template<class T>
Tree<T>::Tree()
{
	m_pRoot = 0;
}
template<class T>
Tree<T>::~Tree()
{
	Destroy();
}
//取得節點
template<class T>
TreeNode<T>* Tree<T>::GetNode(int nNodeID)
{
	if (m_mapNode.find(nNodeID) != m_mapNode.end())		//節點已存在
		return m_mapNode[nNodeID];

	//create node
	TreeNode<T>* newNode = new TreeNode<T>(nNodeID);
	m_mapNode[nNodeID] = newNode;
	return newNode;
}
//加入節點
template<class T>
bool Tree<T>::AddChild(int nParent, int nChild)
{
	TreeNode<T>* pParent = GetNode(nParent);
	TreeNode<T>* pChild = GetNode(nChild);

	if (pChild->GetParent() != 0)	//已經有父節點
		return false;

	if (pParent->AddChild(pChild) == false)	//已經有這個子節點
		return false;

	pChild->SetParent(pParent);

	if (pParent->GetParent() == 0)
		m_pRoot = pParent;

	return true;
}
//取得某節點的孩子數量
template<class T>
int Tree<T>::GetChildNum(int nNodeID)
{
	TreeNode<T>* pNode = GetNode(nNodeID);
	if (pNode == 0)
		return -1;

	return pNode->GetChildNum();

}
//取得某節點的高度
template<class T>
int Tree<T>::Distance(int nNodeID)
{
	TreeNode<T>* pNode = GetNode(nNodeID);
	if (pNode == 0)
		return 0;

	int nChildNum = GetChildNum(nNodeID);
	if (nChildNum == 0)
		return 0;

	int nDepthMax = 0;
	int nDepth = 0;
	TreeNode<T>* pChild = 0;

	for (int k = 0; k < nChildNum; k++)
	{
		pChild = pNode->GetChild(k);
		nDepth = Distance(pChild->GetNodeID()) + 1;
		if (nDepth > nDepthMax)
			nDepthMax = nDepth;
	}
	return nDepthMax;
}
template<class T>
void Tree<T>::Destroy()
{
	TreeNode<T>* pNode;
	typename map<int, TreeNode<T>*>::iterator it;
	for (it = m_mapNode.begin(); it != m_mapNode.end(); it++)
	{
		pNode = it->second;
		if (pNode != 0)
		{
			delete pNode;
			pNode = 0;
		}
	}

	m_mapNode.clear();
}
//取得根節點
template<class T>
int Tree<T>::GetRoot()
{
	if (m_pRoot == 0)
		return -1;

	return m_pRoot->GetNodeID();
}
//取得葉子節點的數量
template<class T>
int Tree<T>::GetLeafNum()
{
	int nLeafNum = 0;

	TreeNode<T>* pNode;
	typename map<int, TreeNode<T>*>::iterator it;
	for (it = m_mapNode.begin(); it != m_mapNode.end(); it++)
	{
		pNode = it->second;

		if (pNode->GetChildNum() == 0)
			nLeafNum++;
	}

	return nLeafNum;
}
//印出
template<class T>
void Tree<T>::PrintTree(int nNodeID)
{
	TreeNode<T>* pNode = GetNode(nNodeID);
	if (pNode == 0)
		return;

	pNode->Print(0);
}
template<class T>
void Tree<T>::SetData(int nNodeID, T data)
{
	TreeNode<T>* pNode = GetNode(nNodeID);
	if (pNode == 0)
		return;

	pNode->SetData(data);
}
template<class T>
T Tree<T>::GetData(int nNodeID)
{
	TreeNode<T>* pNode = GetNode(nNodeID);
	if (pNode == 0)
		return 0.0f;

	return pNode->GetData();
}

template class Tree<float>;

main.cpp

#include <iostream>
#include "tree.h"

int main()
{
	Tree<float>* pTree = new Tree<float>();

	pTree->AddChild(0, 1);
	pTree->AddChild(0, 2);
	pTree->AddChild(0, 3);
	pTree->AddChild(7, 0);
	pTree->AddChild(1, 4);
	pTree->AddChild(1, 5);
	pTree->AddChild(3, 6);

	pTree->SetData(0, 0.1f);	//因為使用了 template ，所以可以儲存自訂資料
	cout <<"data = " << pTree->GetData(0) << endl;

	int nRoot = pTree->GetRoot();
	cout << "root = " << nRoot << endl;

	cout << "print tree:" << endl;
	pTree->PrintTree(nRoot);

	delete pTree;

	system("pause");
	return 0;
}