資料結構第五章小結

任選本章一道題目,談談你解決該題的心得體會.

同時談談你對上次制定目标的完成情況, 以及接下來的目标.

　　這一章主要是學習了二叉樹，首先說一下自己的作業情況吧

首先是深入虎穴。其實這道題之前就聽師兄提過，當時真的有點摸不着頭腦，我記得我是很早就看到了這道題，但是沒有思路，後來老師在課堂上教我們，我們一起做就還好一點，而且我記住了，下次一定要記筆記，後來回去之後重新做了好幾遍，前幾遍都是參照老師的代碼，後來就自己試着寫了一下，而且一定要好好了解題目，畫圖也挺重要的。主要是構造函數挺難的，一定要思路清晰。

int input(node *&a)
{
    int n,x,i,j;
    bool *vi; 
    cin>>n;
    a = new node[n+1];
    vi = new bool[n+1];
    for(i = 1;i<=n;i++)//将vi數組初始化為false 
        vi[i] = false;
        
    for(i = 1;i<=n;++i)
    {
        cin>>x;
        a[i].door = x;
        a[i].p = new int[x];
        for(j = 0;j<x;++j)//new的x隻能從0到x-1
        {
            cin>>a[i].p[j];//門 
            vi[a[i].p[j]]  = true;
        } 
    }
    
    //找出根在a數組的下标
    for(i = 1;i<=n;++i) 
        if(!vi[i]) break;
        
        return i;
}
int find(node *a,int root)
{
    //從a數組的root下标開始往下搜尋 
    queue<int> q;//定義用于存放待通路 的門編号的隊列 
    //根編号入隊
    q.push(root);
    int x,i;
    //當隊列不空；
    //x = 出隊
    // x後面的門号入隊
    while(!q.empty())
    {
        x = q.front();
        q.pop();
        for(i = 0;i<a[x].door;++i)
            q.push(a[x].p[i]);
    }
    //答案就是x；
    return x;
     
}      

然後是葉子節點那一道題，真的研究挺久的，而且參照了好多大佬的代碼，解讀起來特挺難的，真的看了好久，而且，自己就是，一看就會、一做就懵系列，真的挺可怕的，哈哈哈。

#include <iostream>
#include <queue>
using namespace std;
 
typedef struct TNode{
    int L;
    int R;
}Node;
 
int main(int argc, const char * argv[]) {
    int n;
    Node T[10];
    int root[10]={0};
    queue<int> tq;
    scanf("%d",&n);
    getchar();
    for (int i=0; i<n; i++) {
        char l,r;
        scanf("%c %c",&l,&r);
        if(l=='-')
            T[i].L=-1;
        else{
            T[i].L=l-'0';
            root[T[i].L]=1;
        }
        if(r=='-')
            T[i].R=-1;
        else{
            T[i].R=r-'0';
            root[T[i].R]=1;
        }
        getchar();
    }
    int rt=0;
    for(int i=0;i<n;i++){
        if(!root[i])
            rt=i;
    }
    tq.push(rt);
    while (!tq.empty()) {
        int tmp=tq.front();
        
        if (T[tmp].L!=-1) {
            tq.push(T[tmp].L);
        }
        if (T[tmp].R!=-1) {
            tq.push(T[tmp].R);
        }
        tq.pop();
        if(T[tmp].L==-1&&T[tmp].R==-1){
            printf("%d",tmp);
            if(!tq.empty()){
                printf(" ");
            }
        }
    }
    
    return 0;
}      

還有那個樹的同構，一開始真的是不懂他的意思，讀了好多遍，後來也是幫助之下，逐漸找到方法的，其實太多幫助也不是很好，有時候自己都不會思考了，再磨練一段時間吧。思路大概是這樣的

int Isomorphic(Tree R1,Tree R2){
    if((R1==Null)&&(R2==Null))      //如果為空樹則是同構的
        return 1;
         
    if(((R1==Null)&&(R2!=Null))||((R1!=Null)&&(R2==Null)))//如果一個為空一個不為空則不是同構的
         return 0;
         
    if((T1[R1].e)!=(T2[R2].e))//如果資料不同則不是同構的
         return 0;
         
     //如果左兒子都為空判斷右兒子是否同構
     if((T1[R1].left==Null)&&(T2[R2].left==Null))
         return Isomorphic(T1[R1].right,T2[R2].right);
         
     /* 如果兩棵樹左兒子都不為空并且資料還是一樣的，對左兒子進行遞歸*/
     if ( ((T1[R1].left!=Null)&&(T2[R2].left!=Null))&&((T1[T1[R1].left].e)==(T2[T2[R2].left].e)) )
        return ( Isomorphic( T1[R1].left, T2[R2].left )&&Isomorphic( T1[R1].right, T2[R2].right ) );
     /* 如果兩棵樹左兒子（一個空一個不空或者都不空）并且資料不一樣，
     那麼判斷第一棵樹的左（右）兒子是否跟第二棵樹的右（左）兒子同構 */
     else
         return ( Isomorphic( T1[R1].left, T2[R2].right)&&Isomorphic( T1[R1].right, T2[R2].left ) );
 
 }      

而且，那個哈夫曼樹挺有意思的，試了一下。

希望接下來我還可以進步。

轉載于:https://www.cnblogs.com/XJWQ/p/10810421.html