编程练习——二叉树（BinaryTree）

Posted on Edited on Word count in article: 1.8k Reading time ≈ 2 mins.

先写一个树节点类。使用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)
  10. {
  11. this ->data = data;
  12. this ->left = NULL;
  13. this ->right = NULL;
  14. }
    1. TreeNode(T& data,TreeNode* left, TreeNode* right)
  16. {
  17. this ->data = data;
  18. this ->left = left;
  19. this ->right = right;
  20. }
    1. ~TreeNode()
  22. {
    1. this ->left = NULL;
  24. this ->right = NULL;
  25. cout << “node (” << this ->data<< “) destory!” <<endl;
  26. // to do
  27. }
    1. T getData()
  29. {
  30. return data;
  31. }
    1. void setData(T& data)
  33. {
  34. this ->data = data;
  35. }
    1. TreeNode * getLeft()
  37. {
  38. return left;
  39. }
    1. void setLeft(TreeNode * left)
  41. {
  42. this ->left = left;
    1. }
    1. TreeNode * getRight()
  45. {
  46. return right;
  47. }
    1. void setRight(TreeNode* right)
  49. {
  50. this ->right = right;
  51. }
      1. };
    1. 下面是BinaryTree的实现。一般来说，一个BinaryTree最重要的函数就是构造和析构。基本的函数是遍历。

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

  1. template < class T>
  2. class BinaryTree
  3. {
  4. protected :
  5. TreeNode* head;
    1. void clearSubTree(TreeNode* node)
  7. {
  8. if (node != NULL)
  9. {
  10. clearSubTree(node->getLeft());
  11. clearSubTree(node->getRight());
  12. delete node;
  13. }
  14. }
    1. void printTree(TreeNode* subTree, int count)
  16. {
  17. if (subTree!=NULL)
  18. {
    1. printTree(subTree->getRight(), count+1);
  20. for ( int i = 0; i < count; i++)
  21. {
  22. cout << " " ;
  23. }
  24. cout <getData()<<endl;
  25. printTree(subTree->getLeft(),count+1);
  26. }
  27. }
      1. void printInMidOrder(TreeNode* subTree)
  29. {
  30. if (subTree!=NULL)
  31. {
  32. printInMidOrder(subTree->getLeft());
      1. cout <getData()<<endl;
  34. printInMidOrder(subTree->getRight());
  35. }
  36. }
  37. public :
  38. BinaryTree(T& data)
  39. {
  40. head = new TreeNode(data);
  41. }
    1. BinaryTree(TreeNode* head)
  43. {
  44. this ->head = head;
  45. }
    1. ~BinaryTree()
  47. {
  48. clearSubTree(head);
  49. }
    1. void printTree()
  51. {
  52. printTree( this ->head,0);
  53. }
    1. void printInMidOrder()
  55. {
  56. printInMidOrder( this ->head);
  57. }
  58. };
    1. 如果BinaryTree中还有插入删除操作就好了。但是如何插入，如何删除必须按照一定的规则进行。所以就有后面的二叉查找树、AVLTree、SplayTree、RedBlackTree等各种类型的二叉树。