資料結構筆記-樹

相關

• 靜态查找 ：集合是固定的，沒有插入和删除
• 動态查找：集合是動态的，可能發生插入和删除
• 二分查找
  • 将複雜度降為 log ⁡ 2 N \log_2N log2​N,相當于将數組變為樹。
  • 前提：數組是排好序的

樹

定義

樹： n ( n ≥ 0 ) n (n\geq0) n(n≥0)各節點構成的有限集合

n=0時，是空樹。沒有節點也是樹。

• 非根節點可分為m個不相交的有限集合，每個集合又是一棵樹，成為原樹的子樹。
• 除了根節點，每個節點僅有一個父節點
• n個節點有n-1條邊
• 節點的度：子樹的個數
• 樹的度：所有節點中最大的度數
• 路徑和路徑長度：從節點 n 1 n_1 n1​到 n k n_k nk​的路徑為一個節點序列 n 1 , n 2 , . . . n k n_1,n_2,...n_k n1​,n2​,...nk​， n i n_i ni​是 n i + 1 n_{i+1} ni+1​的父節點。路徑所包含的邊數為路徑長度
• 節點的層次，根節點在1層。
• 樹的深度：所有節點中最大層次

二叉樹表示

兒子兄弟法可以将所有樹變為二叉樹。

二叉樹的五種基本形态

• 空樹
• 隻有根節點
• 隻有左孩子
• 隻有右孩子
• 有左，右孩子

幾種特殊的二叉樹

• 斜二叉樹(skewed Binary tree)。即連結清單，所有節點隻有一個孩子
• 完美二叉樹(perfect Binary tree) 或 滿二叉樹(full binary tree) .每層節點數量達到最大
• 完全二叉樹(complete binary tree) 對節點從上到下，從左到右進行編号，與滿二叉樹編号相同

二叉樹的性質

• 第i層最大節點數為 2 i − 1 , i ≥ 1 2^{i-1},i\geq1 2i−1,i≥1
• 深度為k的二叉樹最多有 2 i − 1 2^i-1 2i−1節點
• 對于非空二叉樹， n 0 n_0 n0​為葉子節點數， n 2 n_2 n2​是度為二的非葉子節點個數，那麼滿足 n 0 = n 2 + 1 n_0 =n_2 +1 n0​=n2​+1

存儲

完全二叉樹

• 順序存儲 i = index+1
• 節點為i，左孩子為2I,右孩子為2i+1
• 節點為i，父節點為 i/2 (向下取整)

一般二叉樹

• 連結清單存儲，用數組會造成空間浪費

樹的周遊

樹有兩大類周遊方法，深度優先和廣度優先。對于二叉樹來說，深度優先又分為先序，中序，後序三種周遊方式。如果從根開始周遊，最後回到根，每個節點會被周遊三次，對應前序，中序，後序。深度優先的周遊線路時固定的，隻是什麼時候周遊該節點是不确定的。而先中後三種是針對根節點通路順序而言的。

對于一個 n n n叉樹來說，深度優先周遊時，每個節點會被周遊 n + 1 n+1 n+1次。

F i g u r e 1 深 度 優 先 遍 曆 路 徑 Figure 1 深度優先周遊路徑 Figure1深度優先周遊路徑

遞歸周遊(針對深度優先周遊)

void preOrder(vector v ,int root){
  if(root<v.size()){
       visit(v[root]);
       preOrder(vector,root*2);
       preOrder(vector v ,root*2+1);       
  }
}
           

該順序是先周遊根節點，再周遊左子樹，最後右子樹。從根到各個葉子是從左到右的順序周遊。若要先周遊右側路徑,換一個位置即可.對于遞歸周遊，隻需要調節三條語句的順序，即可實作三種周遊。

非遞歸周遊

因為遞歸和深度周遊都使用了棧，是以可以通過遞歸來實作深度優先周遊。如果使用非遞歸實作深度優先周遊，隻需要配合一個棧即可。

• 中序周遊

Tree t;
stack s;
while(t || !s.empty()){
  while(t){
     s.push(t);
     t = t.left;
  }
  if(!s.empty()){
     t = s.top();
     s.pop();
     visit(t);
     t = t.right;
  }
}
           

• 先序周遊

Tree t;
stack s;
while(t || !s.empty()){
  while(t){
     s.push(t);
      visit(t); //在第一次遇到就進行周遊
     t = t.left;
  }
  if(!s.empty()){
    t = s.top();
    s.pop();
    // visit(t); 将此處周遊上移
    t = t.right;
  }
}
           

• 後序周遊

stack s;
tree t ,last = null;
while(t || ! s.empty()){
  while(t){
    s.push(t);
    t = t.left;
  }
  
  while(!s.empty()){
      if(!s.top.right ||(! last && s.top.right == last) || ! last ){
           t = s.top();
           s.pop();
           last = t;
           visit(t);
      }else{
         t = s.top().right；
         break;
      }
  }
  
}
           

