樹的基本操作（連載中）
摘要：
樹是一種一對多的非線性資料結構，可以利用順序儲存結構來儲存資料，也可以利用鏈式結構來儲存資料。
考慮到空間問題以及實用性，這裡利用鏈式結構來儲存資料。
這裡由於筆者的題目輸入格式是這樣的：
每個輸入檔案包含一個測試用例。
對於每種情況，第一行給出正整數N（≤10），它...
樹是一種一對多的非線性資料結構，可以利用順序儲存結構來儲存資料，也可以利用鏈式結構來儲存資料。
考慮到空間問題以及實用性，這裡利用鏈式結構來儲存資料。
這裡由於筆者的題目輸入格式是這樣的：
每個輸入檔案包含一個測試用例。
對於每種情況，第一行給出正整數N（≤10），它是樹中節點的總數 - 因此節點從0到N-1編號。
然後是N行，每行對應一個節點，並給出節點左右子節點的索引。
如果孩子不存在，將在該位置放置“ - ”。
任何一對孩子都被一個空間隔開。
輸入樣例：
8 1 - - - 0 - 2 7 - - - - 5 - 4 6
所以後面的基本操作就以這種輸入格式為基礎啦。
1.樹節點的定義
typedef char datatype;
typedef struct node{//定義節點
datatype data;
struct node *lchild, *rchild;
}node;
2.樹的初始化
//建立樹
//傳入資料：樹的節點個數，頭指標
//傳出資料：根節點下標，指向根節點的頭指標
void create_tree(int num, int *mark, node *&head)
{
int i;
datatype data, left, right;
node *h[num];//指標陣列，指向樹節點
int root[num] = {0};//root[]陣列初始化為0
for(i=0; i<num; i++){
h[i] = new node;//給樹節點申請空間
h[i]->lchild = h[i]->rchild = NULL;
}
for(i=0; i<num; i++){
cin>>data>>left>>right;
int l, r;
if(left != '-'){
l = left-48;//轉化為int型別
h[i]->lchild = h[l];
root[l] = 1;//表示如果h[l]有雙親，root[l] = 1
}
if(right != '-'){
r = right-48;
h[i]->rchild = h[r];
root[r] = 1;
}
}
//掃描root[]陣列，root[i] == 0 時，i為根節點下標
for(i=0; i<num; i++){
if(root[i] == 0){
*mark = i;
break;
}
}
head = h[*mark];//頭指標指向根節點
}
3. 判斷是否為葉節點（是返回1，否返回0）
bool is_leave(node *n)//判斷是否為葉節點：是返回1，否返回0
{
if(n->lchild == NULL && n->rchild == NULL){
return true;
}else{
return false;
}
}
4.前序遍歷（根左右）
這裡是遞迴版本
void preorder(node *head)//前序遍歷樹
{
node *i;
i = head;
if(i != NULL){
cout<< i->data<<endl;
}
preorde(i->lchild);
preorde(i->rchild);
}
}