现在的位置: 首页 > 综合 > 正文

递归 栈 线索 中序遍历二叉树

2013年10月06日 ⁄ 综合 ⁄ 共 4454字 ⁄ 字号 评论关闭
//哎。。发现 写一段代码 需要的时间都要好久啊 
#include<stdio.h>
#include<stdlib.h>

#define ERROR 0
#define OK 1

typedef int Status;
typedef struct BiTree{
	int id;     //二叉树节点的标识符 用来查找用的
	int data;
	int LTag,RTag;  //标志  左子树  右子树  0代表线索 1代表指针
    struct BiTree *LChild;  //left child
    struct BiTree *RChild;  //right child
} BiTree,*PBiTree;

Status InitBiTree(PBiTree *PBT,int data)
{
	if(!((*PBT)=(PBiTree)malloc(sizeof(BiTree)))) return ERROR;
	(*PBT)->id=1; (*PBT)->data=data; (*PBT)->LChild=NULL; (*PBT)->RChild=NULL;   //初始化 
	return OK;
}

Status GetBiTreeNodeById(PBiTree BTO,PBiTree *PBTR,int id)  //receive
{
	int stat1=ERROR,stat2=ERROR;
	if(BTO->id==id)
	{ *PBTR=BTO; return OK;}   //注意:BTR=BTO  这是没有意义的事情 如果用 *BTR=*BTO; 报告内存不可写
	else{
		if(BTO->LChild)
 		{stat1=GetBiTreeNodeById(BTO->LChild,PBTR,id);}
 		
 		if(BTO->RChild)
 		{stat2=GetBiTreeNodeById(BTO->RChild,PBTR,id);}
 		
 		return stat1 || stat2;  //就算有一个有找到 也算成功 
	} 
	
}

Status InsertBiTree(PBiTree BT,int fid,char lr,int sid,int data)  
{//要被插入的树  该树下的节点id下插入  成为它的左孩子或者右孩子 l左 r右 插入者的id 数据   
//如果在该位置上已经存在 节点 则把原来的 替换
	PBiTree BTR,BTT;
	if(GetBiTreeNodeById(BT,&BTR,fid)) //找到父树 
	{
		switch(lr)
		{
			case 'l': //left
				if(BTR->LChild)
				{
					BTR->LChild->id=sid;
					BTR->LChild->data=data;
				}else{
					if(!(BTT=(PBiTree)malloc(sizeof(BiTree)))) return ERROR;
					BTR->LChild=BTT;
					BTT->id=sid;  BTT->data=data;
					BTT->LChild=NULL;  BTT->RChild=NULL;
				}
				break;
				
			case 'r': //right
				if(BTR->RChild)
				{
					BTR->RChild->id=sid;
					BTR->RChild->data=data;
				}else{
					if(!(BTT=(PBiTree)malloc(sizeof(BiTree)))) return ERROR;
					BTR->RChild=BTT;
					BTT->id=sid;  BTT->data=data;
					BTT->LChild=NULL;  BTT->RChild=NULL;
				}
				break;		
		}	
	}else{ return ERROR;}
	
	return OK;
}

Status PrintBiTree(const BiTree *PB)  //做好之后  做一下扩充  给它传一个 函数 来调用 打印 
{
	if(!PB) return ERROR;
	
	//printf(" id:%d data:%d  ",PB->id,PB->data);  //先序 从根节点起 先左完 再右 
	if(PB->LChild)
	{PrintBiTree(PB->LChild);}
	
	printf(" id:%d data:%d  ",PB->id,PB->data); 
	
	if(PB->RChild)
	{PrintBiTree(PB->RChild);}
//	printf(" id:%d data:%d  ",PB->id,PB->data); 
	
	return OK;
}

Status DestoryBiTree(BiTree *PB)
{
	if(PB->LChild)
	{DestoryBiTree(PB->LChild);}
	
	if(PB->RChild)
	{DestoryBiTree(PB->RChild);}
	
	free(PB);
	
	return OK;
}

//======================栈操作 
typedef struct StackNode{  //栈遍历 
	BiTree *TreeNode; 
	struct StackNode *next;
}NStack,*PStack;

Status InitStack(PStack *P)
{
	if(!((*P)=(PStack)malloc(sizeof(NStack)))) return ERROR;
	(*P)->TreeNode=NULL;
	(*P)->next=NULL;
	
	return OK;
}

Status Push(PStack S,BiTree *PB)
{
	PStack st;
	if(!((st)=(PStack)malloc(sizeof(NStack)))) return ERROR;
	st->TreeNode=PB;
	st->next=S->next;
	S->next=st;
	
	return OK;
}

