数据结构期末复习

之前写的代码比较少，现在补补用来复习

二叉树的遍历操作（前序、中序、后序、层序），求一棵二叉树的深度，求一棵二叉树的叶子结点

图的遍历操作（深搜，广搜），求一个图的连通分量；

#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