二叉樹(shù)的一些概念

二叉樹(shù)就是每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹(shù)的樹(shù)形存儲(chǔ)結(jié)構(gòu)。先上圖，方便后面分析。

 1 滿(mǎn)二叉樹(shù)和完全二叉樹(shù) 

上圖就是典型的二叉樹(shù)，其中左邊的圖還叫做滿(mǎn)二叉樹(shù)，右邊是完全二叉樹(shù)。然后我們可以得出結(jié)論，滿(mǎn)二叉樹(shù)一定是完全二叉樹(shù)，但是反過(guò)來(lái)就不一定。滿(mǎn)二叉樹(shù)的定義是除了葉子結(jié)點(diǎn)，其它結(jié)點(diǎn)左右孩子都有,深度為k的滿(mǎn)二叉樹(shù)，結(jié)點(diǎn)數(shù)就是2的k次方減1。完全二叉樹(shù)是每個(gè)結(jié)點(diǎn)都與深度為k的滿(mǎn)二叉樹(shù)中編號(hào)從1到n一一對(duì)應(yīng)。

 2 樹(shù)的深度

樹(shù)的最大層次就是深度，比如上圖，深度是4。很容易得出，深度為k的樹(shù)，擁有的最大結(jié)點(diǎn)數(shù)是2的k次方減1。

 3 樹(shù)的孩子，兄弟，雙親

上圖中，B,C是A的孩子，B,C之間互為兄弟，A是B,C的雙親。

 二如何創(chuàng)建二叉樹(shù)

先說(shuō)說(shuō)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，跟很多其它模型一樣，也有順序和鏈?zhǔn)絻煞N方式。前者雖然使用簡(jiǎn)單，但是存在浪費(fèi)空間的問(wèn)題，舉個(gè)例子，下圖的二叉樹(shù)，用順序的方式存儲(chǔ)(0表示空，沒(méi)有子樹(shù))是:

1 2 3 4 5 6 7 0 0 0 0 8 0 0 0

 是不是相當(dāng)浪費(fèi)空間呢。

 鏈?zhǔn)浇Y(jié)構(gòu)可以定義如下:

typedef struct _BiTNode 
{ 
  int data; 
  _BiTNode *leftChild; 
  _BiTNode *rightChild; 
}BiTNode, *pBiTree; 

然后就可以寫(xiě)一個(gè)函數(shù)來(lái)創(chuàng)建二叉樹(shù)，過(guò)程是在控制臺(tái)輸入a表示退出當(dāng)前這一層,不再為該層創(chuàng)建左右孩子。輸入其它字母表示繼續(xù)創(chuàng)建。比如下面的輸入序列：

 創(chuàng)建了如下結(jié)構(gòu)的二叉樹(shù),

 每個(gè)結(jié)點(diǎn)里的數(shù)值是隨機(jī)生成的小于100的數(shù)字。同時(shí)我也寫(xiě)了一個(gè)自動(dòng)的命令序列函數(shù)，方便測(cè)試，不用手動(dòng)輸入，非自動(dòng)和自動(dòng)創(chuàng)建的函數(shù)如下:

//創(chuàng)建二叉樹(shù), 先序順序 
int CreateBiTree(pBiTree *root) 
{ 
  char ch = 0; 
  fflush(stdin); 
  if ((ch = getchar()) == 'a')//控制樹(shù)的結(jié)構(gòu) 
  { 
    *root = NULL; 
  } 
  else 
  { 
    *root = (BiTNode *)malloc(sizeof(BiTNode)); 
    if (!(*root)) 
    { 
      return RET_ERROR; 
    } 
    (*root)->data = GetRandom(); 
    CreateBiTree(&(*root)->leftChild); 
    CreateBiTree(&(*root)->rightChild); 
  } 
  return RET_OK; 
} 
 
