樹狀結構 (Tree)

Tree 定義

• 每個點之間都有路可以連通。
• 不會形成循環(cycle)。

名詞定義

• node 節點：所有的點都是結點。
• edge 邊

• root 根結點：main。
• parent 雙親節點：父。
• children 小孩節點：子。
• sibling 手足節點：兄弟。

• leaf node 葉節點、external 外部節點：下面不再連通的點。
• internal 內部節點、non terminal node 非終結點：非葉節點的點。

• level 階層：位在哪個階層。
• height 高度、depth 深度：階層的總數。

• degree 分支度：有幾個分支。

二元樹 Binary tree

• 每個節點的分支必為 2。

使用陣列建立二元樹

• 如果點 A 放在 a[i]，若點 B 是點 A 的左分支，則點 B 會放在 a[2*i]，若點 C 是點 A 的右分支，則點 C 會放在 a[2*i+1]。
• 優點：撰寫簡單。
• 缺點：如果右子樹很多，但左子樹很少，會浪費空間。

#include <bits/stdc++.h>
using namespace std;
char btree[10];
void visit(int p){
	if(btree[p]){
		cout << btree[p] << ' ';
		visit(2*p);
		visit(2*p+1);
	}
}
int main(){
	btree[1] = 'A';
	btree[2] = 'B';
	btree[3] = 'C';
	btree[4] = 'D';
	btree[5] = 'E';
	btree[7] = 'F';
	visit(1);
}

使用指標建立二元樹

• 需要兩個指標（一個指向左子樹、一個指向右子樹）。
• 若子樹為空，設定為NULL。（走訪時若遇到NULL則倒退回去）

#include <bits/stdc++.h>
using namespace std;
struct node{ //node p1 'A' 指向 node left 'B' 和 node right 'C'
	char data;
	struct node *left;
	struct node *right;
};
void visit(node *p){
	if(p){
		cout << p->data << ' ';
		visit(p->left);
		visit(p->right);
	}
}
int main(){
	node *root,*p1,*p2,*p3,*p4,*p5,*p7;
	p1 = new node;
	p2 = new node;
	p3 = new node;
	p4 = new node;
	p5 = new node;
	p7 = new node;
	
	p1->data = 'A'; root=p1;
	p2->data = 'B';  
	p3->data = 'C';
	p4->data = 'D';
	p5->data = 'E';	
	p7->data = 'F';
	
	p1->left = p2;
	p2->left = p4;
	p2->right = p5;
	
	p1->right = p3;
	p3->right = p7;
	p3->left = NULL;
	p4->left = NULL;
	p4->right = NULL;
	p5->left = NULL;
	p5->right = NULL;
	p7->left = NULL;
	p7->right = NULL;
	
	visit(root);
}

queue<node*> qu;
void visit(node *now){
	qu.push(now);
	while(!qu.empty()){
		cout << qu.front()->data << ' ';
		if(qu.front()->left != NULL){
			qu.push(qu.front()->left);
		}
		if(qu.front()->right != NULL){
			qu.push(qu.front()->right);
		}
		qu.pop();
	}
}

//input: ABDECF DBEACF
//output: DEBFCA
#include <bits/stdc++.h>
using namespace std;
string preo, ino;
int first;
struct node{
	char data;
	struct node *left;
	struct node *right;
};
void postorder(node *p){
	if(p != NULL){
		postorder(p->left);
		postorder(p->right);
		cout << p->data; 
	}
}
node* buildTree(int left, int right){
	int mid;
	node *bNode = new node;
	bNode->data = preo[first++];
	if(left<right){
		for(int i=left; i<=right; i++){
			if(ino[i] == bNode->data){
				mid = i;
				break;	
			} 
		} 
		if(left<=(mid-1)){
			bNode->left = buildTree(left, mid-1);
		}else{
			bNode->left = NULL;
		}
		if((mid+1)<=right){
			bNode->right = buildTree(mid+1, right);
		}else{
			bNode->right = NULL;
		}
	}else{
		bNode->left = NULL;
		bNode->right = NULL;
	} 
	return bNode;
}
int main(){
	first = 0;
	cin >> preo >> ino;
	node *root = buildTree(0, preo.length()-1);
	postorder(root);
	cout << '\n';
}

#include <bits/stdc++.h>
using namespace std;
int ino[1005], posto[1005];
struct node{
	char data;
	struct node *left;
	struct node *right;
};
int main(){
	int n;
	cin >> n;
	for(int i=0; i<n; i++)
		cin >> ino[i];
	for(int i=0; i<n; i++)
		cin >> posto[i];
}