ep7_14.cpp
上传用户:wxcui2006
上传日期:2022-07-12
资源大小:1274k
文件大小:2k
源码类别:

书籍源码

开发平台:

Visual C++

  1. /*7.14  编写函数模板,用递归方法求二叉树的深度。*/
  2. #include<iostream>
  3. #include<cstdlib>
  4. using namespace std;
  5. template<typename T>class BinaryTree;
  6. template<typename T>class Node{
  7. Node<T> *lchild,*rchild;
  8. T info;
  9. public:
  10. Node(){lchild=NULL;rchild=NULL;}
  11. Node(T data,Node<T> *left=NULL,Node<T> *right=NULL){
  12. info=data;
  13. lchild=left;
  14. rchild=right;
  15. }
  16. friend class BinaryTree<T>;
  17. };
  18. template<typename T>class BinaryTree{
  19. Node<T> *root;                  //二叉树的根指针
  20. void Insert(const T &data,Node<T> * &b); //插入结点,参数为引用!
  21. void Destory(Node<T> * Current);        //删除树
  22. int Countdepth(Node<T> *btree);      //树深度计数
  23. public:
  24. BinaryTree(){root=NULL;} //空树构造函数
  25. ~BinaryTree(){Destory(root);} //析构函数
  26. void Creat(T* data,int n);                    //建立(排序)二叉树
  27. int Countdepth(){return Countdepth(root);}      //树深度计数
  28. };
  29. template<typename T> void BinaryTree<T>::Destory(Node<T> *Current){
  30. if(Current!=NULL){
  31. Destory(Current->lchild);
  32. Destory(Current->rchild);
  33. delete Current;   //后序释放根结点
  34. }
  35. }
  36. template<typename T>void BinaryTree<T>::Insert(const T &data,Node<T> * &b){
  37. if(b==NULL){ //已到空树,插入
  38. b=new Node<T>(data);
  39. if(b==NULL){
  40. cout<<"空间不足"<<endl;
  41. exit(1);
  42. }
  43. }
  44. else if(data<b->info) Insert(data,b->lchild); //小于,向左子树去查
  45.      else Insert(data,b->rchild); //大于等于,向右子树去查
  46. }
  47. template<typename T>void BinaryTree<T>::Creat(T* data,int n){//建立一棵二叉排序树
  48. for(int i=0;i<n;i++) Insert(data[i],root);
  49. }
  50. template<typename T>int BinaryTree<T>::Countdepth(Node<T> *btree){//树深度
  51. int num1,num2;
  52. if(btree==NULL)return 0;
  53. else if(btree->lchild==NULL&&btree->rchild==NULL)return 1;
  54. else{
  55. num1=Countdepth(btree->lchild)+1;
  56. num2=Countdepth(btree->rchild)+1;
  57. if(num1>num2) return num1;
  58. else return num2;
  59. }
  60. }
  61. int main(){
  62. const int n=15;
  63. int i,a[n]={10,5,15,8,3,18,13,12,14,16,20,1,4,6,9};
  64. BinaryTree<int> btree;//按排序二叉树生成,共4个层次
  65. btree.Creat(a,n);
  66. cout<<"输入数据:"<<endl;
  67. for(i=0;i<n;i++) cout<<a[i]<<'t';
  68. cout<<endl<<"树深度计数:"<<endl;
  69. cout<<btree.Countdepth()<<endl;    //树深度计数:4
  70. return 0;
  71. }