資料結構期末復習

之前寫的代碼比較少，現在補補用來復習

二叉樹的遍歷操作（前序、中序、后序、層序），求一棵二叉樹的深度，求一棵二叉樹的葉子結點

圖的遍歷操作（深搜，廣搜），求一個圖的連通分量；

#include <iostream>

using namespace std;
struct BiNode {
    char data;
    BiNode *lchild,*rchild;
};

class BiTree {
public:
    BiTree(){root=creat();}
    ~BiTree(){Release(root);}
    void PreOrder(){PreOrder(root);}
    void InOrser(){InOrder(root);}
    void PostOrder(){PostOrder(root);}
    int getHigh(){getHigh(root);}
    void leafNum(){leafNum(root);}
private:
    BiNode* creat();
    void Release(BiNode *bt);
    void PreOrder(BiNode *bt);
    void InOrder(BiNode *bt);
    void PostOrder(BiNode *bt);
    int getHigh(BiNode *bt);
    void leafNum(BiNode *bt);
    BiNode *root;
};
BiNode* BiTree::creat(){
    BiNode *bt;
    char ch;
    cin>>ch;
    if(ch=='#')bt=NULL;
    else {
        bt=new BiNode;
        bt->data=ch;
        bt->lchild=creat();
        bt->rchild=creat();
    }
    return bt;
}
void BiTree::Release(BiNode *bt){
    if(bt==NULL) return;
    else {
        Release(bt->lchild);
        Release(bt->rchild);
        delete bt;
    }
}
void BiTree::PreOrder(BiNode *bt){
    if(bt==NULL) return;
     else {
        cout<<bt->data;
        PreOrder(bt->lchild);
        PreOrder(bt->rchild);
    }
}
void BiTree::InOrder(BiNode *bt){
    if(bt==NULL) return;
    else {
        InOrder(bt->lchild);
        cout<<bt->data;
        InOrder(bt->rchild);
    }
}
void BiTree::PostOrder(BiNode *bt){
     if(bt==NULL) return;
    else {
        PostOrder(bt->lchild);
        PostOrder(bt->rchild);
        cout<<bt->data;
    }
}
//求二叉樹的深度
int BiTree::getHigh(BiNode *bt){
    int lnum=0,rnum=0;
    if(bt==NULL) return 0;
    else{
        lnum=getHigh(bt->lchild);
        rnum=getHigh(bt->rchild);
        if(lnum>=rnum){
            return (lnum+1);
        }else{
            return (rnum+1);
        }
    }

}
/*求二叉樹的葉子結點的個數（帶回傳值）
int BiTree::leafNum(BiNode *bt){
    int num=0;
    if(bt==NULL) return 0;
    else{
        if(bt->lchild==NULL&&bt->rchild==NULL){
            return 1;
        }
        num=leafNum(bt->lchild);
        num+=leafNum(bt->rchild);
    }
    return num;
}*/


//求二叉樹的葉子結點的個數（不帶回傳值）
int num1=0;
void BiTree::leafNum(BiNode *bt){
    if(bt==NULL) return ;
    else{
        if(bt->lchild==NULL&&bt->rchild==NULL)
             num1++;
        leafNum(bt->lchild);
        leafNum(bt->rchild);
    }
}

int main()
{
        BiTree T;
        //cout<<"該二叉樹的前序遍歷為：";
        T.PreOrder();
        cout<<endl;
        //cout<<"該二叉樹的中序遍歷為：";
        T.InOrser();
        cout<<endl;
        //cout<<"該二叉樹的后序遍歷為：";
        T.PostOrder();
        cout<<endl;
        int num=T.getHigh();
        cout<<"樹的深度為；"<<num<<endl;
        /*
        int num1=T.leafNum();
        cout<<"樹的葉子結點個數："<<num1;
        */
        T.leafNum();
        cout<<"二叉樹的葉子結點："<<num1;
    return 0;
}

測驗1：

