二叉树
存儲 > 順序存儲表示 > 基本操作

基於C/C++的實現演算法
/* [[二元樹]]的順序存儲的基本操作(23個)*/
#define ClearBiTree InitBiTree /* 在順序存儲結構中，兩函數完全一樣 */
#define DestroyBiTree InitBiTree /* 在順序存儲結構中，兩函數完全一樣 */
void InitBiTree(SqBiTree T) －－－（SqBiTree & T）
{ /* 構造[[空二元樹]]T。因為T是陣列名稱，故不需要& */
  int i;
  for(i=0;i<MAX_TREE_SIZE;i++)
    T[i]=Nil; /* 初值為空(Nil在主程中定義) */
}
void CreateBiTree(SqBiTree T)
{ /* 按層序次序輸入二叉樹中結點的值(字元型或整型), 構造順序存儲的二叉樹T */
  int i=0;
#if CHAR /* 結點類型為字元 */
  int l;
  char s[MAX_TREE_SIZE];
  InitBiTree(T); /* 構造[空二元樹]T */
  printf("請按層序輸入結點的值(字元)，空格表示空結點，節點數≦%d:\n",MAX_TREE_SIZE);
  gets(s); /* 輸入字串 */
  l=strlen(s); /* 求字串的長度 */
  for(;i<l;i++) /* 將字串賦值給T */
    T[i]=s[i];
#else  /* 節點類型為整型 */
  InitBiTree(T); /* 構造[空二元樹]T */
  printf("請按層序輸入節點的值(整型)，0表示空節點，輸999結束。節點數≦%d:\n",MAX_TREE_SIZE);
  while(1)
  {
    scanf("%d",&T[i]);
    if(T[i]==999)
    {
       T[i]=Nil;
      break;
    }
    i++;
  }
#endif
  for(i=1;i<MAX_TREE_SIZE;i++)
    if(T[(i+1)/2-1]==Nil&&T[i]!=Nil) /* 此非根節點(不空)無雙親 */
    {
      printf("出現無雙親的非根節點"form"\n",T[i]);
      exit(ERROR);
    }
}
int BiTreeDepth(SqBiTree T)
{ /* 初始條件：[二元樹]T存在。操作結果：返回T的深度 */
  int i,j=-1;
  for(i=MAX_TREE_SIZE-1;i>=0;i--) /* 找到最後一個節點 */
    if(T[i]!=Nil)
      break;
  i++; /* 為了便於計算 */
  do
    j++;
  while(i>=pow(2,j));   /*pow是原型為double pow( double x, double y ),計算x的y次方,h = log<sub>2</sub>k + 1來計算[二元樹]的深度*/
  return j;
}
Status Root(SqBiTree T,TElemType *e)
{ /* 初始條件：[二元樹]T存在。操作結果：當T不空，用e返回T的根，返回OK；否則返回ERROR，e無定義 */
  if(BiTreeEmpty(T)) /* T空 */
    return ERROR;
  else
  {
    *e=T[0];
    return OK;
  }
}
TElemType Value(SqBiTree T,position e)
{ /* 初始條件：[二元樹]T存在，e是T中某個結點(的位置) */
  /* 操作結果：返回處於位置e(層,本層序號)的結點的值 */
  return T[(int)pow(2,e.level-1)+e.order-2];
}
Status Assign(SqBiTree T,position e,TElemType value)
{ /* 初始條件：二叉樹T存在，e是T中某個結點(的位置) */
  /* 操作結果：給處於位置e(層,本層序號)的結點賦新值value */
  int i=(int)pow(2,e.level-1)+e.order-2; /* 將層、本層序號轉為矩陣的序號 */
  if(value!=Nil&&T[(i+1)/2-1]==Nil) /* 給葉子賦非空值但雙親為空 */
     return ERROR;
  else if(value==Nil&&(T[i*2+1]!=Nil||T[i*2+2]!=Nil)) /*  給雙親賦空值但有葉子(不空) */
    return ERROR;
  T[i]=value;
  return OK;
}
TElemType Parent(SqBiTree T,TElemType e)
{ /* 初始條件：二叉樹T存在，e是T中某個結點 */
  /* 操作結果：若e是T的非根結點，則返回它的雙親，否則返回＂空＂ */
  int i;
  if(T[0]==Nil) /* 空樹 */
    return Nil;
  for(i=1;i<=MAX_TREE_SIZE-1;i++)
    if(T[i]==e) /* 找到e */
      return T[(i+1)/2-1];
  return Nil; /* 沒找到e */
}
TElemType LeftChild(SqBiTree T,TElemType e)
{ /* 初始條件：二叉樹T存在，e是T中某個結點。操作結果：返回e的左孩子。若e無左孩子,則返回"空" */
  int i;
  if(T[0]==Nil) /* 空樹 */
    return Nil;
  for(i=0;i<=MAX_TREE_SIZE-1;i++)
    if(T[i]==e) /* 找到e */
      return T[i*2+1];
  return Nil; /* 沒找到e */
}
TElemType RightChild(SqBiTree T,TElemType e)
{ /* 初始條件：二叉樹T存在，e是T中某個結點。操作結果：返回e的右孩子。若e無右孩子,則返回"空" */
  int i;
  if(T[0]==Nil) /* 空樹 */
    return Nil;
  for(i=0;i<=MAX_TREE_SIZE-1;i++)
    if(T[i]==e) /* 找到e */
      return T[i*2+2];
  return Nil; /* 沒找到e */
}
TElemType LeftSibling(SqBiTree T,TElemType e)
{ /* 初始條件：二叉樹T存在，e是T中某個結點 */
  /* 操作結果：返回e的左兄弟。若e是T的左孩子或無左兄弟，則返回＂空＂ */
  int i;
  if(T[0]==Nil) /* 空樹 */
    return Nil;
  for(i=1;i<=MAX_TREE_SIZE-1;i++)
    if(T[i]==e&&i%2==0) /* 找到e且其序號為偶數(是右孩子) */
      return T[i-1];
  return Nil; /* 沒找到e */
}
TElemType RightSibling(SqBiTree T,TElemType e)
{ /* 初始條件：二叉樹T存在，e是T中某個結點 */
  /* 操作結果：返回e的右兄弟。若e是T的右孩子或無右兄弟，則返回＂空＂ */
  int i;
  if(T[0]==Nil) /* 空樹 */
    return Nil;
  for(i=1;i<=MAX_TREE_SIZE-1;i++)
    if(T[i]==e&&i%2) /* 找到e且其序號為奇數(是左孩子) */
      return T[i+1];
  return Nil; /* 沒找到e */
}
void Move(SqBiTree q,int j,SqBiTree T,int i) /* InsertChild()用到。加 */
{ /* 把從q的j結點開始的子樹移為從T的i結點開始的子樹 */
  if(q[2*j+1]!=Nil) /* q的左子樹不空 */
    Move(q,(2*j+1),T,(2*i+1)); /* 把q的j結點的左子樹移為T的i結點的左子樹 */
  if(q[2*j+2]!=Nil) /* q的右子樹不空 */
    Move(q,(2*j+2),T,(2*i+2)); /* 把q的j結點的右子樹移為T的i結點的右子樹 */
  T[i]=q[j]; /* 把q的j結點移為T的i結點 */
  q[j]=Nil; /* 把q的j結點置空 */
}
void InsertChild(SqBiTree T,TElemType p,int LR,SqBiTree c)
{ /* 初始條件：二叉樹T存在，p是T中某個結點的值，LR為0或1，非空二叉樹c與T不相交且右子樹為空 */
  /* 操作結果: 根據LR為0或1,插入c為T中p結點的左或右子樹。p結點的原有左或右子樹則成為c的右子樹 */
  int j,k,i=0;
  for(j=0;j<(int)pow(2,BiTreeDepth(T))-1;j++) /* 查找p的序號 */
    if(T[j]==p) /* j為p的序號 */
      break;
  k=2*j+1+LR; /* k為p的左或右孩子的序號 */
  if(T[k]!=Nil) /* p原來的左或右孩子不空 */
    Move(T,k,T,2*k+2); /* 把從T的k結點開始的子樹移為從k結點的右子樹開始的子樹 */
  Move(c,i,T,k); /* 把從c的i結點開始的子樹移為從T的k結點開始的子樹 */
}
typedef int QElemType; /* 設佇列元素類型為整型(序號) */
#include "c3-2.h" /* 鏈佇列 */
#include "bo3-2.c" /* 鏈佇列的基本操作 */
Status DeleteChild(SqBiTree T,position p,int LR)
{ /* 初始條件：二叉樹T存在，p指向T中某個結點，LR為1或0 */
  /* 操作結果：根據LR為1或0，刪除T中p所指結點的左或右子樹 */
  int i;
  Status k=OK; /* 佇列不空的標誌 */
  LinkQueue q;
  InitQueue(&q); /* 初始化佇列，用於存放待刪除的結點 */
  i=(int)pow(2,p.level-1)+p.order-2; /* 將層、本層序號轉為矩陣的序號 */
  if(T[i]==Nil) /* 此結點空 */
    return ERROR;
  i=i*2+1+LR; /* 待刪除子樹的根結點在矩陣中的序號 */
  while(k)
  {
    if(T[2*i+1]!=Nil) /* 左結點不空 */
      EnQueue(&q,2*i+1); /* 入隊左結點的序號 */
    if(T[2*i+2]!=Nil) /* 右結點不空 */
      EnQueue(&q,2*i+2); /* 入隊右結點的序號 */
    T[i]=Nil; /* 刪除此結點 */
    k=DeQueue(&q,&i); /* 佇列不空 */
  }
  return OK;
}
void(*VisitFunc)(TElemType); /* 函數變數 */
void PreTraverse(SqBiTree T,int e)
{ /* PreOrderTraverse()調用 */
  VisitFunc(T[e]);
  if(T[2*e+1]!=Nil) /* 左子樹不空 */
    PreTraverse(T,2*e+1);
  if(T[2*e+2]!=Nil) /* 右子樹不空 */
    PreTraverse(T,2*e+2);
}
void PreOrderTraverse(SqBiTree T,void(*Visit)(TElemType))
{ /* 初始條件：二叉樹存在，Visit是對結點操作的應用函數 */
  /* 操作結果：先序遍歷T，對每個結點調用函數Visit一次且僅一次 */
  VisitFunc=Visit;
  if(!BiTreeEmpty(T)) /* 樹不空 */
    PreTraverse(T,0);
  printf("\n");
}
void InTraverse(SqBiTree T,int e)
{ /* InOrderTraverse()調用 */
  if(T[2*e+1]!=Nil) /* 左子樹不空 */
    InTraverse(T,2*e+1);
  VisitFunc(T[e]);
  if(T[2*e+2]!=Nil) /* 右子樹不空 */
    InTraverse(T,2*e+2);
}
void InOrderTraverse(SqBiTree T,void(*Visit)(TElemType))
{ /* 初始條件：二叉樹存在，Visit是對結點操作的應用函數 */
  /* 操作結果：中序遍歷T，對每個結點調用函數Visit一次且僅一次 */
  VisitFunc=Visit;
  if(!BiTreeEmpty(T)) /* 樹不空 */
    InTraverse(T,0);
  printf("\n");
}
void PostTraverse(SqBiTree T,int e)
{ /* PostOrderTraverse()調用 */
  if(T[2*e+1]!=Nil) /* 左子樹不空 */
    PostTraverse(T,2*e+1);
  if(T[2*e+2]!=Nil) /* 右子樹不空 */
    PostTraverse(T,2*e+2);
  VisitFunc(T[e]);
}
void PostOrderTraverse(SqBiTree T,void(*Visit)(TElemType))
{ /* 初始條件：二叉樹T存在，Visit是對結點操作的應用函數 */
  /* 操作結果：後序遍歷T，對每個結點調用函數Visit一次且僅一次 */
  VisitFunc=Visit;
  if(!BiTreeEmpty(T)) /* 樹不空 */
    PostTraverse(T,0);
  printf("\n");
}
void LevelOrderTraverse(SqBiTree T,void(*Visit)(TElemType))
{ /* 層序遍歷二叉樹 */
  int i=MAX_TREE_SIZE-1,j;
  while(T[i]==Nil)
    i--; /* 找到最後一個非空結點的序號 */
  for(j=0;j<=i;j++) /* 從根結點起，按層序遍歷二叉樹 */
    if(T[j]!=Nil)
      Visit(T[j]); /* 只遍歷非空的結點 */
  printf("\n");
}
void Print(SqBiTree T)
{ /* 逐層、按本層序號輸出二叉樹 */
  int j,k;
  position p;
  TElemType e;
  for(j=1;j<=BiTreeDepth(T);j++)
  {
    printf("第%d層: ",j);
    for(k=1;k<=pow(2,j-1);k++)
    {
      p.level=j;
      p.order=k;
      e=Value(T,p);
      if(e!=Nil)
      printf("%d:"form" ",k,e);
    }
    printf("\n");
  }
}