程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C 言語二叉樹幾種遍歷辦法詳解及實例

C 言語二叉樹幾種遍歷辦法詳解及實例

編輯：關於C++

C 言語二叉樹幾種遍歷辦法詳解及實例。本站提示廣大學習愛好者：（C 言語二叉樹幾種遍歷辦法詳解及實例）文章只能為提供參考，不一定能成為您想要的結果。以下是C 言語二叉樹幾種遍歷辦法詳解及實例正文

二叉樹的一些概念

二叉樹就是每個結點最多有兩個子樹的樹形存儲構造。先上圖，方便前面剖析。

1 滿二叉樹和完全二叉樹

上圖就是典型的二叉樹，其中右邊的圖還叫做滿二叉樹，左邊是完全二叉樹。然後我們可以得出結論，滿二叉樹一定是完全二叉樹，但是反過去就不一定。滿二叉樹的定義是除了葉子結點，其它結點左右孩子都有,深度為k的滿二叉樹，結點數就是2的k次方減1。完全二叉樹是每個結點都與深度為k的滿二叉樹中編號從1到n逐個對應。

2 樹的深度

樹的最大層次就是深度，比方上圖，深度是4。很容易得出，深度為k的樹，擁有的最大結點數是2的k次方減1。

3 樹的孩子，兄弟，雙親

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

二如何創立二叉樹

先說說二叉樹的存儲構造，跟很多其它模型一樣，也有順序和鏈式兩種方式。前者雖然運用復雜，但是存在糜費空間的問題，舉個例子，下圖的二叉樹，用順序的方式存儲(0表示空，沒有子樹)是:

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

是不是相當糜費空間呢。

鏈式構造可以定義如下:

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

然後就可以寫一個函數來創立二叉樹，進程是在控制台輸出a表示加入以後這一層,不再為該層創立左右孩子。輸出其它字母表示持續創立。比方上面的輸出序列：

創立了如下構造的二叉樹,

每個結點裡的數值是隨機生成的小於100的數字。同時我也寫了一個自動的命令序列函數，方便測試，不必手動輸出，非自動和自動創立的函數如下:

//創立二叉樹, 先序順序 
int CreateBiTree(pBiTree *root) 
{ 
  char ch = 0; 
  fflush(stdin); 
  if ((ch = getchar()) == 'a')//控制樹的構造 
  { 
    *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; 
//創立二叉樹,自動執行，方便測試 
int CreateBiTreeAuto(pBiTree *root) 
{ 
  char szOrder[] = "bbaabaa"; 
  char ch = 0; 
  if (szOrder[g_i++] == 'a')//控制樹的構造 
  { 
    *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; 
}

三遍歷順序

先序遍歷

先序遍歷是先訪問根結點，再左子樹，再右子樹，比方圖1中的右圖，先序遍歷的輸入如下:

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

依據下面的思想，很容易用遞歸的方式寫出先序遍歷的代碼：

//先序遍歷 
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; 
  } 
}

中序遍歷和後序遍歷

有了先序的經歷，這兩個就很好了解了，中序是先訪問左子樹, 再根結點，再右子樹, 後序是先訪問左子樹, 再右子樹，再根結點。代碼更容易，只需改一下調用順序就可以了。

不過我這裡給出一種非遞歸的完成。遞歸固然是明晰明了，但是存在效率低的問題，非遞歸的方案用棧構造來存結點信息，經過出棧訪問來遍歷二叉樹。它思想是這樣的，當棧頂中的指針非空時，遍歷左子樹，也就是左子樹根的指針進棧。當棧頂指針為空時，應退至上一層，假如是從左子樹前往的，訪問以後層，也就是棧頂中的根指針結點。假如是從右子樹前往，闡明以後層遍歷終了，持續退棧。代碼如下:

//中序遍歷, 非遞歸完成 
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

感激閱讀，希望能協助到大家，謝謝大家對本站的支持！