|
|
前几日从朋友得到几个关于树结构的题目，颇为有趣。 第一道题目：一个二叉树，有三种遍历，前序遍历，中序遍历，后序遍历。已知两种遍历的顺序，求出第三种顺序。如前序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;
}
|