Tree

樹狀結構

general tree(一般樹)
定義:一群節點所形成之集合,至少一個節點(樹根),每個集合又是一棵樹
有序樹:兄弟之間的次序是固定的
無序樹:兄弟之間的次之可變動的
degree(分支度):指節點的子數個數
leaf(樹葉),terminal node(末端節點):指分支度為0的節點
ancestors(祖先):從樹根節點到該節點的路徑中所有節點
節點數=分支數+1,因為除了樹根外,各節點都被一個分支指到

binary tree(二元樹):
定義:一群節點所形成之集合,節點數可為0(空集合),其餘節點為樹根的左子樹與右子樹且皆為2元樹
設二元樹深度為k,階層為i,則有三特性:
1:節點數最多為2^k-1
2:第i層的節點數最多為2^(i-1)
3:設n0=分支度為0的節點,n2=分支度為2的節點,則n0=n2+1,也就是樹葉數=分支度為2的節點的總數+1
證明:設節點個數:n2+n1+n0,分支個數:2*n2+1*n1+0*n0=2*n2+n1
因節點數=分支數+1,所以n2+n1+n0=(2*n2+n1)+1,移項得到n0=n2+1

二元樹的種類:
full binary tree(全滿二元樹):節點個數最多的二元樹,節點數為2^k-1
complete binary tree(完整二元樹):節點最少為2^(k-1),最多為2^k-1
strictly binary tree
skewed binary tree(傾斜樹):節點個數最少的二元樹,節點數為k

樹林變二元樹
1,各樹的樹根皆為兄弟
2,是兄弟一律放在右子樹,是兒子一律放在左子樹

………………………………………………………………..

若用陣列表示二元樹
設i為父節點,則左兒子節點為2i,右兒子節點為2i+1
缺點:插入和刪除時需大量搬動資料,若二元樹有資料的節點不多則浪費空間

若用鏈結表示二元樹
typedef struct bin_tree{ //二元樹節點含指標的結構:
　struct bin_tree *left; //左子樹的指標
　int data; /資料/
　struct bin_tree *right; //右子樹的指標
}BIN_TREE;

計算端末節點數
int count(struct bin_tree *root){ //會將各節點走訪一次,所以是big O(n)
　 if(root==null)return(0);
　else if(root->left==null&&root->right==null)return(1)
　else return(count(root->left)+count(root->right));
}
對調左子樹和右子樹
void swap(treenode root){
　treenode *temp;
　if(root==null){return(null);}
　else{
　　temp=root->right;
　　root->right=swap(root->left);
　　root->left=swap(temp);
　}
}

………………………….

traversal
主要有三種
preorder(DLR)前序走訪
void preorder(treenode root){
　if(root!=null){
　　printf(“%d”,root->data); //列data,
　　preorder(root->left); //在往左子樹
　　preorder(root->right); //在往右子樹
　}
}
inorder(LDR)中序走訪
void inorder(treenode root){
　if(root!=null){
　　preorder(root->left); //在往左子樹
　　printf(“%d”,root->data); //列data,
　　preorder(root->right); //在往右子樹
　}
}
postorder(LRD)後序走訪
void postorder(treenode root){
　if(root!=null){
　　preorder(root->left); //在往左子樹
　　preorder(root->right); //在往右子樹
　　printf(“%d”,root->data); //列data,
　}
}
呼叫次數皆為2n+1次,時間複雜度為O(n)

前序走訪的樹根一定先印出,後序走訪的樹根一定最後被印出,而中序走訪的樹根則在左子樹之後右子樹之前
因此只要藉由前序走訪+中序走訪或後序走訪+中序走訪,就可將印出的資料依順序重組回二元樹
但後序走訪+前序走訪則不一定可以組回二元樹
ex:給前序abc及後序cba，則可產生右傾斜二元樹和左傾斜二元樹

…………………………………………………………………………………………….

threaded binary trees(引線二元樹)
說明:
一種特殊的二元樹,利用原二元樹中的空指標,改變成引線,以方便進行追蹤
若左欄為空則變引線,並指向上一個被印出的節點,若右欄為空變為引線,則指向下一個被印出的節點

