資料結構-圖結構轉化為二叉樹

• 不多bb先上代碼

首先聲明這個圖不是連通圖，存在3個連通分支

#include<iostream>
using namespace std;
struct TreeNode{
    int data;
    struct TreeNode* f;
    struct TreeNode* s;
};
char name[13]={'a','b','c','d','e','f','g','h','i','j','k','l','m'};//data[a],a号點的名字
struct G{
    int n;
    int weight[20][20];
};
struct G* creat(){
    struct G* G=new struct G;
    cin>>G->n;
    for(int a=0;a<G->n;a++){
        for(int b=0;b<G->n;b++){
            cin>>G->weight[a][b];
        }
    }
    return G;
};
struct TreeNode* creatNode(int data ){
    struct TreeNode* head=new struct TreeNode;
    head->data=data;
    head->s=NULL;
    head->f=NULL;
    return head;
};
void fun1(struct G *G,struct TreeNode ** head,int *flag,int dian){
    int f=1;//g==1 通路了第一個孩子 g==0 沒有通路第一個；
    flag[dian]=1;
    struct TreeNode *pr=NULL;
    for(int a=0;a<G->n;a++){
        if(G->weight[dian][a]==1&&flag[a]!=1){
            struct TreeNode* p=creatNode(a);
            if(f==1){
                (*head)->f=p;
                f=0;
            }else{
                pr->s=p;
            }
            pr=p;
            fun1(G,&p,flag,a);
        }
    }
}
void fun(struct G* G ,struct TreeNode**head,int *flag){
    struct TreeNode* pr=NULL;
    for(int a=0;a<G->n;a++){
        if(flag[a]!=1){
            struct TreeNode*p=creatNode(a);
            if(*head==NULL)*head=p;
            else {
                pr->s=p;
            }
            pr=p;
            fun1(G,&p,flag,a);
        }
    }
}
void xian(struct TreeNode* head){
    if(head==NULL)return ;
    cout<<name[head->data]<<' ';
    xian(head->f);
    xian(head->s);
}
void hou(struct TreeNode *head){
    if(head==NULL)return ;
    hou(head->f);
    cout<<name[head->data]<<' ';
    hou(head->s);
}
main(){
    struct G* G=creat();
    int *flag= new int[G->n];
    for(int a=0;a<G->n;a++){
        flag[a]=0;
    }
    struct TreeNode* head=NULL;
    fun(G,&head,flag);
    xian(head);
    cout<<endl;
    hou(head);
}
/*
    13
    0 1 1 0 0 1 0 0 0 0 0 1 0
    1 0 0 0 0 0 0 0 0 0 0 0 1
    1 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 1 0 0 0 0 0 0 0 0
    0 0 0 1 0 0 0 0 0 0 0 0 0
    1 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 1 1 0 1 0 0
    0 0 0 0 0 0 1 0 0 0 1 0 0
    0 0 0 0 0 0 1 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 1 1
    0 0 0 0 0 0 1 1 0 0 0 0 0
    1 0 0 0 0 0 0 0 0 1 0 0 1
    0 1 0 0 0 0 0 0 0 1 0 1 0


0 1 12 9 11 2 5 3 4 6 7 10 8
xian:
a b m j l c f d e g h k i
zhong:
l j m b c f a e d k h i g
*/

           

這個算法真的花費了我好多腦力，注意事項：

思路

• 如果這個圖不是連通圖需要一個函數把每個連通分量都“合在”一個二叉樹中（這是fun()的功能）
• 建立一個圖 這個很簡單你們都會
• fun（）将周遊圖的每一個連通分支同時以一個連通分支的其中一個點作為根節點調用fun1（）函數來周遊這個連通分支中的所有點
• fun1（）函數是個深度優先的周遊 但要值得注意的是first這個變量代表的意思：時候周遊了這個點的下一個點（賦給左孩子）否則（給右孩子）而且永遠有一個單獨的指針指向我們新建立的節點！！這是是最關鍵的！（反正我在這弄了好久）

注意事項

• 簡單說一下fun（）函數 的最關鍵的部分：建立一個節點存儲第一個點（一定是第一個點）如果head沒有東西，那就給head 因為這是我們在外界函數的頭！如果*head有東西 那就給 目前活躍的節點（）的右孩子 這是因為我們是兄弟啊 不管怎麼說我都會以這個新創的節點為活躍節點
• fun1（）函數 最關鍵的部分：我們的父親（頭結點已經知道了）來了，我們要接到父親的身上。（記住：遞歸函數調用的時候有可能回來的）要記錄是否通路了第一個孩子将其賦給左孩子 否則賦給活躍節點的右兄弟！

趕緊寫代碼吧