樹狀結構 (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];
}
分享文章!
發佈留言

發佈留言必須填寫的電子郵件地址不會公開。