維基百科

樹 (資料結構)

抽象資料結構

在電腦科學中，樹（英語：tree）是一種抽象資料類型（ADT）或是實作這種抽象資料類型的資料結構，用來類比具有樹狀結構性質的資料集合。它是由n（n>0）個有限節點組成一個具有層次關係的集合。把它叫做「樹」是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：

  • 每個節點都只有有限個子節點或無子節點；
  • 沒有父節點的節點稱為根節點；
  • 每一個非根節點有且只有一個父節點；
  • 除了根節點外，每個子節點可以分為多個不相交的子樹；
  • 樹裡面沒有環路(cycle)
一棵樹

術語

編輯
  1. 節點的度：一個節點含有的子樹的個數稱為該節點的度；
  2. 樹的度：一棵樹中，最大的節點度稱為樹的度；
  3. 葉節點或終端節點：度為零的節點；
  4. 非終端節點或分支節點：度不為零的節點；
  5. 父親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點；
  6. 孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點；
  7. 兄弟節點：具有相同父節點的節點互稱為兄弟節點；
  8. 節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；
  9. 深度：對於任意節點n,n的深度為從根到n的唯一路徑長，根的深度為0；
  10. 高度：對於任意節點n,n的高度為從n到一片樹葉的最長路徑長，所有樹葉的高度為0；
  11. 堂兄弟節點：父節點在同一層的節點互為堂兄弟；
  12. 節點的祖先：從根到該節點所經分支上的所有節點；
  13. 子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫。
  14. 森林：由m（m>=0）棵互不相交的樹的集合稱為森林；

樹的種類

編輯
有序/無序：
  • 無序樹：樹中任意節點的子節點之間沒有順序關係，這種樹稱為無序樹，也稱為自由樹。
  • 有序樹/搜尋樹/尋找樹：樹中任意節點的子節點之間有順序關係，這種樹稱為有序樹。即樹的所有節點按照一定的順序排列，這樣進行插入、刪除、尋找時效率就會非常高
平衡/不平衡：
節點的分叉情況：
  • 等叉樹：是每個節點的鍵值個數都相同、子節點個數也都相同
    • 二元樹：每個節點最多含有兩個子樹的樹稱為二元樹；
      • 完全二元樹：對於一棵二元樹，假設其深度為d（d>1）。除了第d層外，其它各層的節點數目均已達最大值，且第d層所有節點從左向右連續地緊密排列，這樣的二元樹被稱為完全二元樹；
        • 滿二元樹：所有葉節點都在最底層的完全二元樹；
      • 平衡二元樹（AVL樹）：若且唯若任何節點的兩棵子樹的高度差不大於1的二元樹；
      • 排序二元樹：也稱二元搜尋樹、二元搜尋樹、有序二元樹；
    • 霍夫曼樹：帶權路徑最短的二元樹稱為哈夫曼樹或最佳二元樹；
    • 多叉樹（英語：m-ary tree）
  • 不等叉樹：每個節點的鍵值個數不一定相同、子節點個數也不一定相同
    • B樹：對不等叉樹的節點鍵值數和插入、刪除邏輯添加一些特殊的要求，使其能達到絕對平衡的效果。B樹全稱Balance Tree。如果某個B樹上所有節點的分叉數最大值是m，則把這個B數叫做m階B樹。

儲存

編輯

父節點表示法

編輯

儲存結構

編輯 
/* 树节点的定义 */
#define MAX_TREE_SIZE 100
typedef struct
{
  TElemType data;
  int parent; /* 父节点位置域 */
} PTNode;
typedef struct
{
  PTNode nodes[MAX_TREE_SIZE];
  int n; /* 节点数 */
} PTree;
 
A
B
E
 

H

 
 

I

 
 

J

 
 
 
 

C

 
D
 

F

 
G
 

K

 
 
 
 

基本操作

編輯

設已有鏈佇列類型LinkQueue的定義及基本操作（參見佇列）。

構造空樹
編輯

