樹(數據結構名詞)

樹狀圖是一種數據結構，它是由n（n>=1）個有限結點組成一個具有層次關係的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：

每個結點有零個或多個子結點；沒有父結點的結點稱為根結點；每一個非根結點有且只有一個父結點；除了根結點外，每個子結點可以分為多個不相交的子樹；

基本介紹

• 中文名：樹
• 外文名：tree
• 數據結構：基本數據結構的一種

定義

樹（tree）是包含n（n>=0）個結點的有窮集，其中：

（1）每個元素稱為結點（node）；

（2）有一個特定的結點被稱為根結點或樹根（root）。

（3）除根結點之外的其餘數據元素被分為m（m≥0）個互不相交的集合T1，T2，……Tm-1，其中每一個集合Ti（1<=i<=m）本身也是一棵樹，被稱作原樹的子樹（subtree）。

樹也可以這樣定義：樹是由根結點和若干顆子樹構成的。樹是由一個集合以及在該集合上定義的一種關係構成的。集合中的元素稱為樹的結點，所定義的關係稱為父子關係。父子關係在樹的結點之間建立了一個層次結構。在這種層次結構中有一個結點具有特殊的地位，這個結點稱為該樹的根結點，或稱為樹根。

我們可以形式地給出樹的遞歸定義如下:

單個結點是一棵樹，樹根就是該結點本身。

設T1,T2,..,Tk是樹，它們的根結點分別為n1,n2,..,nk。用一個新結點n作為n1,n2,..,nk的父親，則得到一棵新樹，結點n就是新樹的根。我們稱n1,n2,..,nk為一組兄弟結點，它們都是結點n的子結點。我們還稱T1,T2,..,Tk為結點n的子樹。

空集合也是樹，稱為空樹。空樹中沒有結點。

相關術語

節點的度：一個節點含有的子樹的個數稱為該節點的度；

葉節點或終端節點：度為0的節點稱為葉節點；

非終端節點或分支節點：度不為0的節點；

雙親節點或父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點；

孩子節點或子節點：一個節點含有的子樹的根節點稱為該節點的子節點；

兄弟節點：具有相同父節點的節點互稱為兄弟節點；

樹的度：一棵樹中，最大的節點的度稱為樹的度；

節點的層次：從根開始定義起，根為第1層，根的子節點為第2層，以此類推；

樹的高度或深度：樹中節點的最大層次；

堂兄弟節點：雙親在同一層的節點互為堂兄弟；

節點的祖先：從根到該節點所經分支上的所有節點；

子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫。

森林：由m（m>=0）棵互不相交的樹的集合稱為森林；

種類

無序樹：樹中任意節點的子結點之間沒有順序關係，這種樹稱為無序樹,也稱為自由樹;

有序樹：樹中任意節點的子結點之間有順序關係，這種樹稱為有序樹；

二叉樹：每個節點最多含有兩個子樹的樹稱為二叉樹；

完全二叉樹

滿二叉樹

霍夫曼樹：帶權路徑最短的二叉樹稱為哈夫曼樹或最優二叉樹；

深度

定義一棵樹的根結點層次為1，其他節點的層次是其父結點層次加1。一棵樹中所有結點的層次的最大值稱為這棵樹的深度。

表示方法

圖像表達法

樹的表示方法有很多種，最常用的是圖像表示法。

一下是一個普通的樹（非二叉樹）：

符號表達法

用括弧先將根結點放入一對圓括弧中，然後把它的子樹由左至右的順序放入括弧中，而對子樹也採用同樣的方法處理；同層子樹與它的根結點用圓括弧括起來，同層子樹之間用逗號隔開，最後用閉括弧括起來。如前文樹形表示法可以表示為：（1（2（5（9，10）），3（6，7），4（8）））

遍歷表達法

遍歷表達法有3種方法：先序遍歷、中序遍歷、後序遍歷

例如右圖：

其先序遍歷為ABDECF

其中序遍歷為DBEAFC

其後序遍歷為DEBFCA

具體請參照參考資料

其他

關於二叉樹的其他知識請參照參考資料。

父節點表示法

存儲結構

/* 樹節點的定義 */#define MAX_TREE_SIZE 100typedef struct{    TElemType data;    int parent; /* 父節點位置域 */} PTNode;typedef struct{    PTNode nodes[MAX_TREE_SIZE];    int n; /* 節點數 */} PTree;

基本操作

設已有鏈佇列類型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;