二叉樹簡介及其應用

08-21

二叉樹簡介及其應用

來自專欄程序員的成長之路

OK，大家好，我又回來了，雖然前幾篇文章我們了解過樹和二叉樹（在並查集那一章裡面提過），但是還沒有仔細的認識一下這個神奇的朋友，今天帶大家走進二叉樹的世界，看看它的神奇之處和應用。

樹簡單來說就是沒有迴路的圖，入度為0的唯一頂點為根節點，以其出邊所指的另一個頂點為根的樹為其子樹。

二叉樹，每個頂點最多有兩棵子樹

而像題圖中所示的很「豐滿」的二叉樹，稱為完全二叉樹。

二叉樹的描述：

1，數組描述：按照題圖所示給二叉樹節點標記順序，可以發現，i號節點的左兒子（如果有）的編號為i*2，右兒子的編號為i*2+1,父節點的編號為i/2.

我們就可以很輕易的用數組來表示一棵二叉樹

優點：簡單明了，方便操作，隨機訪問快（因為是數組）

缺點：面對殘缺很嚴重的二叉樹，浪費空間：假設所有節點都沒有左子樹，那麼儲存n節點所消耗的空間為2^n。

2，鏈表描述：

使用結構體，結構體中有指向左兒子和右兒子的指針，如果有特殊需要也可以有指向父節點的指針，還有自身所包含的元素

優點：不存在空間浪費，可以包含複雜的信息

缺點：訪問複雜，邏輯思維需要非常的清晰

二叉樹的訪問：

前序訪問：

訪問本節點->訪問左兒子->訪問右兒子

中序訪問：

訪問左兒子->訪問本節點->訪問右兒子

後序訪問：

訪問左兒子->訪問右兒子->訪問本節點

註：可見，訪問本節點在前中後對應了什麼序列訪問

當然還有層次訪問：

一層一層的訪問，利用隊列，依次訪問本層所有節點，然後把本層所有節點的兒子入隊，本層節點出隊

二叉樹的基本概念，描述和訪問我們都知道了，他有什麼應用呢？

設置信號放大器：

問題描述：

廣播電視塔發送信號給各個地方，路途經過很多中轉站，每個中轉站最多發往兩個中轉站或目的地，在傳輸過程中有信號損失，中轉站和目的地對信號損失有最大的容忍值，可以通過在節點設置加強站來使得該點的信號和源頭的信號相同，求怎樣設置加強塔可以讓所有的中轉站和目的地的信號不低於容忍值，且加強塔數目最小：

問題輸入：

輸入節點個數和容忍值

（為了方便我們講解我們假設是一個完全二叉樹）

輸入節點個數-1個值代表按順序父子節點之間的信號損失

輸出：

加強塔的最小個數

解題思路：

我們用fromfa來表示節點i到其父節點的信號損失

我們用fromle來表示節點i到其所有葉子結點信號損失的最大值

fromfa在輸入可以得到，fromle需要我們遍歷樹才能得到，如何得到呢？

我們使用後序訪問來遍歷，因為父節點的fromle需要子節點的fromle。

在設置到葉子結點的信號損失最大值的時候，如果我們發現節點i的fromfa與fromle之和大於容忍值，說明該節點應該設置加強站了，並且將該節點的fromle設置為0，因為該點有加強站，子節點的信號損失沒有了意義。為什麼呢？因為我們是後序訪問的節點，所以我們優先訪問了i節點的所有兒子，當遞歸上來時，說明兒子節點都是沒有問題，那麼就是說是因為fromfa使得信息缺失過多，所以我們需要加強站。

給出解決代碼：

#include<bits/stdc++.h>using namespace std;struct node{ int fromfa;//來自父節點消費 int fromle;//到達葉子結點消費 }; int n,tol,icount=0; //節點個數，容忍值 node tree[1000];void init()//假設是完全二叉樹 { cout<<"輸入節點個數和最大容忍值"<<endl; cin>>n>>tol; tree[1].fromfa = 0; cout<<"輸入節點消耗"<<endl; for(int i=2;i<=n;i++) cin>>tree[i].fromfa;}void place(int i){ int z = 0;//左右子樹中距離葉子節點最遠的距離 if(i*2<=n)//有左子樹 { place(i*2); z = max(z,tree[i*2].fromle+tree[i*2].fromfa); } if(i*2+1<=n)//有右子樹 { place(i*2+1); z = max(z,tree[i*2+1].fromle+tree[i*2+1].fromfa); } if(z+tree[i].fromfa>tol) { icount++; tree[i].fromle=0; } else tree[i].fromle = z; } int main() { init(); place(1); for(int i=1;i<=n;i++) cout<<tree[i].fromle<<endl; cout<<icount<<endl; return 0; }// 2 1 2 1 1 3 2 3 1 3 1 2 2 2這是一組測試數據，節點個數和容忍值為15 5看看和計算的是否相同

好了，這就是今天的所有內容了，我們下篇文章再見了。