二叉樹的特點：每個結點的度最大不能超過2，并且左右子樹不能颠倒
二叉樹的存儲結構：下面采用鍊式存儲進行闡述，堆排序算法（快速排序改進）采用的順序存儲結構的二叉樹，先看如下結構體的存儲方式
順序存儲：
/*二叉樹的順序存儲*/
#define MAX_TREE_SIZE 100
typedef TElemType SqBiTree[MAX_TREE_SIZE];
鍊式存儲：
/*二叉樹的鍊式存儲*/
typedef struct BiTNode
{
TElemType data;
BiTNode *lchild,*rchild;
}BiTNode, *BiTree;
這裡的TElemType的類型如下，這裡我使用了int型的定義：
#define INT_TYPE
#ifdef INT_TYPE
typedef int TElemType;
#elif defined FLOAT_TYPE
typedef float TElemType
#elif defined STRING_TYPE
typedef char *TElemType
#endif
二叉樹的建立：這裡需要進行遞歸建立，如下
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;
}
這裡我對資料進行了限制，便于進行測試，這裡隻接受0~100的資料，如果是0表明目前沒有孩子的節點（左孩子或者右孩子），如果存在就建立節點，填充資料
周遊二叉樹：建立後之後，我必須測試建立的二叉樹中的資料是否正确，這裡采用的是先根周遊，如下
/*周遊二叉樹*/
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; //如果沒有子孩子，這時候應該回溯,要檢視右孩子必須為真
}
這裡周遊的時候采用了一個函數，注意傳遞的形參是函數指針，隻是進行簡單的結點資料的輸出，如下：
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）呢，這裡主要是上面的周遊函數的原因，因為這裡必須是先周遊左孩子且傳回值為真，才能周遊右孩子，是以不能傳回ERROR（0），感覺傳回值有點怪，修改如下
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; //如果沒有子孩子，這時候應該回溯
}
這樣看着就舒服多了，其實可以不使用任何傳回值，主要周遊完左右子樹不用做其他任何事情，如果還有其他，就不能沒有傳回值，這裡return OK其實要不要也無所謂，因為我根本沒有進行判斷
測試用例：如下
BiTree T;
if (CreateBiTree(T))
{
PreOrderTraverseEx(T, VisitNode);
printf("\n");
}
這裡對測試的資料輸入其實有一定的要求，假設根為12 孩子結點為 34 78，這裡應該這樣輸入資料 12 34 0 0 78 0 0，隻有這樣才能正常退出，如下測試結果：
Please Enter BiTree Node data:
12
Please Enter BiTree Node data:
34
Please Enter BiTree Node data:
Please Enter BiTree Node data:
Please Enter BiTree Node data:
78
Please Enter BiTree Node data:
Please Enter BiTree Node data:
12 34 78
從前面我可以看到這裡采用的其實都是遞歸算法，我們都知道遞歸最大之弊病就是在每次下潛下一層的時候，一定要儲存目前所在層次的資料，具體哪些資料其實是由作業系統OS來進行管理的，但是像每次的形參T一定會入棧，便于在層次退出傳回上一層的時候使用，是以這裡就可以采用非遞歸的方式的來進行修改算法：如何做呢？請參考二叉樹先序周遊的非遞歸算法