65.9K
CodeProject 正在变化。 阅读更多。
Home

二叉搜索树模板

Prateek Kumar Dubey
starIconstarIconstarIcon
emptyStarIcon
starIcon
emptyStarIcon

3.65/5 (13投票s)

2006年5月18日

CPOL

5分钟阅读

viewsIcon

73858

downloadIcon

2842

这是一个类库，可以用来创建任何基本数据类型或类对象的二叉搜索树。

引言

很多时候，我们都需要为不同数据类型创建二叉搜索树。本文介绍了一个名为CTree的模板库的创建。template <class T> class CTree可以用来创建任何数据类型的二叉搜索树（BST）。

Using the Code

使用这个类非常简单，只需将所有头文件复制

  • Node.h
  • ListNode.h
  • LinkList.h
  • Tree.h
  • Treelib.h

到你的项目文件夹中，并在你的应用程序中包含TreeLib.h。之后，创建一个类的实例。

示例

CTree<int> objCTreeInt ; //creating an instance of class
CTree<FLOAT> objCTreeFloat ;
CTree<MYCLASS> objCTreeMyClass ;

特点

该类支持树的所有基本操作。除了基本操作外，它还包括

  • bool TreeInorderWalk(CNode<T>*) ;
  • bool TreePreorderWalk(CNode<T>*) ;
  • bool TreePostorderWalk(CNode<T>*) ;
  • bool TreeInorderWalk(T & ) ;
  • bool TreePreorderWalk(T & ) ;
  • bool TreePostorderWalk(T & ) ;

这些函数执行各种遍历，并按遇到的顺序准备一个包含所有节点的链表。这些链表的指针是CTree类的一个public数据成员。

  1. CLinkList<T> *m_pListInorder ;
    调用TreeInorderWalk准备的链表的指针
  2. CLinkList<T> *m_pListPreorder ;
    调用TreePreorderWalk准备的链表的指针
  3. CLinkList<T> *m_pListPostorder ;
    调用TreePostorderWalk准备的链表的指针

这个列表还支持许多操作，例如

  • bool AddToFirst(T &);
  • bool AddToLast(T &);
  • bool DeleteFirst();
  • bool DeleteLast();
  • bool GetNode(T &, CListNode<T> **) ;

约束

在创建任何用户定义类对象的树时，必须在类中重载'=='、'='、'<'和'>'运算符，并应包含一个复制构造函数。

方法和说明

  1. bool AddRoot(T & );
    添加根元素，仅当根不存在时。
  2. bool Insert(T & );
    插入一个元素到树中，如果根不存在，也可以插入根。
  3. bool Delete(T & );
    从树中删除一个元素。
  4. bool Search(T & );
    搜索一个元素。
  5. bool Minimum(T &, T & );
    搜索树或子树的最小值，将根的内容作为IN参数传递（见代码）以找到树的最小值。
  6. bool Maximum(T &, T & );
    Minimum的对应方法。
  7. bool Successor(T &, T & );
    搜索树或子树的后继，将根的内容作为IN参数传递（见代码）以找到树的后继。
  8. bool Predecessor(T &, T & );
    Successor的对应方法。
  9. bool Parent(T &, T &) ;
    搜索树中节点的父节点。
  10. bool Left(T &, T &) ;
    搜索树中节点的左子节点。
  11. bool Right(T &, T &) ;
    搜索树中节点的右子节点。
  12. bool TreeInorderWalk(T & ) ;
    对树或子树执行中序遍历，并准备一个包含所有遇到的节点的链表。传递根的内容以遍历整个树。
  13. bool TreePreorderWalk(T & ) ;
    对树或子树执行前序遍历，并准备一个包含所有遇到的节点的链表。传递根的内容以遍历整个树。
  14. bool TreePostorderWalk(T & ) ;
    Private方法:: 对树或子树执行后序遍历，并准备一个包含所有遇到的节点的链表。传递根的内容以遍历整个树。
  15. bool DeleteTree(T & ) ;
    删除一棵树或一个子树。传递根的内容以删除整棵树。
  16. bool Delete(CNode<T>* pNode );
    从树中删除一个节点。
  17. bool Search(T &obj, CNode<T> **pOut);
    在树中搜索一个节点，并将其指针返回到out参数中（见代码）。
  18. bool Minimum(CNode<T>* , CNode<T>** );
    搜索树或子树的最小值，将指向根的指针作为IN参数传递（见代码）以找到树的最小值。最小值在OUT参数中返回（见代码）。
  19. bool Maximum(CNode<T>* , CNode<T>** );
    Minimum的对应方法。
  20. bool Successor(CNode<T>* , CNode<T>** );
    搜索节点的后继，将指向根的指针作为IN参数传递（见代码）以找到树的后继。后继在OUT参数中返回（见代码）。
  21. bool Predecessor(CNode<T>* , CNode<T>** );
    Successor的对应方法。
  22. CNode<T>* Parent(CNode<T>** pNode)
    返回指向节点父节点的指针。
  23. CNode<T>* Left(CNode<T>** pNode)
    返回指向节点左子节点的指针。
  24. CNode<T>* Right(CNode<T>** pNode)
    返回指向节点右子节点的指针。
  25. bool TreeInorderWalk(CNode<T>*) ;
    对树或子树执行中序遍历，并准备一个包含所有遇到的节点的链表。传递指向根的指针以遍历整个树。
  26. bool TreePreorderWalk(CNode<T>*) ;
    对树或子树执行前序遍历，并准备一个包含所有遇到的节点的链表。传递指向根的指针以遍历整个树。
  27. bool TreePostorderWalk(CNode<T>*) ;
    对树或子树执行后序遍历，并准备一个包含所有遇到的节点的链表。传递指向根的指针以遍历整个树。
  28. bool DeleteTree(CNode<T>*) ;
    删除一棵树或一个子树。传递指向根的指针以删除整棵树。
    此外，使用22到26条目中的方法准备的链表支持以下方法：
    1. bool AddToFirst(T &);
      在链表开头添加一个节点。
    2. bool AddToLast(T &);
      在链表末尾添加一个节点。
    3. bool DeleteFirst();
      从链表开头删除一个节点。
    4. bool DeleteLast();
      从链表末尾删除一个节点。
    5. bool GetNode(T &, CListNode<T> **) ;
      检索节点的指针。

最后

我已经测试了这个功能，适用于多种操作，但如果您发现任何错误，请随时告知我。祝您阅读愉快！

历史

  • 2006年5月18日：初始发布
Auther
© . All rights reserved.