二叉樹先根（先序）遍歷的改良。本站提示廣大學習愛好者：（二叉樹先根（先序）遍歷的改良）文章只能為提供參考，不一定能成為您想要的結果。以下是二叉樹先根（先序）遍歷的改良正文
二叉樹的特色：每一個結點的度最年夜不克不及跨越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:
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
早年面我可以看到這裡采取的其實都是遞歸算法，我們都曉得遞歸最年夜之弊端就是在每次下潛下一層的時刻，必定要保留以後地點條理的數據，詳細哪些數據實際上是由操作體系OS來停止治理的，然則像每次的形參T必定會入棧，便於在條理加入前往上一層的時刻應用，所以這裡便可以采取非遞歸的方法的來停止修正算法：若何做呢？
請參考二叉樹先序遍歷的非遞歸算法
