数据结构 前序中序求二叉树
【摘要】 #include <stdio.h>#include <stdlib.h>#include <string.h> #define OK 1#define ERROR 0#define OVERFLOW -2 typedef char TElemType; typedef struct BiNode{ TElemType data; stru...
-
#include <stdio.h>
-
#include <stdlib.h>
-
#include <string.h>
-
-
#define OK 1
-
#define ERROR 0
-
#define OVERFLOW -2
-
-
typedef char TElemType;
-
-
typedef struct BiNode
-
{
-
TElemType data;
-
struct BiNode *lchild,*rchild;
-
}BiNode, *BiTree;
-
-
void PostOrderTraverse(const char *preStart, const char *preEnd, const char *inStart, const char *inEnd,BiTree &T)
-
{
-
char root = *preStart;
-
int len = preEnd - preStart,i = 0;
-
T = (BiTree)malloc(sizeof(BiNode));
-
T->data = root;
-
for(;*(inStart+i) != root && i<=len; i++); //查找根结点在中序的位置
-
if (i != 0)
-
{//如果不是第一个，说明其含有左子树
-
PostOrderTraverse(preStart+1, preStart+i, inStart, inStart+i-1,T->lchild);
-
}
-
else
-
{
-
T->lchild = NULL;
-
}
-
if (i != len)
-
{//如果不是最后一个，说明其含有右子树
-
PostOrderTraverse(preStart+i+1, preEnd, inStart+i+1, inEnd,T->rchild);
-
}
-
else
-
{
-
T->rchild = NULL;
-
}
-
}
-
-
void PreOrderTraverse(BiTree T)
-
{//先序遍历的递归调用
-
if (T == NULL)
-
{
-
return;
-
}
-
printf("%c",T->data);//访问根结点
-
PreOrderTraverse(T->lchild);//访问左子树
-
PreOrderTraverse(T->rchild);//访问右子树
-
}
-
-
void InOrderTraverse(BiTree T)
-
{
-
if (T == NULL)
-
{
-
return;
-
}
-
InOrderTraverse(T->lchild);//访问左子树
-
printf("%c",T->data);//访问根结点
-
InOrderTraverse(T->rchild);//访问右子树
-
}
-
-
void PostOrderTraverse(BiTree T)
-
{
-
if (T == NULL)
-
{
-
return;
-
}
-
PostOrderTraverse(T->lchild);//访问左子树
-
PostOrderTraverse(T->rchild);//访问右子树
-
printf("%c",T->data);//访问根结点
-
}
-
-
int main()
-
{
-
char *s1 = "ABCDEFG";
-
char *s2 = "CBEDAFG";
-
BiTree T = NULL;
-
PostOrderTraverse(s1,s1+strlen(s1)-1, s2,s2+strlen(s2)-1,T);
-
PreOrderTraverse(T);
-
printf("\n");
-
InOrderTraverse(T);
-
printf("\n");
-
PostOrderTraverse(T);
-
printf("\n");
-
return 0;
-
}
文章来源: blog.csdn.net，作者：悦来客栈的老板，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/qq523176585/article/details/17268219
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）