二叉樹先根（先序）遍歷的改進

更新時間：2014年01月09日 15:15:10 作者：

這篇文章主要介紹了二叉樹先根（先序）遍歷的改進，有需要的朋友可以參考一下

二叉樹的特點：每個結(jié)點的度最大不能超過2，并且左右子樹不能顛倒

二叉樹的存儲結(jié)構(gòu)：下面采用鏈?zhǔn)酱鎯M行闡述，堆排序算法（快速排序改進）采用的順序存儲結(jié)構(gòu)的二叉樹，先看如下結(jié)構(gòu)體的存儲方式

順序存儲：

復(fù)制代碼代碼如下:

/*二叉樹的順序存儲*/
#define  MAX_TREE_SIZE 100
typedef  TElemType  SqBiTree[MAX_TREE_SIZE];

鏈?zhǔn)酱鎯Γ?BR>

復(fù)制代碼代碼如下:

/*二叉樹的鏈?zhǔn)酱鎯?/
typedef struct BiTNode
{
 TElemType data;
 BiTNode  *lchild,*rchild;
}
BiTNode, *BiTree;

這里的TElemType的類型如下，這里我使用了int型的定義：

復(fù)制代碼代碼如下:

#define INT_TYPE
#ifdef INT_TYPE
typedef int TElemType;
#elif defined FLOAT_TYPE
typedef float TElemType
#elif defined STRING_TYPE
typedef char  *TElemType
#endif

二叉樹的創(chuàng)建：這里需要進行遞歸創(chuàng)建，如下

復(fù)制代碼代碼如下:

int CreateBiTree(BiTree &T)
{
int nData;

printf("Please Enter BiTree Node data:\n");
scanf_s("%d", &nData);

if (nData == 0)
{
  T = NULL;
  return OK;
}
else if (nData > 0 && nData < 100)
{
  T = (BiTNode*)malloc(sizeof(BiTNode));
  if (!T)
  {
   return BTOVERFLOW;
  }
  T->data = nData;
  CreateBiTree(T->lchild);
  CreateBiTree(T->rchild);
  return OK;
}
#ifdef _DEBUG
printf("Enter data Error！\n");
#endif // _DEBUG

return ERROR;
}

這里我對數(shù)據(jù)進行了限制，便于進行測試，這里只接受0~100的數(shù)據(jù)，如果是0表明當(dāng)前沒有孩子的節(jié)點（左孩子或者右孩子），如果存在就創(chuàng)建節(jié)點，填充數(shù)據(jù)
遍歷二叉樹：創(chuàng)建后之后，我必須測試創(chuàng)建的二叉樹中的數(shù)據(jù)是否正確，這里采用的是先根遍歷，如下

復(fù)制代碼代碼如下:

/*遍歷二叉樹*/
int PreOrderTraverse(BiTree T, int (*VisitNode)(TElemType))
{
 if (T)
 {
  if (VisitNode(T->data))
  {
   if (PreOrderTraverse(T->lchild, VisitNode))
   {
    if (PreOrderTraverse(T->rchild, VisitNode))
    {
     return OK;
    }
   }
  }
  return ERROR;
 }
 return OK; //如果沒有子孩子，這時候應(yīng)該回溯,要查看右孩子必須為真
}

這里遍歷的時候采用了一個函數(shù)，注意傳遞的形參是函數(shù)指針，只是進行簡單的結(jié)點數(shù)據(jù)的輸出，如下：

復(fù)制代碼代碼如下:

int VisitNode(TElemType data)
{
#if defined(INT_TYPE) || defined(FLOAT_TYPE)
 printf("%d ", data);
#elif defined(STRING_TYPE)
 printf("%s ", data);
#endif
 return OK;
}

但是在遍歷的時候，為什么T為NULL的時候，返回還是OK（1）呢，這里主要是上面的遍歷函數(shù)的原因，因為這里必須是先遍歷左孩子且返回值為真，才能遍歷右孩子，所以不能返回ERROR（0），感覺返回值有點怪，修改如下

復(fù)制代碼代碼如下:

int PreOrderTraverseEx(BiTree T, int (*VisitNode)(TElemType))
{
 if (T)
 {
  if (VisitNode(T->data))
  {
   PreOrderTraverse(T->lchild, VisitNode);
   PreOrderTraverse(T->rchild, VisitNode);
   return OK;
  }
 }
 return ERROR; //如果沒有子孩子，這時候應(yīng)該回溯
}

這樣看著就舒服多了，其實可以不使用任何返回值，主要遍歷完左右子樹不用做其他任何事情，如果還有其他，就不能沒有返回值，這里return OK其實要不要也無所謂，因為我根本沒有進行判斷
測試用例：如下

復(fù)制代碼代碼如下:

 BiTree T;
 if (CreateBiTree(T))
 {
  PreOrderTraverseEx(T, VisitNode);
  printf("\n");
 }

這里對測試的數(shù)據(jù)輸入其實有一定的要求，假設(shè)根為12 孩子結(jié)點為 34 78，這里應(yīng)該這樣輸入數(shù)據(jù) 12 34 0 0 78 0 0，只有這樣才能正常退出，如下測試結(jié)果：
Please Enter BiTree Node data:
12
Please Enter BiTree Node data:
34
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
78
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
12 34 78

從前面我可以看到這里采用的其實都是遞歸算法，我們都知道遞歸最大之弊病就是在每次下潛下一層的時候，一定要保存當(dāng)前所在層次的數(shù)據(jù)，具體哪些數(shù)據(jù)其實是由操作系統(tǒng)OS來進行管理的，但是像每次的形參T一定會入棧，便于在層次退出返回上一層的時候使用，所以這里就可以采用非遞歸的方式的來進行修改算法：如何做呢？

請參考二叉樹先序遍歷的非遞歸算法

您可能感興趣的文章: