线索二叉树的先序、中序、后序

线索二叉树的先序、中序、后序

/*
	Name: 线索二叉树 
	Copyright: 
	Author: lkm 
	Date: 30/09/21 14:50
	Description: 
*/

#include<stdio.h> 
#include<malloc.h>
typedef struct node{
	char data;	//数据元素 
	struct node *lchild,*rchild;	//左、右孩子指针 
	int ltag,rtag;	//左、右线索标志 
}BiTreeNode,*BiTree;
//输入abc###def###h##
void CreateBiTree(BiTree &T){
	char c;
	BiTree pre=NULL;
	scanf("%c",&c);
	if(c=='#')
	{
		T=NULL;
	}
	else{
		T=(BiTree)malloc(sizeof(BiTreeNode)); 
		T->data=c;
		T->lchild=T->rchild=NULL;
		T->ltag=T->rtag=0;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
}
//先序二叉树 NLR
void PreOrder(BiTree T){
	BiTree pre;
	if(T){				
		pre=(BiTree)malloc(sizeof(BiTreeNode));		
		if(T->lchild==NULL){
			T->lchild=pre;
			T->ltag=1;
		}
		if(pre!=NULL&&pre->rchild==NULL){
			pre->rchild=T;
			pre->rtag=1;
		}
		pre=T;
		printf("%c",T->data);//访问根结点
		if(T->ltag==0) {
			PreOrder(T->lchild);//线索化左子树
		}
		if(T->rtag==0){
			PreOrder(T->rchild);//线索化右子树 
		}	
	}
}
//中序二叉树 LNR
void InOrder (BiTree T){
	BiTree pre;
	if(T){	
		if(T->rtag==0){
			PreOrder(T->lchild);//线索化左子树 
		}		
		pre=(BiTree)malloc(sizeof(BiTreeNode));		
		if(T->lchild==NULL){
			T->lchild=pre;
			T->ltag=1;
		}
		if(pre!=NULL&&pre->rchild==NULL){
			pre->rchild=T;
			pre->rtag=1;
		}		
		pre=T;
		printf("%c",T->data);//访问根结点	
		if(T->rtag==0){
			PreOrder(T->rchild);//线索化右子树 
		}	 	
	}
}
//后序二叉树 LRN
void PostOrder(BiTree T) {
BiTree pre;
	if(T){	
		if(T->rtag==0){
			PreOrder(T->lchild);//线索化左子树 
		}
		if(T->rtag==0){
			PreOrder(T->rchild);//线索化右子树 
		}		
		pre=(BiTree)malloc(sizeof(BiTreeNode));		
		if(T->lchild==NULL){
			T->lchild=pre;
			T->ltag=1;
		}
		if(pre!=NULL&&pre->rchild==NULL){
			pre->rchild=T;
			pre->rtag=1;
		}		
		pre=T;		
		printf("%c",T->data);//访问根结点	
	}
}
int main(){
	BiTree T;
	CreateBiTree(T);
	printf("先序线索二叉树："); 
	PreOrder(T);
	printf("\n");
	printf("中序线索二叉树：");
	InOrder(T);
	printf("\n");
	printf("后序线索二叉树：");
	PostOrder(T);
	return 0;
}