在這一節(jié)中，我們來學(xué)習如何使用程序來實現(xiàn)一棵文件樹。在上一節(jié)中，我們了解到使用文件樹的方式來整合計算機中所有的資源，而這一棵文件樹則是一棵多叉樹。也就是說，樹上的每一個節(jié)點都可能有多個子節(jié)點。

而這樣的一棵多叉樹在計算機中來實現(xiàn)是較為復(fù)雜的，使用起來也不方便。例如我們想要為節(jié)點1增加一個子節(jié)點2，之后再為節(jié)點1增加一個子節(jié)點3，之后再為節(jié)點1增加一個子節(jié)點4。整個過程如下圖：

由于這是一棵多叉樹，因此節(jié)點1可能具有多個子節(jié)點。這樣一來，在為節(jié)點1分配內(nèi)存時，我們就無法確定的為其分配指定大小，由于樹型結(jié)構(gòu)的特點，我們需要使用一個指針變量用于指向其一個子節(jié)點，而如果其具有2個子節(jié)點，則需要2個指針變量，如果其具有3個子節(jié)點，則需要3個指針變量。

于是對于多叉樹來說，當一個節(jié)點增加一個子節(jié)點時，當前節(jié)點也需要發(fā)生變化，也就是需要重新申請一個較大的內(nèi)存空間用于存放更多的指針變量。同樣的，當一個節(jié)點的子節(jié)點被刪除時，也需要重新申請內(nèi)存，釋放多余的指針變量。這對于編程實現(xiàn)多叉樹來說，是很復(fù)雜的，也是低效的。因此我們有必要尋找一種簡潔的辦法來處理多叉樹的實現(xiàn)問題。

我們知道，使用計算機編程來實現(xiàn)一個二叉樹是非常簡單的，每一個節(jié)點除了實際數(shù)據(jù)區(qū)域外只需要額外兩個指針用于存放其左孩子節(jié)點和右孩子節(jié)點即可，而且其內(nèi)存申請和釋放都很簡潔。二叉樹就是每一個節(jié)點的子節(jié)點最多不能超過2個節(jié)點，如下圖則是一個二叉樹：

為了解決多叉樹的問題，我們自然想到是否能將一個多叉樹轉(zhuǎn)化為一個二叉樹，并使用計算機程序來實現(xiàn)呢？答案是肯定的！其實，每一棵多叉樹都可以轉(zhuǎn)化為一個等價的二叉樹。進而可以將一個具有多個多叉樹的森林轉(zhuǎn)化為一個與之等價的二叉樹。

具體轉(zhuǎn)化的過程是這樣的：我們可以定義一個二叉樹的節(jié)點，并定義兩個指針變量，這兩個指針變量分別為指向其“子節(jié)點”（child）和其“兄弟節(jié)點”（sibling），也就是說，一個二叉樹的兩個叉，左側(cè)表示其孩子，而右側(cè)表示其兄弟。于是我們就可以將一個多叉樹轉(zhuǎn)化一個二叉樹，具體轉(zhuǎn)化過程如下：

上圖中的多叉樹和二叉樹是等價的，這兩棵樹所表示的內(nèi)容完全一致，只是在結(jié)構(gòu)上不同而已。也就是說這棵多叉樹可以轉(zhuǎn)化為二叉樹，二叉樹也可以轉(zhuǎn)化為多叉樹，本質(zhì)上講它們二者是可以相互轉(zhuǎn)化的，而沒有任何的不同。

對于這棵二叉樹來講，其“左叉”表示其孩子節(jié)點，而“右叉”表示其兄弟節(jié)點。而二叉樹在計算機程序中是比較容易實現(xiàn)的。接下來我們就定義這樣一棵二叉樹，用于表示其原有的多叉樹：

typedef struct vfs_node_s
{
  struct vfs_node_s *child;
  struct vfs_node_s *sibling;
  char name[200];
} vfs_node_s;

我們簡單的定義name屬性為表示這個節(jié)點的數(shù)據(jù)內(nèi)容，而左叉child為其子節(jié)點，而右叉sibling為其兄弟節(jié)點。然后實現(xiàn)兩函數(shù)用于初始化和銷毀這個虛擬文件樹：

int vfs_init(void)
{
  vfs = malloc(sizeof(vfs_s));
  vfs- >root = malloc(sizeof(vfs_node_s));
  strncpy(vfs- >root- >name, "/", NODE_NAME_SIZE);
  vfs- >root- >child = NULL;
  vfs- >root- >sibling = NULL;


  return 0;
}


int vfs_destory(void)
{
  vfs_destory_r(&vfs- >root);
  free(vfs);
  return 0;
}

完成初始化和銷毀虛擬文件樹之后我們再來實現(xiàn)對任意節(jié)點進行的插入和刪除操作，也就是說針對虛擬文件樹，我們在指定位置插入一個新的節(jié)點：

int vfs_insert_node(char *path, file_operations_s ops)
{
  if (path[0] != '/')
  {
    return -1;
  }
  //插入子節(jié)點，調(diào)用遞歸函數(shù)
  int ret = vfs_insert_node_r(&vfs- >root- >child, &path[1], ops);
  return ret;
}


int vfs_insert_node_r(vfs_node_s **node, char *abs_path, file_operations_s ops)
{
  if (node == NULL)
  {
    return -1;
  }
  if (abs_path == NULL)
  {
    return -1;
  }
  if (abs_path[0] == 0)
  {
    return -1;
  }
  char node_name[NODE_NAME_SIZE] = {0};
  //找到虛擬文件樹上的指定路徑
  char *p = abs_path;
  for (int i = 0; *p != '/' && *p != 0 && i < NODE_NAME_SIZE; i++)
  {
    node_name[i] = *p++;
  }
  if (*p == '/' && *p != 0)
  {
    p++;
  }
  //查找其所有兄弟節(jié)點
  while (*node != NULL)
  {
    //找到兄弟節(jié)點
    if (strcmp((*node)- >name, node_name) == 0)
    {
      //遞歸執(zhí)行其子節(jié)點插入操作
      return vfs_insert_node_r(&(*node)- >child, p, ops);
    }
    node = &(*node)- >sibling;
  }


  //最后生成一個新節(jié)點
  vfs_node_s *node_new = malloc(sizeof(vfs_node_s));
  strncpy(node_new- >name, node_name, NODE_NAME_SIZE);
  node_new- >child = NULL;
  node_new- >sibling = NULL;
  *node = node_new;
  //將新節(jié)點插入
  if (*p != 0)
  {
    return vfs_insert_node_r(&node_new- >child, p, ops);
  }
  return 0;
}

這樣，我們就完成了二叉樹的創(chuàng)建、銷毀與插入功能，當然還應(yīng)該實現(xiàn)針對指定節(jié)點的刪除功能，這里我們不再給出具體實現(xiàn)代碼，請讀者自行完成。這樣的二叉樹就可以完整的表示我們計算機中的虛擬文件系統(tǒng)（根節(jié)點是虛擬節(jié)點，并非是實際存在的，Linux系統(tǒng)中的根節(jié)點是實際的硬盤分區(qū)，因此Linux的文件系統(tǒng)不是虛擬文件系統(tǒng)）。

此后我們就可以用這一棵二叉樹來表示計算機中的所有資源了，具體方式則是將資源抽象成一個文件，掛載到文件系統(tǒng)中，成為文件系統(tǒng)中的一個節(jié)點，這樣就可以方便用戶管理和使用這些資源了。