|
|
前幾日從朋友得到幾個關于樹結構的題目，頗為有趣。 第一道題目：一個二叉樹，有三種遍歷，前序遍歷，中序遍歷，后序遍歷。已知兩種遍歷的順序，求出第三種順序。如前序abc，中序bac，則后序則是bca。當然知道前序和后序不一定能確定中序的順序。如前序ab，后序則是ba，葉結點b可能是左葉，也可能是右葉。就有了第二道題目 第二道題目：如果是一個N叉樹，如果知道前序遍歷，后序遍歷，則這棵樹可能有這種可能的形式。 和樹有關的算法一般可以用遞歸算法。因為子樹也是一棵樹，和遞歸思想吻合。這兩個程序用到的算法就是遞歸，關鍵點就是找出子樹的起始位置。程序如下：
 /* 得到二叉樹的后序輸出 */
int GetPostOrder(int n, const int* preorder, const int* inorder, int* postorder)
{
if (n == 1)
{
postorder[0] = preorder[0];
}
else if (n > 1)
{
int i;
for (i=0; i<n; i++)
{
if (inorder[i] == preorder[0])
break;
}
if (i == n) return -1;
GetPostOrder(i, preorder+1, inorder, postorder);
GetPostOrder(n-1-i, preorder+1+i, inorder+i+1, postorder+i);
postorder[n-1] = preorder[0];
}
return 0;
}
/* 得到二叉樹的中序輸出，由于不唯一，所以子樹左優先 */
int GetInOrder(int n, const int* preorder, int* inorder, const int* postorder)
{
if (n == 1)
{
inorder[0] = preorder[0];
}
else if (n > 1)
{
int i;
for (i=0; i<n; i++)
{
if (preorder[1] == postorder[i])
break;
}
if (i == n) return -1;
i++;
GetInOrder(i, preorder+1, inorder, postorder);
inorder[i] = preorder[0];
GetInOrder(n-1-i, preorder+1+i, inorder+i+1, postorder+i);
}
return 0;
}
/* 得到二叉樹的前序輸出 */
int GetPreOrder(int n, int* preorder, const int* inorder, const int* postorder)
{
if (n == 1)
{
preorder[0] = postorder[n-1];
}
else if (n > 1)
{
int i;
for (i=0; i<n; i++)
{
if (inorder[i] == postorder[n-1])
break;
}
if (i == n) return -1;
preorder[0] = postorder[n-1];
GetPreOrder(i, preorder+1, inorder, postorder);
GetPreOrder(n-1-i, preorder+1+i, inorder+i+1, postorder+i);
}
return 0;
}
/* 得到N叉樹可能的子樹結構的數目 */
int PsbInOrder(int tsize, int n, const int* preorder, const int* postorder)
{
int ret = 1;
if (n > 1)
{
int i, s, size;
for (i=0,s=1,size=0; i<n-1; i++)
{
if (preorder[s] == postorder[i])
{
ret *= PsbInOrder(tsize, i-s+2, preorder+s, postorder+s-1);
size++;
s = i+2;
}
}
for (i=0; i<size; i++)
{
ret = (tsize-i) * ret / (i+1);
}
}
return ret;
}
int main(void)
{
/*
* ABFEGCDHN （前序）
* FBEGAHDNC （中序）
* FGEBHNDCA （后序）
*/
int i;
int preorder[] = {'A','B','F','E','G','C','D','H','N'};
int inorder[] = {'F','B','E','G','A','H','D','N','C'};
int postorder[] = {'F','G','E','B','H','N','D','C','A'};
int n = sizeof(preorder)/sizeof(int);
/*
* abejkcfghid （前序）
* jkebfghicda （后序）
*/
int p1[] = {'a','b','e','j','k','c','f','g','h','i','d'};
int p2[] = {'j','k','e','b','f','g','h','i','c','d','a'};
int m = sizeof(p1)/sizeof(int);
GetPostOrder(n, preorder, inorder, postorder);
for (i=0; i<sizeof(preorder)/sizeof(int); i++)
printf("%c", (char)postorder[i]);
i = PsbInOrder(13, m, p1, p2);
printf("\n%d\n", i);
return 0;
}
|