快捷導(dǎo)航

二叉樹(shù)先根（先序）遍歷的改進(jìn)

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

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

二叉樹(shù)的特點(diǎn)：每個(gè)結(jié)點(diǎn)的度最大不能超過(guò)2，并且左右子樹(shù)不能顛倒

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

順序存儲(chǔ)：

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

/*二叉樹(shù)的順序存儲(chǔ)*/
#define  MAX_TREE_SIZE 100
typedef  TElemType  SqBiTree[MAX_TREE_SIZE];

鏈?zhǔn)酱鎯?chǔ)：

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

/*二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)*/
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

二叉樹(shù)的創(chuàng)建：這里需要進(jìn)行遞歸創(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;
}

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

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

/*遍歷二叉樹(shù)*/
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; //如果沒(méi)有子孩子，這時(shí)候應(yīng)該回溯,要查看右孩子必須為真
}

這里遍歷的時(shí)候采用了一個(gè)函數(shù)，注意傳遞的形參是函數(shù)指針，只是進(jìn)行簡(jiǎn)單的結(jié)點(diǎn)數(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;
}

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

復(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; //如果沒(méi)有子孩子，這時(shí)候應(yīng)該回溯
}

這樣看著就舒服多了，其實(shí)可以不使用任何返回值，主要遍歷完左右子樹(shù)不用做其他任何事情，如果還有其他，就不能沒(méi)有返回值，這里return OK其實(shí)要不要也無(wú)所謂，因?yàn)槲腋緵](méi)有進(jìn)行判斷
測(cè)試用例：如下

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

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

這里對(duì)測(cè)試的數(shù)據(jù)輸入其實(shí)有一定的要求，假設(shè)根為12 孩子結(jié)點(diǎn)為 34 78，這里應(yīng)該這樣輸入數(shù)據(jù) 12 34 0 0 78 0 0，只有這樣才能正常退出，如下測(cè)試結(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

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

請(qǐng)參考二叉樹(shù)先序遍歷的非遞歸算法

您可能感興趣的文章: