本文共 1536 字,大约阅读时间需要 5 分钟。
#include#include #include #define OK 1#define ERROR 0#define OVERFLOW -2typedef 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;}
转载地址:http://sqmbn.baihongyu.com/