ABD##E##CF##G##
該二叉樹的前序遍歷為：ABDECFG
該二叉樹的中序遍歷為：DBEAFCG
該二叉樹的后序遍歷為：DEBFGCA
樹的深度為；3
二叉樹的葉子結點：4

測驗2：

ABCD####E##
該二叉樹的前序遍歷為：ABCDE
該二叉樹的中序遍歷為：DCBAE
該二叉樹的后序遍歷為：DCBEA
樹的深度為；4
二叉樹的葉子結點：2

圖的遍歷操作（深搜廣搜），求連通分量（）:

#include <iostream>
const int MaxSize=10;
using namespace std;
int visited[MaxSize]={0};
class MGraph{
public:
    MGraph(char a[],int n,int e);
    ~MGraph(){}
    void DFS(int v);
    void BFS(int v);
    int sum();
private:
    char vertex[MaxSize];
    int edge[MaxSize][MaxSize];
    int edgeNum,vertexNum;
};
MGraph::MGraph(char a[],int n,int e){
    int i,j;
    vertexNum=n;
    edgeNum=e;
    for(int i=0;i<vertexNum;i++){
        vertex[i]=a[i];
    }
    for(int i=0;i<vertexNum;i++){
        for(int j=0;j<vertexNum;j++){
            edge[i][j]=0;
        }
    }
    for(int k=0;k<edgeNum;k++){
        cin>>i>>j;
        edge[i][j]=edge[j][i]=1;
    }
}
void MGraph::DFS(int v){
    cout<<vertex[v]<<" ";
    visited[v]=1;
    for(int j=0;j<vertexNum;j++){
    if(edge[v][j]==1&&visited[j]==0)
        DFS(j);
    }
}
void MGraph::BFS(int v){
    int w,j,Q[MaxSize];
    int rear=-1;
    int front=-1;
    cout<<vertex[v]<<" ";
    visited[v]=1;
    Q[++rear]=v;
    while(rear!=front){
        w=Q[++front];
        for(j=0;j<vertexNum;j++){
           if(edge[w][j]==1&&visited[j]==0){
            cout<<vertex[j]<<" ";
            visited[j]=1;
            Q[++rear]=j;
           }
        }

    }
}
int MGraph::sum(){
    int sum=0;
    for(int i=0;i<vertexNum;i++){
        if(visited[i]==0){
            DFS(i);
            sum++;
        }
    }
    return sum;
}

測驗：

int main()
{
    int i;
    char ch[]={'A','B','C','D','E'};
    MGraph MG(ch,5,6);
    for(int i=0;i<MaxSize;i++){
        visited[i]=0;
    }
    cout<<"樹的深度遍歷：";
    MG.DFS(0);
    for(int i=0;i<MaxSize;i++){
        visited[i]=0;
    }
    cout<<"樹的廣度遍歷：";
    MG.BFS(0);
    cout<<endl;
    for(int i=0;i<MaxSize;i++){
        visited[i]=0;
    }
    int m=MG.sum();
    cout<<"該無向圖的連通分量為："<<m;
    return 0;
}

0 1
0 2
0 3
1 3
2 3
1 4
樹的深度遍歷：A B D C E 樹的廣度遍歷：A B C D E
A B D C E 該無向圖的連通分量為：1

測驗2：（非連通圖）

int main()
{
    int i;
    char ch[]={'A','B','C','D','E','F','G'};
    MGraph MG(ch,7,7);
    for(int i=0;i<MaxSize;i++){
        visited[i]=0;
    }
    cout<<"樹的深度遍歷：";
    MG.DFS(0);
    for(int i=0;i<MaxSize;i++){
        visited[i]=0;
    }
    cout<<"樹的廣度遍歷：";
    MG.BFS(0);
    cout<<endl;
    for(int i=0;i<MaxSize;i++){
        visited[i]=0;
    }
    int m=MG.sum();
    cout<<"該無向圖的連通分量為："<<m;
    return 0;
}

0 1
0 2
0 3
1 3
2 3
1 4
5 6
樹的深度遍歷：A B D C E 樹的廣度遍歷：A B C D E
A B D C E F G 該無向圖的連通分量為：2