在C++编译器下可直接运行
#include <stdio.h>
#include <malloc.h>
//算法思想:先读入根结点数据,并且创建根结点,在读入左子树数据并创建左子树
//之后再读入右子树数据并创建右子树,在根结点左右子树创建好之后,最终将根结点返回。
typedef char ElemType;
typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTNode *createBiTree()//该函数用来创建一棵树
{
BiTNode *T = NULL;
ElemType enter;
enter = getchar();//可能读入空格，这样就结束输入
if('@' != enter)
{
T = (BiTNode *)malloc(sizeof(BiTNode));
T->data = enter;
T->lchild = createBiTree();//结构体用点，结构体指针用箭头***********
T->rchild = createBiTree();
}
return T;
}
void preOrder(BiTree T)
{
if(T != NULL)
{
printf("%c ", T->data);
preOrder(T->lchild);
preOrder(T->rchild);
}
}
void midOrder(BiTree T)
{
if(T != NULL)
{
midOrder(T->lchild);
printf("%c ", T->data);
midOrder(T->rchild);
}
}
//給定二叉鏈表的先序遍歷和中序遍歷，構造一顆二叉鏈表表示一棵樹
BiTNode *createBiTree1(ElemType preOrderList[],int preStartIndex,int preEndIndex,
ElemType inOrderList[],int inStartIndex,int inEndIndex)
{
if(preStartIndex > preEndIndex)
{
return NULL;
}
BiTNode *t = (BiTNode *)malloc(sizeof(BiTNode));
t->data = preOrderList[preStartIndex];
int rootIndex;
for(rootIndex = inStartIndex;rootIndex <= inEndIndex;rootIndex++)//在中序序列中查找跟節點位置
{
if(t->data == inOrderList[rootIndex])
{
break;
}
}
int length = rootIndex - inStartIndex;
t->lchild = createBiTree1(preOrderList,preStartIndex + 1,preStartIndex + length,
inOrderList,inStartIndex,rootIndex - 1);
t->rchild = createBiTree1(preOrderList,preStartIndex + length + 1,preEndIndex,
inOrderList,rootIndex + 1,inEndIndex);
return t;
}
//层次遍历
//输入层次遍历序列和中序序列创建一棵二叉树
//算法思想：先层次遍历确定（子树）根结点，再到中序序列中确定根位置，分出左右子树数列。
//然后确定层次遍历对左右子树序列，构建左右子树，重复上述步骤，构建整棵二叉树。
#define MAX_SIZE 100
BiTNode *createBiTree2(ElemType levelOrderList[],int levelStartIndex,int levelEndIndex,
ElemType inOrderList[],int inStartIndex,int inEndIndex)
{
if(levelStartIndex > levelEndIndex)
{
return NULL;
}
BiTNode *t = (BiTNode *)malloc(sizeof(BiTNode));
t->data = levelOrderList[levelStartIndex];
int rootIndex;//在中序遍历序列中确定子树根结点位置
for(rootIndex = inStartIndex;rootIndex < inEndIndex;rootIndex++)
{
if(inOrderList[rootIndex] == t->data)
{
break;
}
}
ElemType lftLeverOrderList[MAX_SIZE];
int lftLeverLength = 0;
for(int j = levelStartIndex + 1;j <= levelEndIndex;j++)//找出左子树的层次遍历序列
{
for(int i = inStartIndex;i <= rootIndex - 1;i++)
{
if(inOrderList[i] == levelOrderList[j])
{
lftLeverOrderList[lftLeverLength++] = levelOrderList[j];
}
}
}
ElemType rgtLeverOrderList[MAX_SIZE];
int rgtLeverLength = 0;
for(int j = levelStartIndex + 1;j <= levelEndIndex;j++)//找出左子树的层次遍历序列
{
for(int i = rootIndex + 1;i <= inEndIndex;i++)
{
if(inOrderList[i] == levelOrderList[j])
{
rgtLeverOrderList[rgtLeverLength++] = levelOrderList[j];
}
}
}
t->lchild = createBiTree2(lftLeverOrderList,0,lftLeverLength - 1,
inOrderList,inStartIndex,rootIndex - 1);
t->rchild = createBiTree2(rgtLeverOrderList,0,rgtLeverLength - 1,
inOrderList,rootIndex + 1,inEndIndex);
return t;
}
////层次遍历
//void levelTravelBiTree(BiTree T)
//{
// queue q;
// initailQueue(q);
// enQueue
//}
int main()
{
// BiTree T = createBiTree();
// preOrder(T);
// midOrder(T);
// char preOrderList[] = {'A','B','D','E','C','F','G'};
// int preOrderListLength = 7;
char leverOrderList[] = {'A','B','C','D','E','F','G'};
int leverOrderListLength = 7;
char inOrderList[] = {'D','B','E','A','F','C','G'};
int inOrderListLength = 7;
BiTree t = createBiTree2(leverOrderList,0,leverOrderListLength - 1,inOrderList,0,inOrderListLength - 1);
preOrder(t);
printf("\n");
midOrder(t);
return 0;
}
二叉树总结——BiTree的相关教程结束。
