二叉查找树的基类实现（终）-白红宇

二叉查找树的基类实现（终）

阅读量：5037 次

发布时间：2019-06-12

本文共 2386 字，大约阅读时间需要 7 分钟。

下面举一个具体使用这个数据结构的例子，由于前面的缺点，这里

显得比较麻烦，也比较耗资源，但确实使用到了多态的好处

main.cpp 文件

#include 
    
     #include "BSTree.h"#include "IntClass.h"#include "StringClass.h"using namespace std;int main(){BSTree bstree;BSTree bstreeStr;bstree.insert(new IntClass(10),new StringClass("Tao",3));bstree.insert(new IntClass(5),new StringClass("Tao",3));bstree.insert(new IntClass(15),new StringClass("Lily",4));bstree.insert(new IntClass(3),new StringClass("Tom",3));bstree.insert(new IntClass(7),new StringClass("John",4));bstree.insert(new IntClass(13),new StringClass("Peter",5));bstree.insert(new IntClass(17),new StringClass("Joson",5));bstree.insert(new IntClass(2),new StringClass("Tao",3));bstree.insert(new IntClass(4),new StringClass("Tao",3));bstree.insert(new IntClass(6),new StringClass("Tao",3));bstree.insert(new IntClass(8),new StringClass("Lucy",4));bstree.insert(new IntClass(11),new StringClass("Jim",3));bstree.insert(new IntClass(14),new StringClass("Brown",5));bstree.insert(new IntClass(16),new StringClass("Tao",3));bstree.insert(new IntClass(18),new StringClass("Tao",3));bstree.insert(new IntClass(1),new StringClass("Tao",3));bstree.insert(new IntClass(9),new StringClass("Tao",3));bstree.insert(new IntClass(12),new StringClass("Tao",3));cout<<"-------------------------------------------------"<
     
      <<"The total tree is like this:"<
      
       <<"-------------------------------------------------"<
       
        <<"The sub-tree is like this:"<

输出结果如下：

附：前面要使用一个队列来进行树的层次遍历，这里将它给出，这是一个模板类

#ifndef QUEUE_H#define QUEUE_H#define MAXLEN 20#include 
    
     template
     
      class Queue{private:	T data[MAXLEN];	int head,end;public:	Queue();	bool EnQueue(T next);	T DeQueue();	bool isFull();	bool isEmpty();};#endiftemplate
      
       Queue
       
        ::Queue(){	head = 0;	end = 0;}template
        
         bool Queue
         
          ::EnQueue(T next){ if(isFull())return false; data[end] = next; end=end+1; if(end >= MAXLEN)end = 0; return true;}template
          
           T Queue
           
            ::DeQueue(){ assert(!isEmpty()); int temp=head; head=head+1; if(head>=MAXLEN) head=0; return data[temp];}template
            
             bool Queue
             
              ::isFull(){ if(end+1==head || (head==0 && end == MAXLEN-1)) return true; return false;}template
              
               bool Queue
               
                ::isEmpty(){ if(head == end)return true; return false;}