根据先中序序列或后中序序列确定二叉树
/*Name: 根据先中序序列或后中序序列确定二叉树
Copyright:
Author: 巧若拙
Date: 03-10-14 11:25
Description:
根据先中序序列或后中序序列确定二叉树，各种顺序遍历二叉树检查结果。
根据先中序序列生成二叉树：从先序序列中找到二叉树（或者子树）的根结点，然后在中序序列找到该根结点，
根结点将中序序列分成左右两部分，左边为左子树，右边为右子树。
根据中序序列确定左子树的长度，确定左子树中最右下结点在先序序列中的位置，
从而可以确定左右子树在先中序序列中的范围，然后递归的生成左右子树。
根据后中序序列生成二叉树：从后序序列中找到二叉树（或者子树）的根结点，然后在中序序列找到该根结点，
根结点将中序序列分成左右两部分，左边为左子树，右边为右子树。
根据中序序列确定左子树的长度，确定左子树中最右下根结点在后序序列中的位置，
从而可以确定左右子树在后中序序列中的范围，然后递归的生成左右子树。
*/
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#include<time.h>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define Link 0 //Link:指针
#define Thread 1 //Thread:线索
typedef char ElemType;
typedef int Status; //函数类型，其值是函数结果状态代码，如OK等
typedef struct BiTreeNode{
ElemType data;
struct BiTreeNode *lchild, *rchild;//左，右孩子指针
} BiTreeNode, *BiTree;
void PreOrderPrint(BiTree p); //先序遍历输出结点（递归）
void InOrderPrint(BiTree p); //中序遍历输出结点（递归）
void PostOrderPrint(BiTree p); //后序遍历输出结点（递归）
BiTree BiTreeByPreInd(ElemType pre[], ElemType ind[], int preLeft, int preRight, int indLeft, int indRight);//根据先序和中序序列生成一棵二叉树
BiTree BiTreeByPostInd(ElemType post[], ElemType ind[], int postLeft, int postRight, int indLeft, int indRight);//根据后序和中序序列生成一棵二叉树
int main(void)
{
ElemType ind[MAXSIZE] = "DBEAFCG";
ElemType pre[MAXSIZE] = "ABDECFG";
ElemType post[MAXSIZE] = "DEBFGCA";
BiTree bt1, bt2;
puts("根据先序和中序序列生成一棵二叉树:");
bt1 = BiTreeByPreInd(pre, ind, 0, strlen(pre)-1, 0, strlen(ind)-1);//根据先序和中序序列生成一棵二叉树
printf("先序：%s", pre);
printf("\n先序：");
PreOrderPrint(bt1); //先序遍历输出结点（递归）
printf("\n中序：%s", ind);
printf("\n中序：");
InOrderPrint(bt1); //中序遍历输出结点（递归）
printf("\n后序：%s", post);
printf("\n后序：");
PostOrderPrint(bt1); //后序遍历输出结点（递归）
puts("\n\n根据后序和中序序列生成一棵二叉树:");
bt2 = BiTreeByPostInd(post, ind, 0, strlen(post)-1, 0, strlen(ind)-1);//根据先序和中序序列生成一棵二叉树
printf("先序：%s", pre);
printf("\n先序：");
PreOrderPrint(bt2); //先序遍历输出结点（递归）
printf("\n中序：%s", ind);
printf("\n中序：");
InOrderPrint(bt2); //中序遍历输出结点（递归）
printf("\n后序：%s", post);
printf("\n后序：");
PostOrderPrint(bt2); //后序遍历输出结点（递归）
system("PAUSE");
return 0;
}
BiTree BiTreeByPreInd(ElemType pre[], ElemType ind[], int preLeft, int preRight, int indLeft, int indRight)//根据先序和中序序列生成一棵二叉树
{
BiTree head = NULL;
int root, right;
if (preLeft <= preRight)
{
head = (BiTree)malloc(sizeof(BiTreeNode));
if (!head)
{
printf("Out of space!");
exit (1);
}
head->data = pre[preLeft];
root = indLeft;
while (ind[root] != pre[preLeft]) //在中序序列中查找根结点
root++;
right = preLeft + root - indLeft; //right为左子树中最右下结点在前序序列中的位置
head->lchild = BiTreeByPreInd(pre, ind, preLeft+1, right, indLeft, root-1);//生成左子树
head->rchild = BiTreeByPreInd(pre, ind, right+1, preRight, root+1, indRight);//生成右子树
}
return head;
}
BiTree BiTreeByPostInd(ElemType post[], ElemType ind[], int postLeft, int postRight, int indLeft, int indRight)//根据后序和中序序列生成一棵二叉树
{
BiTree head = NULL;
int root, left;
if (postLeft <= postRight)
{
head = (BiTree)malloc(sizeof(BiTreeNode));
if (!head)
{
printf("Out of space!");
exit (1);
}
head->data = post[postRight];
root = indLeft;
while (ind[root] != post[postRight]) //在中序序列中查找根结点
root++;
left = postLeft + root - indLeft - 1; //left为左子树中根结点在后序序列中的位置
head->lchild = BiTreeByPostInd(post, ind, postLeft, left, indLeft, root-1); //生成左子树
head->rchild = BiTreeByPostInd(post, ind, left+1, postRight-1, root+1, indRight);//生成右子树
}
return head;
}
void PreOrderPrint(BiTree p) //先序遍历输出结点（递归）
{
if (p != NULL)
{
printf("%c ", p->data);//输出该结点
PreOrderPrint(p->lchild); //遍历左子树
PreOrderPrint(p->rchild); //遍历右子树
}
}
void InOrderPrint(BiTree p) //中序遍历输出结点（递归）
{
if (p != NULL)
{
InOrderPrint(p->lchild); //遍历左子树
printf("%c ", p->data);//输出该结点
InOrderPrint(p->rchild); //遍历右子树
}
}
void PostOrderPrint(BiTree p) //后序遍历输出结点（递归）
{
if (p != NULL)
{
PostOrderPrint(p->lchild); //遍历左子树
PostOrderPrint(p->rchild); //遍历右子树
printf("%c ", p->data);//输出该结点
}
}
