数据结构前序中序求二叉树

悠悠 2022-09-19 01:53 131阅读 0赞

#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;
    }