[Day13]程序菜鸟自学C++资料结构演算法 – 二元树的储存与实作

前言：上一篇介绍过了树状结构和二元树，今天要来介绍二元树存取资料的方法，其中有两种方法最常使用，这次都会带大家好好了解。

阵列表示法：

利用阵列结构储存资料的二元树，节点编号具有循序性，一此方法可得到节点编号的规则，例如：左节点编号是父节点编号乘以2；右节点编号是父节点编号乘以2+1。

建立规则：
•将阵列的第1个元素插入二元树成为根节点。

•将阵列元素值与二元树的节点值做比较，如果元素值大於节点值，将元素值插入成为节点的右子节点，如果右子节点不是空的，重覆比较节点值，直到找到插入位置後，将元素值插入二元树。

•如果元素值小於节点值，将元素值插入成为节点的左子节点，如果左子节点不是空的，继续重覆比较，以便将元素值插入二元树。

优点：适合用来存取完满二元树。因为阵列表示法的节点具有循序性，完满二元树的储存能够有效运用记忆体空间，避免造成不必要的浪费。

缺点：不适合用来存取歪斜树。同样因为节点的循序性，就算节点内没有资料，阵列也不会删除储存子节点资料的记忆体，而是形成一个空集合，造成记忆体的浪费。

实作程序码：

现在没有执行结果是因为程序码还没有走访的顺序，所以执行了也没有东西，这部分的内容明天就会讨论到了喔！

链结串列表示法：

利用链结串列储存资料的二元树，每个节点中会多出两个指向子节点的指标(一左一右)

优点：适合用来存取歪斜树，链结串列表示法的二元树只会将指标指向的资料储存，所以并不会像阵列表示法一样浪费过多的空间。

缺点：不适合用来存取完满二元树，需要多使用到记忆体空间储存各节点的左右指标，会比起阵列表示法浪费空间。

实作程序码：

本日小结：今天介绍了二元树的两种储存方式，明天就要照着这个程序码实作二元树的走访，这也是相当重要的环节，不同的走访方式就会有不同的结果，怎麽样的走访方式适合在甚麽地方使用将会是明天的重点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';
}