二叉树
轉換自多叉樹 > 樹的二叉鏈表標記法（孩子兄弟標記法） > 基本操作

基於C/C++的演算法實現
/* 樹的二叉鏈表(孩子—兄弟)存儲的基本操作(17個) */
 #define ClearTree DestroyTree /* 二者操作相同 */
 #include"func6-2.c" /* 包括PreOrderTraverse() */
 void InitTree(CSTree *T)
 { /* 操作結果：構造空樹T */
   *T=NULL;
 }
void DestroyTree(CSTree *T)
 { /* 初始條件：樹T存在。操作結果：銷毀樹T */
   if(*T)
   {
     if((*T)->firstchild) /* T有長子 */
       DestroyTree(&(*T)->firstchild); /* 銷毀T的長子為根結點的子樹 */
     if((*T)->nextsibling) /* T有下一個兄弟 */
       DestroyTree(&(*T)->nextsibling); /* 銷毀T的下一個兄弟為根結點的子樹 */
     free(*T); /* 釋放根結點 */
     *T=NULL;
   }
 }
typedef CSTree QElemType; /* 定義佇列元素類型 */
 #include"c3-2.h" /* 定義LinkQueue類型(鏈佇列) */
 #include"bo3-2.c" /* LinkQueue類型的基本操作 */
 void CreateTree(CSTree *T)
 { /* 構造樹T */
   char c[20]; /* 臨時存放孩子結點(設不超過20個)的值 */
   CSTree p,p1;
   LinkQueue q;
   int i,l;
   InitQueue(&q);
   printf("請輸入根結點(字元型,空格為空): ");
   scanf("%c%*c",&c[0]);
   if(c[0]!=Nil) /* 非空樹 */
   {
     *T=(CSTree)malloc(sizeof(CSNode)); /* 建立根結點 */
     (*T)->data=c[0];
     (*T)->nextsibling=NULL;
     EnQueue(&q,*T); /* 入隊根結點的指針 */
     while(!QueueEmpty(q)) /* 隊不空 */
     {
       DeQueue(&q,&p); /* 出隊一個結點的指標 */
       printf("請按長幼順序輸入結點%c的所有孩子: ",p->data);
       gets(c);
       l=strlen(c);
       if(l>0) /* 有孩子 */
       {
         p1=p->firstchild=(CSTree)malloc(sizeof(CSNode)); /* 建立長子結點 */
         p1->data=c[0];
         for(i=1;i<l;i++)
         {
           p1->nextsibling=(CSTree)malloc(sizeof(CSNode)); /* 建立下一個兄弟結點 */
           EnQueue(&q,p1); /* 入隊上一個結點 */
           p1=p1->nextsibling;
           p1->data=c[i];
         }
         p1->nextsibling=NULL;
         EnQueue(&q,p1); /* 入隊最後一個結點 */
       }
       else
         p->firstchild=NULL; /* 長子指針為空 */
     }
   }
   else
     *T=NULL; /* 空樹 */
 }
Status TreeEmpty(CSTree T)
 { /* 初始條件：樹T存在。操作結果：若T為空樹，則返回TURE，否則返回FALSE */
   if(T) /* T不空 */
     return FALSE;
   else
     return TRUE;
 }
int TreeDepth(CSTree T)
 { /* 初始條件：樹T存在。操作結果：返回T的深度 */
   CSTree p;
   int depth,max=0;
   if(!T) /* 樹空 */
     return 0;
   if(!T->firstchild) /* 樹無長子 */
     return 1;
   for(p=T->firstchild;p;p=p->nextsibling)
   { /* 求子樹深度的最大值 */
     depth=TreeDepth(p);
     if(depth>max)
       max=depth;
   }
   return max+1; /* 樹的深度=子樹深度最大值+1 */
 }
TElemType Value(CSTree p)
 { /* 返回p所指結點的值 */
   return p->data;
 }
