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

2026-05-09 生活百科

可以根據節點類型中的信息不同分為如下幾種具體存儲方案：
3.2.1 雙親表示法結點類型有 2 個存儲域：

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

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

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

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

文章插圖
根節點沒有父結點，雙親指針域中的值為 0 。
雙親表示法很容易找到節點的父節點，如果要找到節點的子節點，需要對整個表進行查詢，雙親表示法是一種自引用表示法。
雙親表示法無論使用順序存儲或鏈表存儲都較容易實現。
3.2.2 孩子表示法用順序表存儲每一個節點，然后以鏈表的形式為每一個節點存儲其所有子結點。如下圖所示，意味著每一個節點都需要維護一個鏈表結構，如果某個節點沒有子結點，其維護的鏈表為空。

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

文章插圖
孩子表示法，查找節點的子節點或兄弟節點都很方便，但是查找父節點，就不怎方便了 ?？梢跃C合雙親、孩子表示法。
3.2.3 雙親孩子表示法雙親孩子表示法的存儲結構，無論是查詢父節點還是子節點都變得輕松。如下圖所示。

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

文章插圖
雙親孩子表示法的具體實現：

設計節點類型:

#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;}

輸出結果：

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

文章插圖
3.2.4 孩子兄弟表示法指針域中存儲子節點和兄弟節點。節點類型中有 3 個信息域：

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

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

文章插圖

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

文章插圖
孩子兄弟表示法的具體實現過程有興趣者可以自行試一試，應該還是較簡單的。
如上幾種實現存儲方式，可以根據實際情況進行合理選擇。

推薦閱讀

上一篇：SpringBoot內置工具類，告別瞎寫工具類了

下一篇：JDK中自帶的JVM分析工具