層次周遊，廣度優先周遊

廣度優先周遊需要queue。從隊列中取出一個元素并通路，将其子節點都壓入隊列。

queue q;
Tree t;
q.push(t);
while(!q.empty()){
   t = q.front();
   q.pop();
   visit(t);
   if(t.left)
      q.push(t.left);
   if(t.right)
      q.push(t.right);
}
           

應用

深度優先周遊中，通過兩種周遊順序推測一個二叉樹樹，必須含有中序周遊。沒有中序周遊的話，無法判斷左右子樹。除非是真二叉樹(沒有度為1的節點，都是2或0)可以還原。

先序或後序周遊中找出根節點，在中序周遊中利用根節點将樹分為左右兩個。

Tree build(vector inorder ,vector post){
    Tree root = post[post.size()-1];
    int root_index = find(inorder ,root);
    vector  l_inoder = copy(inorder,0,root_index-1);
    vector l_post = copy(post,0,root_index-1);
    vector r_inorder = copy(inoder,root_index+1,inorder.size()-1);
    vector r_post = copy(post,root_index,post.size()-2);
    root ->left(l_inorder,l_post);
    root ->right (r_inorder,r_post);
    return root;
}
           

二叉搜尋樹(BST)

• 又叫二叉排序/查找樹
• 對于非空的搜尋樹：
  • 非空左子樹的所有值小于根節點的值
  • 右子樹的所有值大于根節點的值
  • 左右子樹都是二叉搜尋樹
  • 最大元素在最右端
  • 最小元素在最左端
• 二叉搜尋樹的查找效率取決于樹的高度

操作

• 插入 ，類似查找，一定插入的是葉子節點
• 删除
  • 删除葉子
    • 直接删除
  • 删除隻有一個孩子的節點
    • 孩子和爺爺相連
  • 删除兩個孩子的節點
    • 用右子樹最小節點或左子樹最大節點代替。需要将那條路徑上所有節點進行移動，直到葉子節點。

平衡二叉樹 AVL

是個查找樹

平衡因子(balance factor ,BF) BF(T)= h L − h R h_L-h_R hL​−hR​, h L h_L hL​和 h R h_R hR​分别是左右子樹的高度

AVL定義

• 空樹或者任意節點的 ∣ B F ∣ |BF| ∣BF∣不超過1

AVL調整

• 插入節點在不平衡節點的左子樹的左邊

  

• 插入節點是不平衡節點的左子樹的右側

  

• 插入節點後，可能不需要調整，但BF可能需要更新

堆 heap

優先級隊列

• 取出元素的順序是按優先級順序
• 可以用數組，連結清單，有序數組，查找樹等實作。

如果用查找樹實作，插入删除都比較省時間，但一直删除會導緻樹傾斜。

堆 定義

• 優先級隊列的完全二叉樹表示

特性

• 結構性，用數組表示完全二叉樹
• 有序性 ，任意節點都是其子樹的最大值或最小值

每條路徑是有序的

操作

全部是大根堆

• 建堆
  • 插入 ,時間複雜度較大，T(n) = O(nlogn)

vector build(vector v){
  vector heap;
  for(i=0;i<v.size();i++){
      insert(heap,v[i]);
  }
   return heap;
}
           

• 調整。類似遞歸，葉子一定是個堆，從最後一個非葉子節點開始調整，使之成堆。最壞隻需移動書中所有節點高度之和 T(n)= O(n)

vector build(vector v){
   for(i=(v.size()-1)/2 ;i>0;i--){
      tem = v[i];
       for(p=i;p*2<v.size();p=c){
           c = p*2;
           if(p*2+1<v.size() && v[p*2+1]>v[p*2]){
                v[p] = v[c];
           }
       }
        v[p] = tem;
   }
}
           

• 插入
  • 将新節點插入數組末尾，保證插入後滿足二叉樹的結構。再調整，判斷該節點是否大于其父節點，若大于則交換，直到不大于父節點或到達根節點。
  • 實作中，可以再數組下标為0的元素中設定哨兵，遠大于堆中其他元素；在與父節點交換值時，可以隻改變子節點位置處的值，不修改父節點處的值，直到停止交換才修改

insert( vector heap ,int node){
   heap.push_back(node);// 将元素插入末尾
   for(i= heap.size()-1; heap[i] >heap[i/2]; i= i/2){ // 設有哨兵，保證不會越界 heap[0]>>heap[i] (i!=0)
        heap[i] = heap[i/2]; // 将子節點處的值進行修改
   }
   heap[i] = node;
}
// T(N) = O(logN)
           

• 删除，傳回最大值
  • 要保證二叉樹的結構完整，隻能删除最後一個元素。故記錄最大元素，作為傳回值；将最後一個元素放在根節點上，與其最大的孩子進行交換，向下移動至合适的位置。

