编程练习——二叉树(BinaryTree)

先写一个树节点类。使用Temple也可以,不使用的话,使用特定类型,用法比较局限。不过本着“今天尽量不要做出今天不必要的决定”极限编程法制。做一个特殊类型的
BinaryTree,也未尝不可。

这里的TreeNode只有数据域。

  1. template < class T>
  2. class TreeNode
  3. {
  4. private :
  5. T data;
  6. TreeNode * left;
  7. TreeNode * right;
  8. public :
      1. TreeNode(T& data)
  9. {
  10. this ->data = data;
  11. this ->left = NULL;
  12. this ->right = NULL;
  13. }
    1. TreeNode(T& data,TreeNode left, TreeNode right)
  14. {
  15. this ->data = data;
  16. this ->left = left;
  17. this ->right = right;
  18. }
    1. ~TreeNode()
  19. {
    1. this ->left = NULL;
  20. this ->right = NULL;
  21. cout << “node (“ << this ->data<< “) destory!” <<endl;
  22. // to do
  23. }
    1. T getData()
  24. {
  25. return data;
  26. }
    1. void setData(T& data)
  27. {
  28. this ->data = data;
  29. }
    1. TreeNode * getLeft()
  30. {
  31. return left;
  32. }
    1. void setLeft(TreeNode * left)
  33. {
  34. this ->left = left;
    1. }
    1. TreeNode * getRight()
  35. {
  36. return right;
  37. }
    1. void setRight(TreeNode* right)
  38. {
  39. this ->right = right;
  40. }
      1. };
    1. 下面是BinaryTree的实现。一般来说,一个BinaryTree最重要的函数就是构造和析构。基本的函数是遍历。

下面的类只实现了中序遍历,和树形打印。析构删除节点使用的是后序删除法。

  1. template < class T>
  2. class BinaryTree
  3. {
  4. protected :
  5. TreeNode* head;
    1. void clearSubTree(TreeNode* node)
  6. {
  7. if (node != NULL)
  8. {
  9. clearSubTree(node->getLeft());
  10. clearSubTree(node->getRight());
  11. delete node;
  12. }
  13. }
    1. void printTree(TreeNode* subTree, int count)
  14. {
  15. if (subTree!=NULL)
  16. {
    1. printTree(subTree->getRight(), count+1);
  17. for ( int i = 0; i < count; i++)
  18. {
  19. cout << “ “ ;
  20. }
  21. cout <getData()<<endl;
  22. printTree(subTree->getLeft(),count+1);
  23. }
  24. }
      1. void printInMidOrder(TreeNode* subTree)
  25. {
  26. if (subTree!=NULL)
  27. {
  28. printInMidOrder(subTree->getLeft());
      1. cout <getData()<<endl;
  29. printInMidOrder(subTree->getRight());
  30. }
  31. }
  32. public :
  33. BinaryTree(T& data)
  34. {
  35. head = new TreeNode(data);
  36. }
    1. BinaryTree(TreeNode* head)
  37. {
  38. this ->head = head;
  39. }
    1. ~BinaryTree()
  40. {
  41. clearSubTree(head);
  42. }
    1. void printTree()
  43. {
  44. printTree( this ->head,0);
  45. }
    1. void printInMidOrder()
  46. {
  47. printInMidOrder( this ->head);
  48. }
  49. };
    1. 如果BinaryTree中还有插入删除操作就好了。但是如何插入,如何删除必须按照一定的规则进行。所以就有后面的二叉查找树、AVLTree、SplayTree、RedBlackTree等各种类型的二叉树。
  • 本文作者: 帐前卒
  • 本文链接: http://chillyc.info/2008/2794469/
  • 版权声明: 本博客所有文章除特别声明外,只能复制超链接地址,且必须注明出处!