C++ 树数据类

• 下载演示项目 - 4.7 KB

引言

不久前，在我最近的一个项目中，我需要一个树类来表示数据结构。我在网上到处搜索，没有找到任何可以接受的解决方案。树是一种不像数组或列表那样简单的结构，所以不幸的是，STL 没有它，我不得不自己写一个。

我将实现分为两个主要部分：Data 和 Node。 Data 对象负责保存数据，而 Node (Tree) 负责树结构。

数据对象

Data 类的目的是保存实际数据。它保存数据，直到所有对它的实际引用都消失。这是通过引用计数（类似COM）完成的。我知道有些人可能觉得这毫无价值且无用，但它可以使数据更加封装和安全。该实现分为两个类，Data 和 Ref（引用）。所有数据都存储在 Data 类中。所有工作都由 Ref 类完成，它操作数据类

template <class Type> class Data {
private:
...// all methods and variables are private
   friend class Ref<Type>; // Ref class will manipulate us
};
template <class Type> class Ref {
    Ref(Type *p);
    Ref();
    Ref(const Ref<Type> rhs);
    //destructor
    virtual ~Ref();

//operators =
    Ref operator=(const Ref<Type> rhs);
    Ref operator=(const Type t);
    Ref operator=(Type *p); 
// operator ==
    bool operator==(const Ref<Type> rhs) 
// misc

    Ref Clone();
    void Release();
    bool IsNull();

// accessors to the actual data 
// (check if it's null first)
    Type *operator->();
    Type get_Data();
    operator Type();
}

树(节点) 对象

Tree 类表示树中的一个节点，所以它有父节点和子节点。这样，我用一个类来表示节点和树，所以树是没有父节点的节点，叶子是没有子节点的节点。它还有对数据的引用 (Ref)。它的实现分为两个类，NodeData 和 Tree。NodeData 对象保存父节点和子节点的实际数据，但 Tree 对象操作这些数据并提供对它们的访问。实际上，您将始终只直接使用 Tree 类。

定义

• Node - 树中的节点或叶子（也可以是根节点）
• Leaf - 没有子节点的节点
• Root - 没有父节点的节点（我们也会将其称为 Tree）
• Null - null 节点

template <class Type> class NodeData {
private:
    .... // all methods  vars are private
    friend class Tree<Type>;
}

template <class Type> class Tree {
public:
    // we'll call the tree node
    typedef Tree<Type> Node;
    
    // parent
    Node Parent();
    
    // children - Nodes
    __declspec( property( get=get_Nodes) ) Node Nodes[];
    __declspec( property( get=get_Count) ) int Count;

    Node get_Nodes(int nIndex);
    int get_Count();
    
    // data acess
    __declspec( property( get=get_Data) ) Ref<Type> Data;

    operator Type();
    Type *operator->();
    Ref<Type> get_Data();

    // node functions (isLeaf and so on
    bool IsLeaf();
    bool IsNode();
    bool IsRoot();

    // comparision
    bool operator == (const Node rhs)
          { return *(NodeBase*)this==(NodeBase )rhs;};

    // node operations
    Node AddNode(const Type t); 
    void Delete();
    void DeleteNode(int nIndex);
    void DeleteNode(Node node);

    // constructors
    Tree(const Type Data);
    Tree(Type *Data);
    
    Tree();
    Tree(const Tree<Type> rhs);
    Tree(const NodeBase rhs);
    
    // destructor
    virtual ~Tree();
}

非常简单的使用示例

#include "stdio.h"
#include "tree.h"
#include "string"

using namespace std;

typedef Tree<string> StringTree;
 typedef
StringTree::Node StringNode; //


recursive function for prionitng nodes void
PrintNode(StringNode node,int nLevel) { //
	print new line fputs("\n",stdout);
	//
	print spaces for indent (2 for every level) string
	s; s.resize(nLevel*2,'
	'); fputs(s.c_str(),stdout);
	//

	print the value fputs(node.get_Data()->c_str(),stdout);
	//

	iterate through children nLevel++;
	for(int
	n= 0;n<&;node.Count;n++) {
		PrintNode(node.Nodes[n],nLevel);
	}
}

int main(int argc, char* argv[])
{
	// define the tree
	StringTree tree; 
	((string&)tree)="Root";

	//add few nodes
	StringNode node=tree;

	node.AddNode("1").AddNode("11");
	StringNode node2=node.AddNode("2");

	node2.AddNode("21").AddNode("211");
	node2.AddNode("22");
	node2.AddNode("23");
	
	node.AddNode("3");

	// print the tree
	PrintNode(tree,0);

	// wait for enter
	char buf[3];
	fputs("\nPress ENTER :",stdout);
	fgets(buf,3,stdin);
	return 0;
}

结论

所提供的 Tree 类不是最好的解决方案，也不是最好的执行者，因为它在内部使用 vector，但它灵活且易于使用。在大多数可用的 Tree 结构中，您会发现我们需要直接使用指针，并且需要填写和索引大量代码。这个非常容易使用（当然，这是有代价的）。

如果您有任何意见和看法，请在下面留言。

许可证

本文未附加明确的许可证，但可能在文章文本或下载文件本身中包含使用条款。如有疑问，请通过下面的讨论区联系作者。

作者可能使用的许可证列表可以在此处找到。