1. 首頁 > 生活百科 > >

樹的鄰接矩陣、雙親孩子表示法…… C++ 不知樹系列之初識樹( 二 )

生活百科

arrTree的矩陣  ， 行和列的編號對應節點的編號，并初始矩陣的值都為 0 。

樹的鄰接矩陣、雙親孩子表示法…… C++ 不知樹系列之初識樹

文章插圖
  • 在樹結構中，編號為 1 的節點和編號為2、3的節點存在父子關系，則把矩陣的 arrTree[1][2]和 arrTree[1][3]的位置設置為1 。也就是說 ， 行號和列號交叉位置的值如果是 1  ， 則標志著編號和行號、列號相同的節點之間有關系 。

樹的鄰接矩陣、雙親孩子表示法…… C++ 不知樹系列之初識樹

文章插圖
  • 找到樹中所有結點之間的關系，最后矩陣中的信息如下圖所示 。

樹的鄰接矩陣、雙親孩子表示法…… C++ 不知樹系列之初識樹

文章插圖
矩陣記錄了結點之間的雙向（父到子 ， 子到父）關系，最終看到是一個對稱的稀疏矩陣 ?？梢灾淮鎯ι先腔蛳氯菂^域的信息，并可以對矩陣進行壓縮存儲 。
鄰接矩陣存儲優點是實現簡單、查詢方便 。但是，如果不使用壓縮算法，空間浪費較大 。
3.1.2 編碼實現現采用鄰接矩陣方案實現對如下樹的具體存儲：
樹的鄰接矩陣、雙親孩子表示法…… C++ 不知樹系列之初識樹

文章插圖
  • 節點類型： 用來描述數據的信息 。
struct TreeNode{ //節點的編號 int code; //節點上的值 int data;};
  • 樹類型：樹類型中除了存儲節點（數據）信息以及節點之間的關系，還需要提供相應的數據維護算法 。本文僅考慮如何對樹進行存儲 。
class Tree { private:int size=7;vector<TreeNode> treeNodes;//使用矩陣存儲節點之間的關系，矩陣第一行第一列不存儲信息int matrix[7][7];//節點編號，為了方便，從 1 開始int idx=1; public:Tree() {}//初始根節點Tree(char root) {cout<<3<<endl;for(intr=1; r<this->size; r++) {for(int c=1; c<this->size; c++) {this->matrix[r][c]=0;}}TreeNode node= {this->idx,root};this->treeNodes.push_back(node);//節點的編號由內部指定this->idx++;}//獲取到根節點TreeNode getRoot() {return this->treeNodes[0];}//添加新節點int addVertex(char val) {if (this->idx>=this->size)return 0;TreeNode node= {this->idx,val};this->treeNodes.push_back(node);//返回節點編號return this->idx++;;}/** 添加節點之間的關系*/bool addEdge(int from,int to) {char val;//查找編號對應節點是否存在if (isExist(from,val) && isExist(to,val)) {//建立關系this->matrix[from][to]=1;//如果需要，可以打開雙向關系//this->matrix[to][from]=1;}}//根據節點編號查詢節點bool isExist(int code,char & val) {for(int i=0; i<this->treeNodes.size(); i++) {if (this->treeNodes[i].code==code) {val=this->treeNodes[i].data;return true;}}return false;}//輸出節點信息void showAll() {cout<<"矩陣信息"<<endl;for(intr=1; r<this->size; r++) {for(int c=1; c<this->size; c++) {cout<<this->matrix[r][c]<<" ";}cout<<endl;}cout<<"所有節點信息："<<endl;for(int i=0; i<this->treeNodes.size(); i++) {TreeNode tmp=this->treeNodes[i];cout<<"節點："<<tmp.code<<"-"<<tmp.data<<endl;//以節點的編號為行號，在列上掃描子節點char val;for(int j=1; j<this->size; j++ ) {if(this->matrix[tmp.code][j]!=0) {isExist(j,val);cout<<"\t子節點："<<j<<"-"<<val<<endl;}}}}};測試代碼：
int main() { //通過初始化根節點創建樹 Tree tree('A'); TreeNode root=tree.getRoot(); int codeB= tree.addVertex('B'); tree.addEdge(root.code,codeB); int codeC= tree.addVertex('C'); tree.addEdge(root.code,codeC); int codeD= tree.addVertex('D'); tree.addEdge(codeB,codeD); int codeE= tree.addVertex('E'); tree.addEdge(codeC,codeE); int codeF= tree.addVertex('F'); tree.addEdge(codeC,codeF); tree.showAll();}輸出結果：
樹的鄰接矩陣、雙親孩子表示法…… C++ 不知樹系列之初識樹

文章插圖
鄰接矩陣存儲方式的優點：
  • 節點存儲在線性容器中，可以很方便的遍歷所有節點 。
  • 使用矩陣僅存儲節點之間的關系 ， 節點的存儲以及其關系的存儲采用分離機制，無論是查詢節點還是關系（以節點的編號定位矩陣的行，然后在此行上以列掃描就能找到所以子節點）都較方便 。
缺點：
  • 矩陣空間浪費嚴重，雖然可以采用矩陣壓縮，但是增加了代碼維護量 。
3.2 鄰接表存儲鄰接表存儲和鄰接矩陣的分離存儲機制不同 ， 鄰接表的節點類型中除了存儲數據信息，還會存儲節點之間的關系信息 。

推薦閱讀