BinaryTree，也未尝不可。

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 :
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. {
36. }
37. {
39. }
1. ~BinaryTree()
40. {
42. }
1. void printTree()
43. {