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();
}
}
走訪二元樹的方式
- 前序走訪
- 中序走訪
- 後序走訪
- 參考:https://ithelp.ithome.com.tw/articles/10205571
//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];
}