int del(vector heap){
  int max = heap[1];
  int item = heap[heap.size()-1];
  int size = heap.size()-1;
  for(parent = 1; parent *2 < size ;p = c){
    c = p*2;
    if(p*2+1 <size && heap[p*2+1]>heap[p*2]){
        c = p*2+1;
    }
    if(heap[p]<heap[c]){
       heap[p] = heap[c];
    }else{
      beak;
    }
  }
  heap[p] = item;
  return max;
}
           

哈夫曼樹(Huffman Tree)與哈夫曼編碼

哈夫曼樹是根據節點不同的查找頻率建構的搜尋樹

哈夫曼樹定義

帶權路徑長度(WPL):設二叉樹有n個葉子節點，每個葉子節點帶有權值 w k w_k wk​，從根節點到每個葉子節點的長度為 I k I_k Ik​，則每個葉子節點的帶權路徑長度之和就是 W P L = ∑ k = 1 n w k l k WPL=\sum^n_{k=1}w_kl_k WPL=k=1∑n​wk​lk​

最優二叉樹或哈弗曼樹:WPL最小的二叉樹

哈夫曼樹操作

• 建構
  • 将權重最小的兩個進行合并，生成新的節點
  • 每個子樹都是哈夫曼樹

Tree build(minHeap heap){
  Node n1,n2,n3;
  for(i=0;i<heap.szie();i++){
     n1 = heap.del();
     n2 = heap.del();
     n3 = newNode(n1,n2);
     heap.insert(n3);  
  }
}
           

• 特點
  • 沒有度為1的節點
  • n個葉子節點的哈弗曼樹共有2n-1個節點
  • 左右子樹交換後還是哈弗曼樹
  • 一組權值可能對應多個不同構的哈弗曼樹
    • 當出現節點值相同時，無論是葉子節點還是非葉子節點，權值相同時，取點順序不同會導緻樹不同

哈夫曼編碼

不等長編碼，出現的頻率高，編碼短；頻率的，編碼長。

不等長編碼要處理二義性。

• 字首碼 (prefix code)：任何字元的編碼都不是另一個字元的字首，可進行無二意的解碼
  • 要實作，所有編碼必須在葉子上

用二叉樹進行編碼

• 左孩子為0 ，右孩子為1
• 字元在葉子上。（保證無字首碼）

用字元組建一棵哈夫曼樹，左0右1，得到編碼

判斷哈夫曼編碼時

• 是否是最優的編碼
• 字元都在葉子上
• 不需要判斷有沒有度為1 的節點。反證：如果有，則不是最優編碼，某個節點隻有一個孩子，那該節點不存字元，将該節點的子節點與該節點的父節點相連，沒有影響其他節點，且葉子節點編碼長度縮短一位，即原來不是最優編碼，沖突。

并查集-集合的表示和運算

主要用于合并集合，查找元素所屬的集合

每個節點除了自身的資料外，還需要儲存期父親節點。

根的父親節點使用-1或自身等特殊标記。

為了标記每個集合元素數量，可以在跟的父節點中記錄集合元素數量的相反數，既表明了是根節點，又記錄集合中的數量元素。

操作

可以對并查集進行化簡，每個節點的父親節點是數組中的值，自身的資料用數組下标表示。如果自身資料到數組下标這個轉化較複雜，可以單獨寫一個映射。

• 初始化

for(i=0;i<n;i++)
   set[i] = -1; // 父節點且集合中隻有一個節點
           

• 查找

int find(int item ,vector set){
  int a = item,t;
  while(set[item] >0){
      item = set[item];
  }
  // 路徑壓縮
   while(a != item){
      t = set[a];
      set[a] = item;
      a = t;
  }
   retrun item;
}
           

• 合并
• 最簡單是直接合并，但會導緻樹不平衡，
• 按秩歸并
  • 将小集合并入大集合中

void  union (int a ,int b,vector set){
  int x,y;
  x = find(a,set);
  y = find(b,set);
  if(x != y){
  // 按秩歸并
  if(set[x] >set[y])
      set[y]+=set[x];
     set[x] = y;
  }else{
     set[x] +=set[y];
     set[y] =x;
  }
}
           

code技巧

1. 建樹時如何判斷根節點。周遊所有節點，标記各個節點的子節點，沒有節點指向的為根節點。
2. 判斷兩個序列形成的二叉搜尋樹是否一樣。先建一顆樹A，節點增加一個flag标記，用于記錄是否被通路過。另一個序列B從頭開始周遊，B中每個節點在已建好的樹A上進行搜尋，如果在搜尋過程中A樹上遇到了未通路的節點且不是要查找的節點，則樹不一樣。

reference

浙江大學 資料結構mook 樹 https://www.icourse163.org/learn/ZJU-93001?tid=1003013004#/learn/announce