iT邦幫忙

2021 iThome 鐵人賽

DAY 13
0
Software Development

程式菜鳥自學C++資料結構演算法系列 第 13

[Day13]程式菜鳥自學C++資料結構演算法 – 二元樹的儲存與實作

前言:上一篇介紹過了樹狀結構和二元樹,今天要來介紹二元樹存取資料的方法,其中有兩種方法最常使用,這次都會帶大家好好了解。

陣列表示法:

利用陣列結構儲存資料的二元樹,節點編號具有循序性,一此方法可得到節點編號的規則,例如:左節點編號是父節點編號乘以2;右節點編號是父節點編號乘以2+1。

建立規則:
•將陣列的第1個元素插入二元樹成為根節點。

•將陣列元素值與二元樹的節點值做比較,如果元素值大於節點值,將元素值插入成為節點的右子節點,如果右子節點不是空的,重覆比較節點值,直到找到插入位置後,將元素值插入二元樹。

•如果元素值小於節點值,將元素值插入成為節點的左子節點,如果左子節點不是空的,繼續重覆比較,以便將元素值插入二元樹。

優點:適合用來存取完滿二元樹。因為陣列表示法的節點具有循序性,完滿二元樹的儲存能夠有效運用記憶體空間,避免造成不必要的浪費。
https://ithelp.ithome.com.tw/upload/images/20210927/201401870uqf0uWGMb.png
https://ithelp.ithome.com.tw/upload/images/20210927/20140187k3v7Zoxx3Q.png

缺點:不適合用來存取歪斜樹。同樣因為節點的循序性,就算節點內沒有資料,陣列也不會刪除儲存子節點資料的記憶體,而是形成一個空集合,造成記憶體的浪費。
https://ithelp.ithome.com.tw/upload/images/20210927/20140187ZT3AlzpQSM.png
https://ithelp.ithome.com.tw/upload/images/20210927/201401872EqViCXuns.png

實作程式碼:
https://ithelp.ithome.com.tw/upload/images/20210927/20140187Kh1oyZoeRB.png
現在沒有執行結果是因為程式碼還沒有走訪的順序,所以執行了也沒有東西,這部分的內容明天就會討論到了喔!

鏈結串列表示法:

利用鏈結串列儲存資料的二元樹,每個節點中會多出兩個指向子節點的指標(一左一右)

優點:適合用來存取歪斜樹,鏈結串列表示法的二元樹只會將指標指向的資料儲存,所以並不會像陣列表示法一樣浪費過多的空間。
https://ithelp.ithome.com.tw/upload/images/20210927/20140187vUbIHlYfSx.png

缺點:不適合用來存取完滿二元樹,需要多使用到記憶體空間儲存各節點的左右指標,會比起陣列表示法浪費空間。
https://ithelp.ithome.com.tw/upload/images/20210927/20140187wUgHQAt3g9.png

實作程式碼:
https://ithelp.ithome.com.tw/upload/images/20210927/20140187ubrOHa1cmK.png

本日小結:今天介紹了二元樹的兩種儲存方式,明天就要照著這個程式碼實作二元樹的走訪,這也是相當重要的環節,不同的走訪方式就會有不同的結果,怎麼樣的走訪方式適合在甚麼地方使用將會是明天的重點o(-д´- 。)

陣列表示法

#include <iostream>
using namespace std;
struct BiNode {
	char data;
	struct BiNode* Lchild;
	struct BiNode* Rchild;
};

int main() {
	BiNode* root, * p1, * p2, * p3, * p4, * p5, * p6, * p7;
	p1 = new BiNode;
	p1->data = 'A';
	root = p1;
	p2 = new BiNode;
	p2->data = 'B';
	p3 = new BiNode;
	p3->data = 'C';
	p4 = new BiNode;
	p4->data = 'D';
	p5 = new BiNode;
	p5->data = 'E';
	p6 = new BiNode;
	p6->data = 'F';
	p7 = new BiNode;
	p7->data = 'G';
	p1->Lchild = p2;
	p1->Rchild = p3;
	p2->Lchild = p4;
	p2->Rchild = p5;
	p3->Lchild = p6;
	p3->Rchild = p7;
	p4->Lchild = NULL;
	p4->Rchild = NULL;
	p5->Lchild = NULL;
	p5->Rchild = NULL;
	p6->Lchild = NULL;
	p6->Rchild = NULL;
	p7->Lchild = NULL;
	p7->Rchild = NULL;
}

鏈結串列表示法

using T = char;

struct BiNode {
	T data;
	BiNode* Lchild{ 0 };
    BiNode* Rchild{ 0 };
};

int main() {
BiNode* T=new BiNode(); T->data= 'A';
T->Lchild=new BiNode(); T->Lchild->data= 'B';
T->Rchild=new BiNode(); T->Rchild->data= 'C';
BiNode* P=T->Lchild;
P->Lchild=new BiNode(); P->Lchild->data= 'D';
P->Rchild=new BiNode(); P->Rchild->data= 'E';
BiNode* S=T->Rchild;
S->Lchild=new BiNode(); S->Lchild->data= 'F';
S->Rchild=new BiNode(); S->Rchild->data= 'G';
}

上一篇
[Day12]程式菜鳥自學C++資料結構演算法 – 樹Tree
下一篇
[Day14]程式菜鳥自學C++資料結構演算法 – 二元樹的走訪Binary Tree Traversal
系列文
程式菜鳥自學C++資料結構演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言