TElemType Root(CSTree T)
 { /* 初始條件：樹T存在。操作結果：返回T的根 */
   if(T)
     return Value(T);
   else
     return Nil;
 }
CSTree Point(CSTree T,TElemType s)
 { /* 返回二叉鏈表(孩子—兄弟)樹T中指向元素值為s的結點的指標。另加 */
   LinkQueue q;
   QElemType a;
   if(T) /* 非空樹 */
   {
     InitQueue(&q); /* 初始化佇列 */
     EnQueue(&q,T); /* 根結點入隊 */
     while(!QueueEmpty(q)) /* 隊不空 */
     {
       DeQueue(&q,&a); /* 出隊,佇列元素賦給a */
       if(a->data==s)
	 return a;
       if(a->firstchild) /* 有長子 */
         EnQueue(&q,a->firstchild); /* 入隊長子 */
       if(a->nextsibling) /* 有下一個兄弟 */
         EnQueue(&q,a->nextsibling); /* 入隊下一個兄弟 */
     }
   }
   return NULL;
 }
Status Assign(CSTree *T,TElemType cur_e,TElemType value)
 { /* 初始條件：樹T存在，cur_e是樹T中結點的值。操作結果：改cur_e為value */
   CSTree p;
   if(*T) /* 非空樹 */
   {
     p=Point(*T,cur_e); /* p為cur_e的指針 */
     if(p) /* 找到cur_e */
     {
       p->data=value; /* 賦新值 */
       return OK;
     }
   }
   return ERROR; /* 樹空或沒找到 */
 }
TElemType Parent(CSTree T,TElemType cur_e)
 { /* 初始條件：樹T存在，cur_e是T中某個結點 */
   /* 操作結果：若cur_e是T的非根結點，則返回它的雙親，否則函數值為＂空＂*/
   CSTree p,t;
   LinkQueue q;
   InitQueue(&q);
   if(T) /* 樹非空 */
   {
     if(Value(T)==cur_e) /* 根結點值為cur_e */
       return Nil;
     EnQueue(&q,T); /* 根結點入隊 */
     while(!QueueEmpty(q))
     {
       DeQueue(&q,&p);
       if(p->firstchild) /* p有長子 */
       {
         if(p->firstchild->data==cur_e) /* 長子為cur_e */
           return Value(p); /* 返回雙親 */
         t=p; /* 雙親指針賦給t */
         p=p->firstchild; /* p指向長子 */
         EnQueue(&q,p); /* 入隊長子 */
         while(p->nextsibling) /* 有下一個兄弟 */
         {
           p=p->nextsibling; /* p指向下一個兄弟 */
	 if(Value(p)==cur_e) /* 下一個兄弟為cur_e */
	 return Value(t); /* 返回雙親 */
	 EnQueue(&q,p); /* 入隊下一個兄弟 */
	 }
       }
     }
   }
   return Nil; /* 樹空或沒找到cur_e */
 }
TElemType LeftChild(CSTree T,TElemType cur_e)
 { /* 初始條件：樹T存在，cur_e是T中某個結點 */
   /* 操作結果：若cur_e是T的非葉子結點，則返回它的最左孩子，否則返回＂空＂*/
   CSTree f;
   f=Point(T,cur_e); /* f指向結點cur_e */
   if(f&&f->firstchild) /* 找到結點cur_e且結點cur_e有長子 */
     return f->firstchild->data;
   else
     return Nil;
 }
TElemType RightSibling(CSTree T,TElemType cur_e)
 { /* 初始條件：樹T存在，cur_e是T中某個結點 */
   /* 操作結果：若cur_e有右兄弟，則返回它的右兄弟，否則返回＂空＂*/
   CSTree f;
   f=Point(T,cur_e); /* f指向結點cur_e */
   if(f&&f->nextsibling) /* 找到結點cur_e且結點cur_e有右兄弟 */
     return f->nextsibling->data;
   else
     return Nil; /* 樹空 */
 }