清空或銷毀一個樹也是同樣的操作 

void ClearTree(PTree *T)
{ 
  T->n = 0;
}
構造樹
編輯 
void CreateTree(PTree *T)
{ 
  LinkQueue q;
  QElemType p,qq;
  int i=1,j,l;
  char c[MAX_TREE_SIZE]; /* 临时存放孩子节点数组 */
  InitQueue(&q); /* 初始化队列 */
  printf("请输入根节点(字符型，空格为空): ");
  scanf("%c%*c",&T->nodes[0].data); /* 根节点序号为0，%*c吃掉回车符 */
  if(T->nodes[0].data!=Nil) /* 非空树 */
  {
    T->nodes[0].parent=-1 ; /* 根节点无父节点 */
    qq.name=T->nodes[0].data;
    qq.num=0;
    EnQueue(&q,qq); /* 入队此节点 */
    while(i<MAX_TREE_SIZE&&!QueueEmpty(q)) /* 数组未满且队不空 */
    {
      DeQueue(&q,&qq); /* 节点加入队列 */
      printf("请按长幼顺序输入节点%c的所有孩子: ",qq.name);
      gets(c);
      l=strlen(c);
      for(j=0;j<l;j++)
      {
        T->nodes[i].data=c[j];
        T->nodes[i].parent=qq.num;
        p.name=c[j];
        p.num=i;
        EnQueue(&q,p); /* 入队此节点 */
        i++;
      }
    }
    if(i>MAX_TREE_SIZE)
    {
      printf("节点数超过数组容量\n");
      exit(OVERFLOW);
    }
    T->n=i;
  }
  else
    T->n=0;
}
判斷樹是否為空
編輯 
Status TreeEmpty(PTree *T)
{ /* 初始条件：树T存在。操作结果：若T为空树，则返回TRUE，否则返回FALSE */
  return T->n==0;
}
取得樹的深度
編輯 
int TreeDepth(PTree *T)
{ /* 初始条件：树T存在。操作结果：返回T的深度 */
  int k,m,def,max=0;
  for(k=0;k<T->n;++k)
  {
    def=1; /* 初始化本节点的深度 */
    m=T->nodes[k].parent;
    while(m!=-1)
    {
      m=T->nodes[m].parent;
      def++;
    }
    if(max<def)
      max=def;
  }
  return max; /* 最大深度 */
}
取得根節點
編輯 
TElemType Root(PTree *T)
{ /* 初始条件：树T存在。操作结果：返回T的根 */
  int i;
  for(i=0;i<T->n;i++)
    if(T->nodes[i].parent<0)
      return T->nodes[i].data;
  return Nil;
}
取得第i個節點的值
編輯 
TElemType Value(PTree *T,int i)
{ /* 初始条件：树T存在，i是树T中节点的序号。操作结果：返回第i个节点的值 */
  if(i<T->n)
    return T->nodes[i].data;
  else
    return Nil;
}
改變節點的值
編輯 
Status Assign(PTree *T,TElemType cur_e,TElemType value)
{ /* 初始条件：树T存在，cur_e是树T中节点的值。操作结果：改cur_e为value */
  int j;
  for(j=0;j<T->n;j++)
  {
    if(T->nodes[j].data==cur_e)
    {
      T->nodes[j].data=value;
      return OK;
    }
  }
  return ERROR;
}
取得節點的父節點
編輯 
TElemType Parent(PTree *T,TElemType cur_e)
{ /* 初始条件：树T存在，cur_e是T中某个节点 */
  /* 操作结果：若cur_e是T的非根节点，则返回它的父节点，否则函数值为＂空＂*/
  int j;
  for(j=1;j<T->n;j++) /* 根节点序号为0 */
    if(T->nodes[j].data==cur_e)
      return T->nodes[T->nodes[j].parent].data;
  return Nil;
}
取得節點的最左孩子節點
編輯 
TElemType LeftChild(PTree *T,TElemType cur_e)
{ /* 初始条件：树T存在，cur_e是T中某个节点 */
  /* 操作结果：若cur_e是T的非叶子节点，则返回它的最左孩子，否则返回＂空＂*/
  int i,j;
  for(i=0;i<T->n;i++)
    if(T->nodes[i].data==cur_e) /* 找到cur_e，其序号为i */
      break;
  for(j=i+1;j<T->n;j++) /* 根据树的构造函数，孩子的序号＞其父节点的序号 */
    if(T->nodes[j].parent==i) /* 根据树的构造函数，最左孩子(长子)的序号＜其它孩子的序号 */
      return T->nodes[j].data;
  return Nil;
}
取得節點的右兄弟節點
編輯 
TElemType RightSibling(PTree *T,TElemType cur_e)
{ /* 初始条件：树T存在，cur_e是T中某个节点 */
  /* 操作结果：若cur_e有右(下一个)兄弟，则返回它的右兄弟，否则返回＂空＂*/
  int i;
  for(i=0;i<T->n;i++)
    if(T->nodes[i].data==cur_e) /* 找到cur_e，其序号为i */
      break;
  if(T->nodes[i+1].parent==T->nodes[i].parent)
  /* 根据树的构造函数，若cur_e有右兄弟的话则右兄弟紧接其后 */
    return T->nodes[i+1].data;
  return Nil;
}
輸出樹
編輯 
void Print(PTree *T)
{ /* 输出树T。加 */
  int i;
  printf("节点个数=%d\n",T->n);
  printf(" 节点 父节点\n");
  for(i=0;i<T->n;i++)
  {
    printf("    %c",Value(T,i)); /* 节点 */
    if(T->nodes[i].parent>=0) /* 有父节点 */
      printf("    %c",Value(T,T->nodes[i].parent)); /* 父节点 */
    printf("\n");
  }
}
向樹中插入另一棵樹
編輯 
Status InsertChild(PTree *T,TElemType p,int i,PTree c)
{ /* 初始条件：树T存在，p是T中某个节点，1≤i≤p所指节点的度+1，非空树c与T不相交 */
  /* 操作结果：插入c为T中p节点的第i棵子树 */
  int j,k,l,f=1,n=0; /* 设交换标志f的初值为1，p的孩子数n的初值为0 */
  PTNode t;
  if(!TreeEmpty(T)) /* T不空 */
  {
    for(j=0;j<T->n;j++) /* 在T中找p的序号 */
      if(T->nodes[j].data==p) /* p的序号为j */
        break;
    l=j+1; /* 如果c是p的第1棵子树，则插在j+1处 */
    if(i>1) /* c不是p的第1棵子树 */
    {
      for(k=j+1;k<T->n;k++) /* 从j+1开始找p的前i-1个孩子 */
        if(T->nodes[k].parent==j) /* 当前节点是p的孩子 */
        {
          n++; /* 孩子数加1 */
          if(n==i-1) /* 找到p的第i-1个孩子，其序号为k1 */
            break;
        }
      l=k+1; /* c插在k+1处 */
    } /* p的序号为j，c插在l处 */
    if(l<T->n) /* 插入点l不在最后 */
      for(k=T->n-1;k>=l;k--) /* 依次将序号l以后的节点向后移c.n个位置 */
      {
        T->nodes[k+c.n]=T->nodes[k];
        if(T->nodes[k].parent>=l)
          T->nodes[k+c.n].parent+=c.n;
      }
    for(k=0;k<c.n;k++)
    {
      T->nodes[l+k].data=c.nodes[k].data; /* 依次将树c的所有节点插于此处 */
      T->nodes[l+k].parent=c.nodes[k].parent+l;
    }
    T->nodes[l].parent=j; /* 树c的根节点的父节点为p */
    T->n+=c.n; /* 树T的节点数加c.n个 */
    while(f)
    { /* 从插入点之后，将节点仍按层序排列 */
      f=0; /* 交换标志置0 */
      for(j=l;j<T->n-1;j++)
        if(T->nodes[j].parent>T->nodes[j+1].parent)
        {/* 如果节点j的父节点排在节点j+1的父节点之后（树没有按层序排列），交换两节点*/
          t=T->nodes[j];
          T->nodes[j]=T->nodes[j+1];
          T->nodes[j+1]=t;
          f=1; /* 交换标志置1 */
          for(k=j;k<T->n;k++) /* 改变父节点序号 */
            if(T->nodes[k].parent==j)
              T->nodes[k].parent++; /* 父节点序号改为j+1 */
            else if(T->nodes[k].parent==j+1)
              T->nodes[k].parent--; /* 父节点序号改为j */
        }
    }
    return OK;
  }
  else /* 树T不存在 */
    return ERROR;
}
刪除子樹
編輯 
Status deleted[MAX_TREE_SIZE+1]; /* 删除标志数组(全局量) */
void DeleteChild(PTree *T,TElemType p,int i)
{ /* 初始条件：树T存在，p是T中某个节点，1≤i≤p所指节点的度 */
  /* 操作结果：删除T中节点p的第i棵子树 */
  int j,k,n=0;
  LinkQueue q;
  QElemType pq,qq;
  for(j=0;j<=T->n;j++)
    deleted[j]=0; /* 置初值为0(不删除标记) */
  pq.name='a'; /* 此成员不用 */
  InitQueue(&q); /* 初始化队列 */
  for(j=0;j<T->n;j++)
    if(T->nodes[j].data==p)
      break; /* j为节点p的序号 */
  for(k=j+1;k<T->n;k++)
  {
    if(T->nodes[k].parent==j)
      n++;
    if(n==i)
      break; /* k为p的第i棵子树节点的序号 */
  }
  if(k<T->n) /* p的第i棵子树节点存在 */
  {
    n=0;
    pq.num=k;
    deleted[k]=1; /* 置删除标记 */
    n++;
    EnQueue(&q,pq);
    while(!QueueEmpty(q))
    {
      DeQueue(&q,&qq);
      for(j=qq.num+1;j<T->n;j++)
        if(T->nodes[j].parent==qq.num)
        {
          pq.num=j;
          deleted[j]=1; /* 置删除标记 */
          n++;
          EnQueue(&q,pq);
        }
    }
    for(j=0;j<T->n;j++)
      if(deleted[j]==1)
      {
        for(k=j+1;k<=T->n;k++)
        {
          deleted[k-1]=deleted[k];
          T->nodes[k-1]=T->nodes[k];
          if(T->nodes[k].parent>j)
            T->nodes[k-1].parent--;
        }
        j--;
      }
    T->n-=n; /* n为待删除节点数 */
  }
}
層序遍歷樹
編輯 
void TraverseTree(PTree *T,void(*Visit)(TElemType))
{ /* 初始条件：二叉树T存在,Visit是对节点操作的应用函数 */
  /* 操作结果：层序遍历树T,对每个节点调用函数Visit一次且仅一次 */
  int i;
  for(i=0;i<T->n;i++)
    Visit(T->nodes[i].data);
  printf("\n");
}

孩子鏈結串列表示法

編輯

儲存結構

編輯 
/*树的孩子链表存储表示*/
typedef struct CTNode { // 孩子节点
  int child;
  struct CTNode *next;
} *ChildPtr;
typedef struct {
  ElemType data； // 节点的数据元素
  ChildPtr firstchild； // 孩子链表头指针
} CTBox;
typedef struct {
  CTBox nodes[MAX_TREE_SIZE]；
  int n, r； // 节点数和根节点的位置
} CTree;

 

A
B
E
 

H

 
 

I

 
 

J

 
 
 
 

C

 
D
 

F

 
G
 

K

 
 
 
 

森林、樹與二元樹的轉換

編輯

見二元樹相應章節

外部連結

編輯

參考文獻

編輯
取自「https://zh.wikipedia.org/w/index.php?title=树_(数据结构)&oldid=81237364」