?? c++.cpp
字號:
#include<iostream>
#include<string>
using namespace std;
int n=0;
template <class T>
struct BiNode {
T data;
BiNode<T> *lchild, *rchild;
};
template <class T>
class BiTree
{
public:
BiTree( );
~BiTree(void);
BiNode<T>* Getroot();
void PreOrder(BiNode<T> *root);
void InOrder(BiNode<T> *root);
void PostOrder(BiNode<T> *root);
void LeverOrder(BiNode<T> *root);
void PreOrdercount(BiNode<T>*root);
private:
BiNode<T> *root;
BiNode<T> *Creat( );
void Release(BiNode<T> *root);
};
template<class T>
BiTree<T>::BiTree( )
{
//int m;
//cout<<"請輸入結點的個數(shù):"<<endl;
//cin>>m;
this->root = Creat( );
}
template<class T>
BiTree<T>::~BiTree(void)
{
Release(root);
}
template<class T>
BiNode<T>* BiTree<T>::Getroot( )
{
return root;
}
template<class T>
void BiTree<T>::PreOrder(BiNode<T> *root)
{
if(root==NULL) return;
else{
cout<<root->data<<" ";
PreOrder(root->lchild);
PreOrder(root->rchild);
}
}
template <class T>
void BiTree<T>::InOrder (BiNode<T> *root)
{
if (root==NULL) return;
else{
InOrder(root->lchild);
cout<<root->data<<" ";
InOrder(root->rchild);
}
}
template <class T>
void BiTree<T>::PostOrder(BiNode<T> *root)
{
if (root==NULL) return;
else{
PostOrder(root->lchild);
PostOrder(root->rchild);
cout<<root->data<<" ";
}
}
template <class T>
void BiTree<T>::LeverOrder(BiNode<T> *root)
{
const int MaxSize = 100;
int front = 0;
int rear = 0; //采用順序隊列,并假定不會發(fā)生上溢
BiNode<T>* Q[MaxSize];
BiNode<T>* q;
if (root==NULL) return;
else{
Q[rear++] = root;
while (front != rear)
{
q = Q[front++];
cout<<q->data<<" ";
if (q->lchild != NULL) Q[rear++] = q->lchild;
if (q->rchild != NULL) Q[rear++] = q->rchild;
}
}
}
template <class T>
BiNode<T>* BiTree<T>::Creat( )
{
BiNode<T>* root;
T ch;
cout<<"請輸入創(chuàng)建一棵二叉樹的結點數(shù)據(jù)"<<endl;
cin>>ch;
if (ch=="#") root = NULL;
else{
root = new BiNode<T>; //生成一個結點
root->data=ch;
root->lchild = Creat( ); //遞歸建立左子樹
root->rchild = Creat( ); //遞歸建立右子樹
}
return root;
}
template<class T>
void BiTree<T>::Release(BiNode<T>* root)
{
if (root != NULL){
Release(root->lchild); //釋放左子樹
Release(root->rchild); //釋放右子樹
delete root;
}
}
template<class T>
void BiTree<T>::PreOrdercount(BiNode<T>*root)
{ if(root)
{
if(!root->lchild&&root->rchild||root->lchild&&!root->rchild) n++;
PreOrdercount(root->lchild);
PreOrdercount(root->rchild);
}
}
int main()
{
BiTree<string> bt;
char e;
BiNode<string>* root = bt.Getroot( );
while(true)
{
cout<<"*************************************"<<endl;
cout<<"*\t\t實現(xiàn)二叉樹的基本功能\t\t*"<<endl;
cout<<"*\t\t 1.前序遍歷\t\t\t*"<<endl;
cout<<"*\t\t 2.中序遍歷\t\t\t*"<<endl;
cout<<"*\t\t 3.后序遍歷\t\t\t*"<<endl;
cout<<"*\t\t 4.層序遍歷\t\t\t*"<<endl;
cout<<"*\t\t 5.計算單枝節(jié)點數(shù)\t\t*"<<endl;
cout<<"*\t\t 6.退出\t\t\t*"<<endl;
cout<<"*************************************"<<endl;
do{
cout<<"請輸入你的選擇(1-6):";
cin>>e;
}while(e<'1'||e>'6');
switch(e)
{
case'1':
cout<<"前序遍歷:"<<endl;
bt.PreOrder(root);
cout<<endl;
break;
case'2':
cout<<"中序遍歷:"<<endl;
bt.InOrder(root);
cout<<endl;
break;
case'3':
cout<<"后序遍歷:"<<endl;
bt.PostOrder(root);
cout<<endl;
break;
case'4':
cout<<"層序遍歷:"<<endl;
bt.LeverOrder(root);
cout<<endl;
break;
case'5':
cout<<"計算單枝節(jié)點數(shù):";
bt.PreOrdercount(root);
cout<<n<<endl;
break;
case'6':
return 0;
}
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -