資料結構第五章總結

    本章我們學習了樹與二叉樹，樹對于我來說是一種新的概念，雖然它本身的結構比較簡單，但是在認清一些概念的時候還是要費上一點功夫，我們學習到的有樹的基本術語，二叉樹的定義這些概念性的東西，

而後主要學習的是二叉樹。二叉樹的3個性質一開始上課時會因為概念不清晰而覺得一下子有點難了解，過後認真回顧一下書本，并畫了一下圖來數一下，以小見大的方式來了解就不費吹灰之力。然後便是老生

常談的存儲結構。存儲結構分為：順序存儲和鍊式存儲。   

    然後學習到周遊二叉樹和線索二叉樹。

   周遊二叉樹的算法描述有三種：先序、中序、後序。

   其中可能中序有點難了解，以下是我了解的過程：

分享一下上課時老師和我們講解的深入虎穴的題目：

7-2 深入虎穴 (30 分)  

著名的王牌間諜 007 需要執行一次任務，擷取敵方的機密情報。已知情報藏在一個地下迷宮裡，迷宮隻有一個入口，裡面有很多條通路，每條路通向一扇門。每一扇門背後或者是一個房間，或者又有很多條路，同樣是每條路通向一扇門…… 他的手裡有一張表格，是其他間諜幫他收集到的情報，他們記下了每扇門的編号，以及這扇門背後的每一條通路所到達的門的編号。007 發現不存在兩條路通向同一扇門。

内線告訴他，情報就藏在迷宮的最深處。但是這個迷宮太大了，他需要你的幫助 —— 請程式設計幫他找出距離入口最遠的那扇門。

輸入格式：

輸入首先在一行中給出正整數 N（<），是門的數量。最後 N 行，第 i 行（1）按以下格式描述編号為 i 的那扇門背後能通向的門：

K D[1] D[2] ... D[K]
           

其中 

K

 是通道的數量，其後是每扇門的編号。

輸出格式：

在一行中輸出距離入口最遠的那扇門的編号。題目保證這樣的結果是唯一的。

輸入樣例：

13
3 2 3 4
2 5 6
1 7
1 8
1 9
0
2 11 10
1 13
0
0
1 12
0
0
           

輸出樣例：

12                

代碼分解如下：
   老師是采用指針根據門的數量配置設定空間并指向其後跟着的門的方法，十分新穎。      

typedef struct{
    int doors;//門的數量
    int*p;//指向後面的門的編号序列
     
     
}node;      

而後則是讀入門的數量以及門的資訊

int input(node*a,int n) 
{//讀入n扇門的資訊給a數組，同時傳回根所在的門牌号 （下标） 
    int i,j;
    bool*vi;
    vi=new bool[n+1];
    for(i=1;i<=n;i++)//初始化vi數組的全部元素為false 
     vi[i]=false;
  
  for(i=1;i<=n;i++)//讀入n扇門的資訊
  { cin>>a[i].doors;
    if(a[i].doors!=0)
    {
    a[i].p=new int[a[i].doors];//為a【i】.p申請空間    
    for(j=1;j<=a[i].doors;j++){
        cin>>a[i].p[j-1];
        vi[a[i].p[j-1]] =true;        
    
      }//for
     }//if
     else//doors為0的情況
     a[i].p=NULL; 
    
    
   }//外for
   for(i=1;i<=n;i++)
   if(!vi[i]) 
   return i;//找到根節點所在的下标
    
}       

周遊過程

int level(node*a,int r)
{//從a[r]開始對a數組進行層次周遊并傳回周遊的最後一個結點的編号
  queue<int> q;
  int t,i;
  q.push(r);
  
  while(!q.empty()){
      t=q.front();
      q.pop();
      if(a[t].doors!=0){//t号門後面還有門,後面的門就入隊 
           for(i=0;i<a[t].doors;i++)
              q.push(a[t].p[i]);  
          
      }
      
      
  }     return t;
 
}      

完整代碼：

#include<iostream>
#include<queue>
using namespace std;


typedef struct{
    int doors;//門的數量
    int*p;//指向後面的門的編号序列
     
     
}node;



int input(node*a,int n) 
{//讀入n扇門的資訊給a數組，同時傳回根所在的門牌号 （下标） 
    int i,j;
    bool*vi;
    vi=new bool[n+1];
    for(i=1;i<=n;i++)//初始化vi數組的全部元素為false 
     vi[i]=false;
  
  for(i=1;i<=n;i++)//讀入n扇門的資訊
  { cin>>a[i].doors;
    if(a[i].doors!=0)
    {
    a[i].p=new int[a[i].doors];//為a【i】.p申請空間    
    for(j=1;j<=a[i].doors;j++){
        cin>>a[i].p[j-1];
        vi[a[i].p[j-1]] =true;        
    
      }//for
     }//if
     else//doors為0的情況
     a[i].p=NULL; 
    
    
   }//外for
   for(i=1;i<=n;i++)
   if(!vi[i]) 
   return i;//找到根節點所在的下标
    
} 

int level(node*a,int r)
{//從a[r]開始對a數組進行層次周遊并傳回周遊的最後一個結點的編号
  queue<int> q;
  int t,i;
  q.push(r);
  
  while(!q.empty()){
      t=q.front();
      q.pop();
      if(a[t].doors!=0){//t号門後面還有門,後面的門就入隊 
           for(i=0;i<a[t].doors;i++)
              q.push(a[t].p[i]);  
          
      }
      
      
  }     return t;
 
}


int main()
{ node *a;//存儲整棵樹
  int i,j,k;
  int n,root;
  cin>>n;
  a=new node[n+1];
  root=input(a,n);
  //cout<<root<<endl;
  cout<<level(a,root)<<endl;
  return 0;
}      

   最後是哈夫曼樹的構造

   在森林中選兩棵根節點權值最小的樹作為左右子樹構造一顆新的二叉樹，新根的權值為左右子樹根結點的和，在森林中删除這兩棵樹，重複操作

   之後的目标：

  還沒有将哈夫曼樹掌握的很好，隻是了解到皮毛，我覺得這是我後面的增長點。而對于樹的應用其實還不是很敏感，還沒有去總結一下什麼情況

 下采用樹的結構會比較好，這是一個可以進步的地方，還有就是打碼的能力還需進一步提高，對書本上的東西還要更熟悉。看到自己的進步還是有

 點欣慰的。

轉載于:https://www.cnblogs.com/fengwanthousand/p/10809269.html