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

1. 前言

樹是一種很重要的數據結構，最初對數據結構的定義就是指對樹和圖的研究，後來才廣義化了數據結構這個概念。從而可看出樹和圖在數結構這一研究領域的重要性。

樹和圖重要的原因是，它讓電腦能建模出現實世界中更多領域裡錯綜複雜的資訊關係，讓電腦服務這些領域成為可能。

本文將和大家聊聊樹的基本概念，以及樹的物理存儲結構以及實現。

2. 基本概念

數據結構的研究主要是從 2 點出發：

  • 洞悉數據與數據之間的邏輯關係。
  • 設計一種物理存儲方案。除了存儲數據本身還要存儲數據之間的邏輯關係，並且能讓基於此數據上的演算法利用這種存儲結構達到事半功倍的效果。

當數據之間存在一對多關係時，可以使用樹來描述。如公司組織結構、家庭成員關係……
1.png

完整的樹結構除了需要描述出數據資訊，還需要描述數據與數據之間的關係。樹結構中，以節點作為數據的具體形態，邊作為數據之間關係的具體形態。

也可以說樹是由很多節點以及邊組成的集合。

如果一棵樹沒有任何節點，則稱此樹為空樹。如果樹不為空，則此樹存在唯一的根節點（root），根節點是整棵樹的起點，其特殊之處在於沒有前驅節點。如上圖值為董事長的節點。

除此之外，樹中的節點與節點之間會存在如下關係：

  • 父子關係：節點的前驅節點稱其為父節點，且只能有一個或沒有（如根節點）。節點的後驅節點稱其為子節點，子節點可以有多個。如上圖的董事長節點是市場總經理節點的父節點，反之，市場總經理節點是董事長節點的子節點。
  • 兄弟關係： 如果節點之間有一個共同的前驅（父）節點，則稱這些節點為兄弟節點。如上圖的市場總經理節點和運維總經理節點為兄弟關係。
  • 葉節點： 葉節點是沒有後驅（子）節點的節點。
  • 子樹：一棵樹也可以理解是由子節點為根節點的子樹組成，子樹又可以理解為多個子子樹組成…… 所以樹可以描述成是樹中之樹式的遞歸關係。

如下圖所示的 T 樹 。

11.png

可以理解為T1和T2子樹組成。

12.png

T1、T2又可以認為是由它的子節點為根節點的子子樹組成，以此類推，一直到葉節點為止。

樹的相關概念：

  • 節點的度： 一個節點含有子樹的個數稱為該節點的度。
  • 樹的度：一棵樹中，最大的節點的度稱為樹的度。
  • 節點的層次：同級的節點為一個層次。根節點為第1層，根的子節點為第2層，以此類推。
  • 樹的高（深）度： 樹中節點最大的層次。如上圖中的樹的最大層次為 4。

樹的類型：

  • 無序樹：樹中的結點之間沒有順序關係，這種樹稱為無序樹。
  • 有序樹：樹中任意節點的子節點之間有左右順序關係。如下圖，任一節點的左子節點值小於右子節點值。

13.png

  • 二叉樹：如果任一節點最多只有 2 個子節點，則稱此樹結構為二叉樹。上圖的有序樹也是一棵二叉樹。

  • 完全二叉樹：一棵二叉樹至多只有最下面兩層的節點的子結點可以小於 2。並且最下面一層的節點都集中在該層最左邊的若干位置上。

  • 滿二叉樹：除了葉節點，其它節點的子結點都有 2 個。如上圖中的樹也是滿二叉樹。

3. 物理存儲

可以使用鄰接矩陣和鄰接表的形式存儲樹。

3.1 鄰接矩陣存儲

鄰接矩陣是順序表存儲方案。

3.1.1 思路流程

  • 給樹中的每一個節點從小到大進行編號。如下圖，樹共有 11 個節點。

2.png

  • 創建一個11X11的名為 arrTree的矩陣 ，行和列的編號對應節點的編號，並初始矩陣的值都為 0。

3.png

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

4.png

  • 找到樹中所有結點之間的關係，最後矩陣中的資訊如下圖所示。

5.png

矩陣記錄了結點之間的雙向（父到子，子到父）關係，最終看到是一個對稱的稀疏矩陣。可以只存儲上三角或下三角區域的資訊，並可以對矩陣進行壓縮存儲。

鄰接矩陣存儲優點是實現簡單、查詢方便。但是，如果不使用壓縮演算法，空間浪費較大。

3.1.2 編碼實現

現採用鄰接矩陣方案實現對如下樹的具體存儲：

