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

书籍源码

开发平台:

Visual C++

  1. //【例7.15】二叉排序树查找函数。递归慢,下面给出迭代的查找算法。
  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 InOrder(Node<T> *Current);                //中序遍历
  21. void Insert(const T &data,Node<T> * &b); //插入结点,第二参数为引用!
  22. void Destory(Node<T> * Current);         //删除树
  23. Node<T>* Find(const T &data,Node<T> *b);//查找
  24. public:
  25. BinaryTree(){root=NULL;} //空树构造函数
  26. ~BinaryTree(){Destory(root);} //析构函数
  27. void Creat(T* data,int n);                    //建立(排序)二叉树
  28. void InOrder(){InOrder(root);}                //中序遍历,公有函数为接口
  29. void Find(const T &data){//查找
  30. Node<T>* temp=Find(data,root) ;
  31. if(temp==NULL) cout<<"无此数据"<<'t';
  32. else cout<<temp->info<<'t';
  33. }
  34. };
  35. template<typename T> void BinaryTree<T>::Destory(Node<T> *Current){
  36. if(Current!=NULL){
  37. Destory(Current->lchild);
  38. Destory(Current->rchild);
  39. delete Current;   //后序释放根结点
  40. }
  41. }
  42. template<typename T>void BinaryTree<T>::Insert(const T &data,Node<T> * &b){
  43. if(b==NULL){ //已到空树,插入
  44. b=new Node<T>(data);
  45. if(b==NULL){
  46. cout<<"空间不足"<<endl;
  47. exit(1);
  48. }
  49. }
  50. else if(data<b->info) Insert(data,b->lchild); //小于,向左子树去查
  51.      else Insert(data,b->rchild); //大于等于,向右子树去查
  52. }
  53. template<typename T>void BinaryTree<T>::Creat(T* data,int n){ //建立一棵二叉排序树
  54. for(int i=0;i<n;i++) Insert(data[i],root);
  55. }
  56. template<typename T>Node<T> *BinaryTree<T>::Find(const T &data,Node<T> *b){//查找
  57. if(b!=NULL){
  58. Node<T> *temp=b;
  59. while(temp!=NULL){
  60. if(temp->info==data)return temp;
  61. if(temp->info<data)temp=temp->rchild;
  62. else temp=temp->lchild;
  63. }
  64. }
  65. return NULL;
  66. }
  67. template<typename T>void BinaryTree<T>::InOrder(Node<T> *Current){
  68. if(Current!=NULL){ //递归终止条件
  69. InOrder(Current->lchild); //中序遍历左子树
  70. cout<<Current->info<<'t'; //访问根结点,注意所放位置
  71. InOrder(Current->rchild); //中序遍历右子树
  72. }
  73. }
  74. int main(){
  75. const int n=15;
  76. int i,a[n]={10,5,15,8,3,18,13,12,14,16,20,1,4,6,9};
  77. BinaryTree<int> btree;
  78. btree.Creat(a,n);
  79. cout<<"输入数据:"<<endl;
  80. for(i=0;i<n;i++) cout<<a[i]<<'t';
  81. cout<<endl<<"中序:"<<endl;
  82. btree.InOrder();    //中序遍历输出升序
  83. cout<<endl<<"查找:"<<endl;
  84. btree.Find(a[13]);
  85. btree.Find(a[2]);
  86. btree.Find(2);
  87. cout<<endl;
  88. return 0;
  89. }