Status Pop(PStack S,PStack *P)
{
	(*P)=S->next;
	if(*P)
	{S->next=(*P)->next;}
	
	return OK;
}

Status GetHead(PStack S,PStack *H)
{
	(*H)=S->next;
	
	return OK;
}

int StackEmpty(const PStack S)
{
	if(S->next==NULL)
		return 1;
	
	return 0;	
}

Status TraverseByStack(const BiTree *PB) //栈遍历  中序 遍历 
{
	PStack S=(PStack)malloc(sizeof(NStack));
	PStack H,St=S;
	InitStack(S);
	
	Push(S,PB);
	
	while(!StackEmpty(S))
	{
		while(GetHead(S,&H) && H->TreeNode)  //一路向左 
			{Push(S,H->TreeNode->LChild);}  
		
		Pop(S,&H);
		
		if(!StackEmpty(S))
		{
			free(H);  //释放Pop所带来的 残余 
			Pop(S,&H); //要Pop两次  因为 使它上上节点 指向它上节点的下节点 故抛弃上节点 
			Push(S,H->TreeNode->RChild);
			printf(" id:%d data:%d  ",H->TreeNode->id,H->TreeNode->data); //打印上节点 
		}

	}//关键 就是退两步 让它退的第二步栈的下一个节点  指向它退第一步的栈的树节点的右节点所构成的栈节点 
	
	free(St);
}
//=================== 栈操作 end

//===================线索二叉树
PBiTree pre; //前一个指针 
Status Threading(PBiTree B); 
Status ToThread(PBiTree B,PBiTree *P) // 进行线索化   中序 
{
	if(!((*P)=(PBiTree)malloc(sizeof(BiTree)))) return ERROR;  //头节点 
	
	(*P)->RChild=(*P);
	
	if(!B) { (*P)->LChild=(*P); } //树空 则另 (*P)的左子树 回指 
	else{
		(*P)->LChild=B;
		pre=(*P);  //pre是为前一个节点
		
		Threading(B);
		
		//把 头节点的右子树 指向二叉树 中序遍历 的最后一个节点 
		(*P)->RChild=pre;   //此时的 pre指向的是 树的最后一个节点 
		 pre->RChild=(*P);

	} 
	return OK;
}

Status Threading(PBiTree B) //中序 遍历  线索二叉 
{
	if(B->LChild)
	{
		B->LTag=1;
		Threading(B->LChild);// 一直走到左边的底部 
	}else{
		B->LTag=0; // 在左边的底部时 就为线索 
		B->LChild=pre;
	}
	
	if(! pre->RChild) //这一步 需要多看  在上面递归退出的时候 全局变量pre的值被改变 
	{
		pre->RTag=0;
		pre->RChild=B;
	}
	pre=B; //递归退出时 发挥功用 
	
	if(B->RChild)
	{	B->RTag=1; 
		Threading(B->RChild); //线索 右子树 
	}else{
		B->RTag=0;  //如果树就只有一个节点 的情况 
	}
	
	return OK;
}

Status TraverseByThread(const BiTree *PB) //线索二叉遍历  中序 
{
	BiTree *Pa,*Pb=NULL;
	Pa=PB->LChild;

	while(1) 
	{
		for(Pb=Pa;Pb->LTag;Pb=Pb->LChild);
		
		printf(" id:%d data:%d  ",Pb->id,Pb->data);
		
		if(! Pb->RTag)  //线索 
		{
			Pb=Pb->RChild; 
			if(Pb == PB) break; //回到 表头 则退出 
			printf(" id:%d data:%d  ",Pb->id,Pb->data);
		}

		Pa=Pb->RChild;
	}
	return OK;
}

int main()
{
	PBiTree PBT,PBA;
	InitBiTree(&PBT,11);
	
	InsertBiTree(PBT,1,'l',2,22);
	InsertBiTree(PBT,1,'r',3,23);
	
	InsertBiTree(PBT,2,'l',4,32);
	InsertBiTree(PBT,2,'r',5,33);
	
	InsertBiTree(PBT,3,'l',6,33);
	InsertBiTree(PBT,3,'r',7,34);
	
	InsertBiTree(PBT,4,'l',8,44);
	InsertBiTree(PBT,4,'r',9,45);
	
	InsertBiTree(PBT,5,'l',10,55);
	InsertBiTree(PBT,5,'r',11,56);
	
	
	printf("print by 递归:\n");	
	PrintBiTree(PBT);
	printf("\n\n");
	
	printf("print by Stack:\n");	
	TraverseByStack(PBT);	
	printf("\n\n");
	
	printf("print by Thread:\n");
	ToThread(PBT,&PBA);
	TraverseByThread(PBA);
	
	DestoryBiTree(PBT);

}

抱歉!评论已关闭.