14.png

  • 節點類型： 用來描述數據的資訊。
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(int  r=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(int  r=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();
}

輸出結果：

15.png

鄰接矩陣存儲方式的優點：

  • 節點存儲在線性容器中，可以很方便的遍歷所有節點。
  • 使用矩陣僅存儲節點之間的關係，節點的存儲以及其關係的存儲採用分離機制，無論是查詢節點還是關係（以節點的編號定位矩陣的行，然後在此行上以列掃描就能找到所以子節點）都較方便。

缺點：

  • 矩陣空間浪費嚴重，雖然可以採用矩陣壓縮，但是增加了程式碼維護量。

3.2 鄰接表存儲

鄰接表存儲和鄰接矩陣的分離存儲機制不同，鄰接表的節點類型中除了存儲數據資訊，還會存儲節點之間的關係資訊。

可以根據節點類型中的資訊不同分為如下幾種具體存儲方案：

3.2.1 雙親表示法

結點類型有 2 個存儲域：

  • 數據域。
  • 指向父節點的指針域。

6.png

如下文所示的樹結構，用雙親表示法思路存儲樹結構後的物理結構如下圖所示。

7.png

根節點沒有父結點，雙親指針域中的值為 0。

雙親表示法很容易找到節點的父節點，如果要找到節點的子節點，需要對整個表進行查詢，雙親表示法是一種自引用表示法。

雙親表示法無論使用順序存儲或鏈表存儲都較容易實現。

3.2.2 孩子表示法

用順序表存儲每一個節點，然後以鏈表的形式為每一個節點存儲其所有子結點。如下圖所示，意味著每一個節點都需要維護一個鏈表結構，如果某個節點沒有子結點，其維護的鏈表為空。
8.png

孩子表示法，查找節點的子節點或兄弟節點都很方便，但是查找父節點，就不怎方便了。可以綜合雙親、孩子表示法。

3.2.3 雙親孩子表示法

雙親孩子表示法的存儲結構，無論是查詢父節點還是子節點都變得輕鬆。如下圖所示。

9.png

雙親孩子表示法的具體實現：

  • 設計節點類型:
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
	//節點編號
	int code;
	//節點的值
	char val;
	//節點的父節點
	TreeNode *parent;
	//節點的子節點資訊，以單鏈表的方式存儲,head 指向第一個子節點的地址
	TreeNode *head;
	//兄弟結點
	TreeNode *next;
	//構造函數
	TreeNode(int code,char val) {
		this->code=code;
		this->val=val;
		this->parent=NULL;
		this->head=NULL;
		this->next=NULL;
	}
	//自我顯示
	void show() {
		cout<<"結點：";
		cout<<this->code<<"-"<<this->val<<endl;
		if(this->parent) {
			cout<<"\t父節點：";
			cout<<this->parent->code<<"-"<<this->parent->val<<endl;
		}
		TreeNode *move=this->head;
		while(move) {
			cout<<"\t子節點："<<move->code<<"-"<<move->val<<endl;
			move=move->next;
		}
	}
};

樹類型定義：

class Tree {
	private:
		//一維數組容器，存儲所有結點
		vector<TreeNode*> treeNodes;
		//節點的編號生成器
		int idx=0;
	public:
		//無參構造函數
		Tree() {}
		//有參構造函數，初始化根節點
		Tree(char val) {
			//動態創建節點
			TreeNode* root=new TreeNode(this->idx,val);
			this->idx++;
			this->treeNodes.push_back(root);
		}
		//返回根節點
		TreeNode* getRoot() {
			return this->treeNodes[0];
		}
		//添加新節點
		TreeNode* addTreeNode(char val,TreeNode *parent) {
			//創建節點
			TreeNode* newNode=new TreeNode(this->idx,val);
			if(!newNode)
				//創建失敗
				return NULL;
			if(parent) {
				//設置父節點
				newNode->parent=parent;
				//本身成為父節點的子節點
				if(parent->head==NULL)
					parent->head=newNode;
				else {
					//原來頭節點成為尾節點
					newNode->next=parent->head;
					//新子節結點成為頭結點
					parent->head=newNode;
				}
			}
			//編號自增
			this->idx++;
			//添加到節點容器中
			this->treeNodes.push_back(newNode);
			return newNode;
		}
		//顯示樹上的所有結點，以及結點之間的關係
		void showAll() {
			for(int i=0; i<this->treeNodes.size(); i++) {
				TreeNode *tmp=this->treeNodes[i];
				tmp->show();
			}
		}
};

測試程式碼：

int main(int argc, char** argv) {
	Tree tree('A');
    //返回根節點
	TreeNode * root =tree.getRoot();
    //根節點下添加 B、C  兩個子節點
	TreeNode * rootB= tree.addTreeNode('B',root);
	TreeNode * rootC= tree.addTreeNode('C',root);
    //B下添加D子節點
	TreeNode * rootD= tree.addTreeNode('D',rootB);
    //C下添加E、F子節點
	TreeNode * rootE= tree.addTreeNode('E',rootC);
	TreeNode * rootF= tree.addTreeNode('F',rootC);
	tree.showAll();
	return 0;
}

輸出結果：

16.png

3.2.4 孩子兄弟表示法

指針域中存儲子節點和兄弟節點。節點類型中有 3 個資訊域：

  • 數據域。
  • 指向子節點的地址域。
  • 指向兄弟節點的地址域。

17.png

1.jpg

孩子兄弟表示法的具體實現過程有興趣者可以自行試一試，應該還是較簡單的。

如上幾種實現存儲方式，可以根據實際情況進行合理選擇。

4. 總結

本文先講解了樹的基本概念，然後講解了樹的幾種存儲方案。本文提供了鄰接矩陣和雙親孩子表示法的具體實現。

本文同時也收錄至”編程驛站”公眾號！

Tags:

VirMach 便宜 VPS

QNews

QNews