findfleaves_二叉树_源码

#include <iostream> using namespace std; char check[10][2];int cnt=0,i=0; template <class elemType> class queue{ public: virtual bool isEmpty()const=0; virtual elemType gethead()const=0; virtual elemType dequeue()=0; virtual void enqueue(const elemType&x)=0; virtual ~queue(){}; }; template<class elemType> class linkqueue:public queue<elemType> { private: struct node{ elemType data; node *next; node(const elemType &x,node*N=NULL){data=x;next=N;} node():next(NULL){}; ~node(){} }; node *front,*rear; public: linkqueue(); ~linkqueue(); bool isEmpty()const; void enqueue(const elemType&x); elemType dequeue(); elemType gethead()const; }; template<class elemType> linkqueue<elemType>::linkqueue(){ front=rear=NULL; } template<class elemType> linkqueue<elemType>::~linkqueue(){ node *tmp; while (front!=rear){ tmp=front; front=front->next; delete tmp; } } template<class elemType> bool linkqueue<elemType>::isEmpty()const{ return front==NULL; } template<class elemType> elemType linkqueue<elemType>::gethead()const{ return front->data; } template<class elemType> void linkqueue<elemType>::enqueue(const elemType&x){ if (rear==NULL) front=rear=new node(x); else rear =rear->next=new node(x); } template<class elemType> elemType linkqueue<elemType>::dequeue(){ node *tmp=front; elemType value =front->data; front=front->next; if (front==NULL)rear=NULL; delete tmp; return value; } template<class T> class Btree{ public: virtual void clear()=0; virtual bool isEmpty()const=0; virtual T Root(T flag)const=0; virtual T lchild (T x,T flag)const=0; virtual T rchild (T x,T flag)const=0; virtual void preorder()const=0; virtual void postorder()const=0; virtual void levelorder()const=0; }; template<class T> class btree:public Btree<T>{ private: struct Node{ Node *left,*right; T data; Node():left (NULL),right(NULL){} Node (T item, Node*L=NULL,Node*R=NULL):data(item),left(L),right(R){} ~Node(){} }; Node *root; public: btree():root(NULL){} btree(T x){root=new Node(x);} ~btree(); void clear(); bool isEmpty()const; T Root (T flag)const; T lchild (T x,T flag)const; T rchild (T x,T flag)const; void preorder()const; void postorder()const; void midorder()const; void levelorder()const; void createtree(T flag); private: void clear(Node *&t); Node *find(T x,Node *t)const; void preorder(Node *t)const; void postorder(Node *t)const; void midorder(Node *t)const; }; template<class T> bool btree<T>::isEmpty()const{ return root==NULL; } template<class T> T btree<T>::Root(T flag)const{ if(root==NULL)return flag; else return root->data; } template<class T> void btree<T>::clear(btree<T>::Node *&t){ if (t==NULL)return; clear(t->left); clear(t->right); delete t; t=NULL; } template<class T> void btree<T>::clear(){ clear(root); } template<class T> btree<T>::~btree(){ clear(root); } template<class T> void btree<T>::preorder(btree<T>::Node*t)const{ if(t==NULL)return; cout<<t->data<<' '; preorder(t->left); preorder(t->right); } template<class T> void btree<T>::preorder()const{ preorder(root); } template<class T> void btree<T>::midorder(btree<T>::Node*t)const{ if(t==NULL)return; midorder(t->left); cout<<t->data<<' '; midorder(t->right); } template<class T> void btree<T>::midorder()const{ midorder(root); } template<class T> void btree<T>::postorder(btree<T>::Node*t)const{ if(t==NULL)return; cout<<t->data<<' '; postorder(t->left); postorder(t->right); } template<class T> void btree<T>::postorder()const{ postorder(root); } template<class T> void btree<T>::levelorder()const{ linkqueue<Node*> que; Node *tmp; que.enqueue(root); while(!que.isEmpty()){ tmp=que.dequeue(); if(!tmp->left&&!tmp->right)cout<<tmp->data<<' '; if(tmp->left){que.enqueue(tmp->left);} if(tmp->right){que.enqueue(tmp->right);} } } template<class T> typename btree<T>::Node *btree<T>::find (T x,btree<T>::Node *t)const { Node *tmp; if(t==NULL)return NULL; if(t->data==x)return t; if(tmp=find(x,t->left))return tmp; else return find(x,t->right); } template<class T> T btree<T>::lchild(T x,T flag)const { Node *tmp =find(x,root); if (tmp==NULL||tmp->left==NULL)return flag; return tmp->left->data; } template<class T> T btree<T>::rchild(T x,T flag)const { Node *tmp =find(x,root); if (tmp==NULL||tmp->right==NULL)return flag; return tmp->right->data; } template<class T> void btree <T>::createtree(T flag){ linkqueue<Node*>que; Node *tmp,*a,*b,*mid; int x; cin>>x; char arr[x][3];int findroot[x]={0}; for(int i=0;i<x;i++){ cin>>arr[i][0]>>arr[i][1]; } for(int k=0;k<x;k++){ if (arr[k][0]!=flag){findroot[arr[k][0]-'0']=1;} } for(int k=0;k<x;k++){ if (arr[k][1]!=flag){findroot[arr[k][1]-'0']=1;} } char k='0'; for(int i=0;i<x;i++){if(findroot[i]==0){k=i+'0';break;}} root=new Node(k);//findroot que.enqueue(root); while(!que.isEmpty()){ tmp=que.dequeue(); if(arr[tmp->data-'0'][0]!=flag)que.enqueue(tmp->left=new Node(arr[tmp->data-'0'][0])); if(arr[tmp->data-'0'][1]!=flag)que.enqueue(tmp->right=new Node(arr[tmp->data-'0'][1])); } } int main() { btree<char> tree1; tree1.createtree('-'); tree1.levelorder(); return 0; }