特性:
一個具n個節點的引線二元樹,會有2n的鏈結欄位,n-1個欄位是原先的指標,n+1個欄位是引線
空的引線二元樹的開頭節點右欄不當引線,並指自己,但左欄則當引線,並指自己
而非空的引線二元樹的開頭節點左欄不當引線,並指樹根節點

引線分為:
in-thread(中引線),pre-thread(前引線),post-thread(後引線)

資料結構為：
typedef struct threaded_tree{
　short int lthread;
　treenode left;
　char data;
　treenode right;
　short int rthread;
}treenode;

常見運作:將資料插在節點後,將資料插在節點前,找下一個節點
將節點插在某節點後
void insert _right(struct treenode *x,struct treenode *new){
　new->lthread=1; //因為是在x的下一個,因為lthread一定是引線
　new->left=x; //因為是引線所以指向x
　new->right=x->right;
　new->rthread=x->rthread;
　x->right=new;
　x->rthread=0;
　/*若不是插入left則需要做以下,找到新節點適合的位置*/
　if(new->rthread==0){
　　temp=new->right;
　　while(temp->lthread==0){temp=temp->left;}
　　temp->left=new;
　}
/*結束*/
}
找x的下一個節點
treenode next(struct treenode *x){
　treenode *temp;
　temp=x->right;
　if(x->rthread==0){ //如果有非空右子樹
　　while(temp->lthread==0){temp=temp->left;} //左欄位是左子樹就進入
　}
　return(temp);
}

……………………………………………………………………….

binary expression trees(二元運算樹)
具有階層關係(運算子之間的優先順序)及二元關係(運算子需對應兩個運算元)
端末節點表示運算元,內部節點表示運算子,運算子越優先則會在越底層
運算子優先順序通常為:算術運算子(正負,*/,+-) > 關係運算子 > 邏輯運算子(~,and)
進行pre-order traversal可表示成prefix expression
進行post-order traversal可表示成postfix expression
進行in-order traversal,在另外加括號可表示成infix expression

利用後序走訪順序對二元運算樹計算
int evaluate(struct treenode *root){
　int x,,result;
　if(root->left==null&&root->right==null){return (root->data);} //如果是運算元就回傳
　else{ //遞迴關係是先處理左子樹在處理右子樹，最後進行計算
　　x=evaluate(root->left);
　　y=evaluate(root->right);
　　switch(root->operator){
　　　case ‘+’:result=x+y;break;
　　　case ‘*’:result=x*y;break;
　　　case ‘/’:result=x/y;break;
　　　case ‘-‘:result=x-y;break;
　　}
　　return(result);
　}
}
利用stack計算postfix
….

……………………………………………………………..

樹的應用
集合的樹
樹的節點用來表示集合的所有元素,可用一維陣列表示n個元素的集合情況,
ex:int parent[1-n];
而各節點都指向父親節點，可用一維陣列內的value欄儲存父節點key值
父親節點的value欄則儲存這集合的元素個數(可表示為負數方便區別)
ex:set 1={1,2,4},則parent[1]=-3,parent[2]=1,parent[4]=1,
集合的運作有：聯集運作,找元素所屬集合

聯集運作：將兩棵樹合併為一棵樹，可將一個樹的樹根節點指向另一棵樹
如果全部有n個元素,最差情況會形成一個高度為n的樹(可在聯進運作時使用加權法則避免)
weighting rule(加權法則):將集合的元素個數當成加權考量,將較少節點的樹指向將多節點的樹,則高度不變，除非節點相同高度才會加1
void union(int x,int y){ //big O(1)
if(parent[x]
parent[y]=x; //y集合指向x集合,因為x的元素多
}else{
parent[x]=y; //x集合指向y集合,因為y的元素多,或是等於x
}
}
找元素所屬集合：相當於由節點往上找到樹根節點，複雜度＝集合對應的樹高
若在聯集運作時用加權法則,複雜度為big O(log2(n))
find(int z){
int father;
father=parent[z];
while(parent[father]>0){ //如果是負數則代表集合，不然繼續往上找
father=parent[father];
}
return(father);
}

決策樹
遊戲樹