如何實(shí)現(xiàn)遞歸刪除二叉樹中以x為根的子樹

小編給大家分享一下如何實(shí)現(xiàn)遞歸刪除二叉樹中以x為根的子樹，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

名稱：刪除二叉樹中以x為根的子樹

說明:此程序的大部分內(nèi)容，注釋都解釋的較為詳細(xì)了。在這里需要提及一點(diǎn)的是此處遞歸函數(shù)flag傳遞的不是上篇中講的引用，而是普通的變量，因?yàn)樵谙蛳聜鬟f參數(shù)（當(dāng)前結(jié)點(diǎn)是否是x的信息）的過程中只要傳遞給對應(yīng)的子樹，并不需要傳遞給整個樹的結(jié)點(diǎn)。在下一篇會做個關(guān)于遞歸傳遞參數(shù)的總結(jié)。

//遞歸刪除二叉樹中以x為根的子樹，（flag為標(biāo)志）
int DelRoot_x(BiTree &T, int x,int flag)
{
  if(T == NULL)
    return 0;
  else
  {
    if(T->data == x)  //如果當(dāng)前節(jié)點(diǎn)的值為x，則更改標(biāo)志位，在下面將向遞歸子函數(shù)中傳遞flag值
    {
      flag = 1;
    }
    int lef_ret = DelRoot_x(T->lchild,x,flag); //遞歸左子樹，lef_ret為從左子樹中返回的信息
    int rig_ret = DelRoot_x(T->rchild,x,flag); //遞歸右子樹，rig_ret為從右子樹中返回的信息
    if(1 == flag)    //如果標(biāo)志為1，說明其祖父結(jié)點(diǎn)中有x，也就是說當(dāng)前結(jié)點(diǎn)需要刪除
    {
      if(T->data == x)  //如果是x結(jié)點(diǎn)，則需要向上層結(jié)點(diǎn)傳遞信息，以便其父節(jié)點(diǎn)將對應(yīng)的指針域賦空
        return 1;
      delete T;
    }
    else
    {
       if(1 == lef_ret)  //從子結(jié)點(diǎn)接受收的信息，即如果其子結(jié)點(diǎn)為x，需要將其指針域賦空
        T->lchild = NULL;
      if(1 == rig_ret )  //從子結(jié)點(diǎn)接受收的信息，即如果其子結(jié)點(diǎn)為x，需要將其指針域賦空
        T->rchild = NULL;
    }
  }
  return 0;
}

以上是“如何實(shí)現(xiàn)遞歸刪除二叉樹中以x為根的子樹”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識，歡迎關(guān)注億速云行業(yè)資訊頻道！