數據結構樹的專題

• 2019 年 12 月 2 日
• 筆記

一、二叉樹的基本操作

#include<stdio.h>  #include<stdlib.h>    typedef char ElemType;    typedef struct Node  {      ElemType data;      struct Node *lchild, *rchild;  } BiTree;    BiTree *createBT()  //鍵盤輸入創建二叉樹  {      BiTree *b;      ElemType ch;      scanf("%c", &ch);      fflush(stdin);  // 清空鍵盤緩衝      if(ch != '#')   // #表示空      {          b = (BiTree *)malloc(sizeof(BiTree));          b->data = ch;          printf("請輸入%c的左孩子：", ch);          b->lchild = createBT();          printf("請輸入%c的右孩子：", ch);          b->rchild = createBT();      }      else          b = NULL;      return b;  }    void createBT(BiTree *&b, char *s)  //用括弧表示法的字元串s生成二叉樹b  {      BiTree *st[100], *t;    //st存放樹結點的棧      int top = -1;      int k;      //k=1表示左孩子， k=2表示右孩子        b = NULL;      while(*s)      {          switch(*s)          {          case '(':              top++;              st[top] = t;              k = 1;      //準備處理左孩子              break;          case ')':              top--;              break;          case ',':              k = 2;      //準備處理右孩子              break;          default:              t = (BiTree *)malloc(sizeof(BiTree));              t->data = *s;              t->lchild = t->rchild = NULL;              if(b == NULL)                  b = t;              else              {                  switch(k)                  {                  case 1:                      st[top]->lchild = t; break;                  case 2:                      st[top]->rchild = t; break;                  }              }          }          s++;      }  }    BiTree *createBT_PreIn(char *pre, char *in, int n)  //由先序序列pre和中序序列in的n個字元構造二叉樹並返回  {      BiTree *b;      int i;      if(n<=0)          return NULL;      b = (BiTree *)malloc(sizeof(BiTree));      b->data = *pre;      for(i=0; i<n; i++)          if(in[i] == *pre)              break;      b->lchild = createBT_PreIn(pre+1, in, i);      b->rchild = createBT_PreIn(pre+i+1, in+i+1, n-i-1);        return b;  }    BiTree *createBT_InPost(char *in, char *post, int n)    //由中序序列in和後序序列post的n個字元構造二叉樹並返回  {      BiTree *b;      int i;      if(n <= 0)          return NULL;      b = (BiTree *)malloc(sizeof(BiTree));      b->data = *(post + n - 1);      for(i=0; i<n; i++)          if(in[i] == b->data)              break;      b->lchild = createBT_InPost(in, post, i);      b->rchild = createBT_InPost(in+i+1, post+i, n-i-1);        return b;  }    void preOrder(BiTree *b)    //先序遍歷二叉樹  {      if(b)      {          printf("%c", b->data);          preOrder(b->lchild);          preOrder(b->rchild);      }  }    void inOrder(BiTree *b)     //中序遍歷二叉樹  {      if(b)      {          inOrder(b->lchild);          printf("%c", b->data);          inOrder(b->rchild);      }  }    void postOrder(BiTree *b)   //後序遍歷二叉樹  {      if(b)      {          postOrder(b->lchild);          postOrder(b->rchild);          printf("%c", b->data);      }  }    void dispBT(BiTree *b)      //括弧法輸出二叉樹  {      if(b)      {          printf("%c", b->data);          if(b->lchild || b->rchild)          {              printf("(");              dispBT(b->lchild);              if(b->rchild)                  printf(",");              dispBT(b->rchild);              printf(")");          }      }  }    int BT_depth(BiTree *b)     //返二叉樹的高度  {      int dep1, dep2;      if(b == NULL)          return 0;        dep1 = BT_depth(b->lchild);      dep2 = BT_depth(b->rchild);        return (dep1 > dep2 ? dep1 :dep2) + 1;  }    int leafNum(BiTree *b)      //統計葉子節點的個數  {      if(b == NULL)          return 0;      if(b->lchild == NULL && b->rchild == NULL)          return 1;      return leafNum(b->lchild) + leafNum(b->rchild);  }    BiTree *findNode(BiTree *b, ElemType x)     //查找二叉樹b中值為x的結點，並返回該結點的指針  {      BiTree *p;      if(b == NULL)          return NULL;      else if(b->data == x)          return b;      else      {          p = findNode(b->lchild, x);          if(p != NULL)              return p;          else              return findNode(b->rchild, x);      }  }    void destroyBT(BiTree *&b)  //銷毀二叉樹  {      if(b)      {          destroyBT(b->lchild);          destroyBT(b->rchild);          free(b);          b = NULL;      }  }    void main()  {      BiTree *b;      char *s = "A(B(,X),C)";      char *pre = "ABXC";      char *in = "BXAC";      char *post = "XBCA";        //鍵盤輸入二叉樹      //printf("輸入根結點(#表示空)：");      //b = createBT();        //括弧表示法輸入二叉樹      //createBT(b, s);        //先序序列和中序序列輸入二叉樹      //b = createBT_PreIn(pre, in, 4);        //中序序列和後序序列輸入二叉樹      b = createBT_InPost(in, post, 4);        printf("n先序序列："); preOrder(b);      printf("n中序序列："); inOrder(b);      printf("n後序序列："); postOrder(b);      printf("n括弧表示法："); dispBT(b);      printf("n深度：%d" , BT_depth(b));      printf("n葉子數：%dn", leafNum(b));      destroyBT(b);  }  