int g_i = 0; 
//創(chuàng)建二叉樹(shù),自動(dòng)執(zhí)行，方便測(cè)試 
int CreateBiTreeAuto(pBiTree *root) 
{ 
  char szOrder[] = "bbaabaa"; 
  char ch = 0; 
  if (szOrder[g_i++] == 'a')//控制樹(shù)的結(jié)構(gòu) 
  { 
    *root = NULL; 
  } 
  else 
  { 
    *root = (BiTNode *)malloc(sizeof(BiTNode)); 
    if (!(*root)) 
    { 
      return RET_ERROR; 
    } 
    (*root)->data = GetRandom(); 
    CreateBiTreeAuto(&(*root)->leftChild); 
    CreateBiTreeAuto(&(*root)->rightChild); 
  } 
  return RET_OK; 
} 

三遍歷順序

先序遍歷

先序遍歷是先訪(fǎng)問(wèn)根結(jié)點(diǎn)，再左子樹(shù)，再右子樹(shù)，比如圖1中的右圖，先序遍歷的輸出如下:

A,B,D,H,I,E,J,K,C,F,G

根據(jù)上面的思想，很容易用遞歸的形式寫(xiě)出先序遍歷的代碼：

//先序遍歷 
int PreOrderVisitTree(pBiTree T, VisitType pFuncVisit) 
{ 
  if (T) 
  { 
    (*pFuncVisit)(T->data); 
    if (PreOrderVisitTree(T->leftChild, pFuncVisit) == RET_OK) 
    { 
      if (PreOrderVisitTree(T->rightChild, pFuncVisit) == RET_OK) 
      { 
        return RET_OK; 
      } 
    } 
    return RET_ERROR; 
  } 
  else 
  { 
    return RET_OK; 
  } 
} 

中序遍歷和后序遍歷

有了先序的經(jīng)驗(yàn)，這兩個(gè)就很好理解了，中序是先訪(fǎng)問(wèn)左子樹(shù), 再根結(jié)點(diǎn)，再右子樹(shù), 后序是先訪(fǎng)問(wèn)左子樹(shù), 再右子樹(shù)，再根結(jié)點(diǎn)。代碼更容易，只要改一下調(diào)用順序就可以了。

不過(guò)我這里給出一種非遞歸的實(shí)現(xiàn)。遞歸固然是清晰明了，但是存在效率低的問(wèn)題，非遞歸的方案用棧結(jié)構(gòu)來(lái)存結(jié)點(diǎn)信息，通過(guò)出棧訪(fǎng)問(wèn)來(lái)遍歷二叉樹(shù)。它思想是這樣的，當(dāng)棧頂中的指針?lè)强諘r(shí)，遍歷左子樹(shù)，也就是左子樹(shù)根的指針進(jìn)棧。當(dāng)棧頂指針為空時(shí)，應(yīng)退至上一層，如果是從左子樹(shù)返回的，訪(fǎng)問(wèn)當(dāng)前層，也就是棧頂中的根指針結(jié)點(diǎn)。如果是從右子樹(shù)返回，說(shuō)明當(dāng)前層遍歷完畢，繼續(xù)退棧。代碼如下:

//中序遍歷, 非遞歸實(shí)現(xiàn) 
int InOrderVisitTree(pBiTree T, VisitType pFuncVisit) 
{ 
  ponyStack binaryTreeStack; 
  InitStack(&binaryTreeStack, 4); 
  Push(&binaryTreeStack, &T); 
  pBiTree pTempNode; 
 
  while (!IsEmptyStack(binaryTreeStack)) 
  { 
    while((GetTop(binaryTreeStack, &pTempNode) == RET_OK) && (pTempNode != NULL)) 
    { 
      Push(&binaryTreeStack, &(pTempNode->leftChild)); 
    } 
    Pop(&binaryTreeStack, &pTempNode); 
    if (!IsEmptyStack(binaryTreeStack)) 
    { 
      Pop(&binaryTreeStack, &pTempNode); 
      (*pFuncVisit)(pTempNode->data); 
      Push(&binaryTreeStack, &(pTempNode->rightChild)); 
    } 
  } 
  return RET_OK; 
} 

代碼下載地址:http://xiazai.jb51.net/201701/yuanma/BinaryTreeDemo-master(jb51.net).rar

感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！

最新評(píng)論