随笔 - 51, 文章 - 1, 评论 - 41, 引用 - 0
数据加载中……

两个树结构的程序

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

posted on 2008-03-31 11:59 lemene 阅读(288) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理