#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct Node    /* 树结点类型 */
{
    int        info;    /* 数据域 */
    struct Node*    parent;    /* 父结点 */
    struct Node*    lchild;    /* 左孩子结点 */
    struct Node*    rchild;    /* 右孩子结点 */
}PNode;
struct Stack        /* 栈结点类型 */
{
    int*    pre;
    int*    in;
    int    n;
    PNode    parent;
};
PNode *Init_tree(int *pre,int *in,int n);//声明
/* 前序遍历 */
void pre_order(PNode *root)
{
    if (root != NULL)
    {
        printf("%d ",root->info);
        pre_order(root->lchild);
        pre_order(root->rchild);
    }
}
/* 中序遍历 */
void in_order(PNode *root)
{
    if (root != NULL)
    {
        in_order(root->lchild);
        printf("%d ",root->info);
        in_order(root->rchild);
    }
}
/* 后序遍历 */
void post_order(PNode *root)
{
    if (root != NULL)
    {
        post_order(root->lchild);
        post_order(root->rchild);
        printf("%d ",root->info);
    }
}先序中序后序遍历二叉树
int main(void)
{
    PNode *root;
    int pre[50]={1,2,4,8,10,5,9,3,6,7};
    int in[ 50]={8,10,4,2,5,9,1,6,3,7} ;
    /* 建树 */
    root = Init_tree(pre,in,10);
    printf("\n前序遍历结果：\n");
    pre_order(root);
    printf("\n中序遍历结果：\n");
    in_order(root);
    printf("\n后序遍历结果：\n");
    post_order(root);
    printf("\n");
    return 0;
}
PNode *Init_tree(int *pre,int *in,int n)
{
    PNode *root;
    int *p,*q,i,j,m;
if(n<=0)
return (NULL);
root=(PNode*)malloc(sizeof(PNode));
root->info=pre[0];
root->lchild=root->rchild=NULL;
i=0;
while(i<n)
{
if(pre[0]==in[i])
break;
++i;
}
p=pre+1;
q=in;
root->lchild=Init_tree(p,q,i);
p=pre+i+1;
q=in+i+1;
root->rchild=Init_tree(p,q,n-i-1);
return(root);
}
树的形状
                1
              /    \
            2      3
            / \    /  \
          4  5  6    7
          /    \
        8      9                   
          \                     
          10
这种题一般有二种形式，共同点是都已知中序序列。如果没有中序序列，是无法唯一确定一棵树的，证明略。
一、已知二叉树的前序序列和中序序列，求解树。
1、确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。
2、求解树的子树。出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。
3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。
二、已知二叉树的后序序列和中序序列，求解树。
1、确定树的根。树根是当前树中所有元素在后序遍历中最后出现的元素。
2、求解树的子树。出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右
边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。
3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。
举例说明：根据已知求解二叉树
中序序列 HLDBEKAFCG
后序序列 LHDKEBFGCA
1、在后序序列LHDKEBFGCA中最后出现的元素为A，HLDBEK|A|FCG
2、在后序序列LHDKEB中最后出现的元素为B，HLD|B|EK|A|FCG
3、在后序序列LHD中最后出现的元素为D，HL|D|B|EK|A|FCG
4、在后序序列LH中最后出现的元素为H，H|L|D|B|EK|A|FCG
5、在后序序列KE中最后出现的元素为E，H|L|D|B|E|K|A|FCG
5、在后序序列FGC中最后出现的元素为C，H|L|D|B|E|K|A|F|C|G
6、所有元素都已经定位，二叉树求解完成。
                A
              /    \
            B      C
            / \    /  \
          D  E    F  G
          /    \
        H      K                   
          \                       
          L                     
代码的运行结果
         

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。