Status InsertChild(CSTree *T,CSTree p,int i,CSTree c)
 { /* 初始條件：樹T存在，p指向T中某個結點，1≦i≦p所指結點的度+1，非空樹c與T不相交 */
   /* 操作結果：插入c為T中p結點的第i棵子樹 */
   /* 因為p所指結點的位址不會改變，故p不需是參考類型 */
   int j;
   if(*T) /* T不空 */
   {
     if(i==1) /* 插入c為p的長子 */
     {
       c->nextsibling=p->firstchild; /* p的原長子現是c的下一個兄弟(c本無兄弟) */
       p->firstchild=c;
     }
     else /* 找插入點 */
     {
       p=p->firstchild; /* 指向p的長子 */
       j=2;
       while(p&&i>j)
       {
         p=p->nextsibling;
         j++;
       }
       if(j==i) /* 找到插入位置 */
       {
         c->nextsibling=p->nextsibling;
         p->nextsibling=c;
       }
       else /* p原有孩子數小於i-1 */
         return ERROR;
     }
     return OK;
   }
   else /* T空 */
     return ERROR;
 }
Status DeleteChild(CSTree *T,CSTree p,int i)
 { /* 初始條件：樹T存在，p指向T中某個結點，1≦i≦p所指結點的度 */
   /* 操作結果：刪除T中p所指結點的第i棵子樹 */
   /* 因為p所指結點的位址不會改變，故p不需是參考類型 */
   CSTree b;
   int j;
   if(*T) /* T不空 */
   {
     if(i==1) /* 刪除長子 */
     {
       b=p->firstchild;
       p->firstchild=b->nextsibling; /* p的原次子現是長子 */
       b->nextsibling=NULL;
       DestroyTree(&b);
     }
     else /* 刪除非長子 */
     {
       p=p->firstchild; /* p指向長子 */
       j=2;
       while(p&&i>j)
       {
         p=p->nextsibling;
         j++;
       }
       if(j==i) /* 找到第i棵子樹 */
       {
         b=p->nextsibling;
         p->nextsibling=b->nextsibling;
         b->nextsibling=NULL;
         DestroyTree(&b);
       }
       else /* p原有孩子數小於i */
         return ERROR;
     }
     return OK;
   }
   else
     return ERROR;
 }
void PostOrderTraverse(CSTree T,void(*Visit)(TElemType))
 { /* 後根遍歷孩子—兄弟二叉鏈表結構的樹T */
   CSTree p;
   if(T)
   {
     if(T->firstchild) /* 有長子 */
     {
       PostOrderTraverse(T->firstchild,Visit); /* 後根遍歷長子子樹 */
       p=T->firstchild->nextsibling; /* p指向長子的下一個兄弟 */
       while(p)
       {
         PostOrderTraverse(p,Visit); /* 後根遍歷下一個兄弟子樹 */
         p=p->nextsibling; /* p指向再下一個兄弟 */
       }
     }
     Visit(Value(T)); /* 最後訪問根結點 */
   }
 }
void LevelOrderTraverse(CSTree T,void(*Visit)(TElemType))
 { /* 層序遍歷孩子—兄弟二叉鏈表結構的樹T */
   CSTree p;
   LinkQueue q;
   InitQueue(&q);
   if(T)
   {
     Visit(Value(T)); /* 先訪問根結點 */
     EnQueue(&q,T); /* 入隊根結點的指針 */
     while(!QueueEmpty(q)) /* 隊不空 */
     {
       DeQueue(&q,&p); /* 出隊一個結點的指標 */
       if(p->firstchild) /* 有長子 */
       {
         p=p->firstchild;
         Visit(Value(p)); /* 訪問長子結點 */
         EnQueue(&q,p); /* 入隊長子結點的指針 */
         while(p->nextsibling) /* 有下一個兄弟 */
         {
           p=p->nextsibling;
           Visit(Value(p)); /* 訪問下一個兄弟 */
           EnQueue(&q,p); /* 入隊兄弟結點的指針 */
         }
       }
     }
   }
 }