由前序和中序遍历结果构建二叉树
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define N    50

struct Node    /* 树结点类型 */
{
    char         info;    /* 数据域 */
    struct Node*    parent;    /* 父结点 */
    struct Node*     lchild;    /* 左孩子结点 */
    struct Node*    rchild;    /* 右孩子结点 */
};
typedef struct Node* PNode;


struct Stack        /* 栈结点类型 */
{
    char*    pre;
    char*    in;
    int    n;
    PNode    parent;
};


int myIndex(char seq[],char c)    /* 查c在seq中的位置，不存在则返回-1 */
{
    int i;
    for (i = 0;seq[i] != '\0';i++)
    {
        if (seq[i] == c)
        {
            return i;
        }
    }
    return -1;
}


/* 创建一棵树，其中pre是前序遍历的结果，in是中序遍历的结果，n是结点总数,parent是所建的树的父结点 */
/* 如果结点数大于0，则创建一个结点并返回指向这个结点的指针，如果等于0，则返回NULL */
/* 具体算法请参照二叉树的前序遍历的非递归算法 */
PNode creattree(char pre[],char in[],int n,PNode parent)
{
    PNode p;
    struct Stack s[N],t;    /* 用来存储参数的栈 */
    int top = 0;        /* 栈顶指针，值为0的时候，栈为空 */
    int i;
    PNode head = NULL;    /* 用来返回的根结点 */
    int done = 0;    /* 标记树有没有完全建立起来，初始化为假 */
   
    while (!done)    /* 如果树没有建立起来，则要继续进入建立 */
    {
       
        while (n != 0)        /* n的值不为0，也就是pre和in中都至少还有一个元素的时候 */
        {
            i = myIndex(in,pre[0]);        /* 确定pre的第一个元素，就是父结点在中序遍历结果中的位置 */
            p = (PNode)(malloc(sizeof(struct Node)));    /* 建立一个结点 */
            p->info = pre[0];
           
            p->parent = parent;
            p->lchild = NULL;
            p->rchild = NULL;
            if (parent != NULL)    /* 当结点的父结点不是空值时，就把parent的左孩子值改成p */
            {
                parent->lchild = p;
            }
            else        /* 如果为空时 */
            {
                head = p;    /* 那么这个结点就是根结点 */
            }
           
            if (n - i - 1 != 0)    /* 只有前序遍历和中序遍历结果都有元素时，才入栈 */
            {
               
                t.pre = pre + i + 1;    /* 右子树的前序遍历的结果 */
                t.in  = in  + i + 1;    /* 右子树的中序遍历的结果 */
                t.n   = n   - i - 1;    /* 右子树的结点个数 */
                t.parent = p;        /* 右子树的父结点就是当前结点 */
                s[++top] = t;        /* 入栈 */
            }
           
           
            pre = pre + 1;        /* 右子树的前序遍历的结果，中序遍历的结果不变 */
            n = i;            /* 只是结点个数减少而已 */
            parent = p;        /* 右子树的父结点就是当前结点 */
        }
       
       
        if (top != 0)        /* 当栈不空时，也就是至少还有一个子树的右子树没有建立 */
        {
            t = s[top--];    /* 出栈 */
            pre = t.pre;
            in  = t.in;
            n   = t.n;
            parent = t.parent;
           
           
           
            i = myIndex(in,pre[0]);
            p = (PNode)(malloc(sizeof(struct Node)));
            p->info = pre[0];
            p->parent = parent;
            p->lchild = NULL;
            p->rchild = NULL;

            if (parent != NULL)
            {
                parent->rchild = p;    /* 注意，现在是在建立右子树 */
            }
            else
            {
                head = p;
            }
           
            if (n - i - 1 != 0)
            {
               
                t.pre = pre + i + 1;
                t.in  = in  + i + 1;
                t.n   = n   - i - 1;
                t.parent = p;
                s[++top] = t;
            }
           
            pre = pre + 1;
            n = i;
            parent = p;
        }
        else        /* 栈空了，也就是建立起了这棵树 */
先序中序后序遍历二叉树        {
            done = 1;
        }
    }
    return head;
}


/* 前序遍历 */
void pre_order(PNode root)
{
    if (root != NULL)
    {
        printf("%c ",root->info);
        pre_order(root->lchild);
        pre_order(root->rchild);
    }
}

/* 中序遍历 */
void in_order(PNode root)
{
    if (root != NULL)
    {
        in_order(root->lchild);
        printf("%c ",root->info);
        in_order(root->rchild);
    }
}

/* 后序遍历 */
void post_order(PNode root)
{
    if (root != NULL)
    {
        post_order(root->lchild);
        post_order(root->rchild);
        printf("%c ",root->info);
    }
}

int main(void)
{
    PNode root;
    char pre[N];
    char in[N];
   
    printf("请输入前序遍历结果：");
    scanf("%s",pre);
    printf("请输入中序遍历结果：");
    scanf("%s",in);
       
    /* 建树 */
    root = creattree(pre,in,strlen(pre),NULL);
   
    printf("\n前序遍历结果：\n");
    pre_order(root);
    printf("\n中序遍历结果：\n");
    in_order(root);
    printf("\n后序遍历结果：\n");
    post_order(root);
    printf("\n");
    return 0;
}

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