二、樹、森林與二叉樹的轉換

1、樹轉換為二叉樹

由於二叉樹是有序的，為了避免混淆，對於無序樹，我們約定樹中的每個結點的孩子結點按從左到右的順序進行編號。

將樹轉換成二叉樹的步驟是： （1）加線。就是在所有兄弟結點之間加一條連線； （2）抹線。就是對樹中的每個結點，只保留他與第一個孩子結點之間的連線，刪除它與其它孩子結點之間的連線； （3）旋轉。就是以樹的根結點為軸心，將整棵樹順時針旋轉一定角度，使之結構層次分明。

2、森林轉換為二叉樹

森林是由若干棵樹組成，可以將森林中的每棵樹的根結點看作是兄弟，由於每棵樹都可以轉換為二叉樹，所以森林也可以轉換為二叉樹。

將森林轉換為二叉樹的步驟是： （1）先把每棵樹轉換為二叉樹； （2）第一棵二叉樹不動，從第二棵二叉樹開始，依次把後一棵二叉樹的根結點作為前一棵二叉樹的根結點的右孩子結點，用線連接起來。當所有的二叉樹連接起來後得到的二叉樹就是由森林轉換得到的二叉樹。

3、二叉樹轉換為樹

二叉樹轉換為樹是樹轉換為二叉樹的逆過程，其步驟是： （1）若某結點的左孩子結點存在，將左孩子結點的右孩子結點、右孩子結點的右孩子結點……都作為該結點的孩子結點，將該結點與這些右孩子結點用線連接起來； （2）刪除原二叉樹中所有結點與其右孩子結點的連線； （3）整理（1）和（2）兩步得到的樹，使之結構層次分明。

4、二叉樹轉換為森林

二叉樹轉換為森林比較簡單，其步驟如下： （1）先把每個結點與右孩子結點的連線刪除，得到分離的二叉樹； （2）把分離後的每棵二叉樹轉換為樹； （3）整理第（2）步得到的樹，使之規範，這樣得到森林。

根據樹與二叉樹的轉換關係以及二叉樹的遍歷定義可以推知，樹的先序遍歷與其轉換的相應的二叉樹的先序遍歷的結果序列相同；樹的後序遍歷與其轉換的二叉樹的中序遍歷的結果序列相同；樹的層序遍歷與其轉換的二叉樹的後序遍歷的結果序列相同。由森林與二叉樹的轉換關係以及森林與二叉樹的遍歷定義可知，森林的先序遍歷和中序遍歷與所轉換得到的二叉樹的先序遍歷和中序遍歷的結果序列相同。

三、AVL平衡二叉樹

四、哈夫曼樹的應用