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

书籍源码

开发平台:

Visual C++

  1. /*7.10  为二叉树类编写统计其度为2的结点数n2的成员函数,统计叶结点数n0的成员函数。并验证 n0= n2+1。*/
  2. //此题将两函数定为私有,在公有部分加接口函数
  3. #include<iostream>
  4. #include<cstdlib>
  5. using namespace std;
  6. template<typename T>class BinaryTree;
  7. template<typename T>class Node{
  8. Node<T> *lchild,*rchild;
  9. T info;
  10. public:
  11. Node(){lchild=NULL;rchild=NULL;}
  12. Node(T data,Node<T> *left=NULL,Node<T> *right=NULL){
  13. info=data;
  14. lchild=left;
  15. rchild=right;
  16. }
  17. friend class BinaryTree<T>;
  18. };
  19. template<typename T>class BinaryTree{
  20. Node<T> *root;                  //二叉树的根指针
  21. void Insert(const T &data,Node<T> * &b); //插入结点,参数为引用!
  22. void Destory(Node<T> * Current);        //删除树
  23. int Countleaf(Node<T> *btree);      //叶结点计数
  24. int CountNode2(Node<T> *btree);//度为2的结点计数
  25. public:
  26. BinaryTree(){root=NULL;} //空树构造函数
  27. ~BinaryTree(){Destory(root);} //析构函数
  28. void Creat(T* data,int n);                    //建立(排序)二叉树
  29. int Countleaf(){return Countleaf(root);}      //叶结点计数接口
  30. int CountNode2(){return CountNode2(root);}//度为2的结点计数接口
  31. };
  32. template<typename T> void BinaryTree<T>::Destory(Node<T> *Current){
  33. if(Current!=NULL){
  34. Destory(Current->lchild);
  35. Destory(Current->rchild);
  36. delete Current;   //后序释放根结点
  37. }
  38. }
  39. template<typename T>void BinaryTree<T>::Insert(const T &data,Node<T> * &b){
  40. if(b==NULL){ //已到空树,插入
  41. b=new Node<T>(data);
  42. if(b==NULL){
  43. cout<<"空间不足"<<endl;
  44. exit(1);
  45. }
  46. }
  47. else if(data<b->info) Insert(data,b->lchild); //小于,向左子树去查
  48.      else Insert(data,b->rchild); //大于等于,向右子树去查
  49. }
  50. template<typename T>void BinaryTree<T>::Creat(T* data,int n){//建立一棵二叉排序树
  51. for(int i=0;i<n;i++) Insert(data[i],root);
  52. }
  53. template<typename T>int BinaryTree<T>::Countleaf(Node<T> *btree){//叶结点计数
  54. int num1,num2;
  55. if(btree==NULL)return 0;
  56. else if(btree->lchild==NULL&&btree->rchild==NULL)return 1;
  57. else{
  58. num1=Countleaf(btree->lchild);
  59. num2=Countleaf(btree->rchild);
  60. return(num1+num2);
  61. }
  62. }
  63. template<typename T>int BinaryTree<T>::CountNode2(Node<T> *btree){//度为2的结点计数
  64. int num=0;
  65. if(btree!=NULL){
  66. if(btree->lchild!=NULL&&btree->rchild!=NULL) num+=1;;
  67. num+=CountNode2(btree->lchild);
  68. num+=CountNode2(btree->rchild);
  69. }
  70. return num;
  71. }
  72. int main(){
  73. const int n=15;
  74. int i,a[n]={10,5,15,8,3,18,13,12,14,16,20,1,4,6,9};
  75. BinaryTree<int> btree;
  76. btree.Creat(a,n);
  77. cout<<"输入数据:"<<endl;
  78. for(i=0;i<n;i++) cout<<a[i]<<'t';
  79. cout<<endl<<"叶结点计数:"<<endl;
  80. cout<<btree.Countleaf()<<endl;    //叶结点计数:8
  81. cout<<endl<<"度为2结点计数:"<<endl;
  82. cout<<btree.CountNode2()<<endl;    //度为2的结点计数:7
  83. return 0;
  84. }