哈夫曼树打印

大家好，欢迎来到IT知识分享网。

提供先序遍历序列，以*代替空节点，构建哈夫曼树

代码

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100

#define Pstart 62

typedef struct node  
{
	int    key;
	int    data;
	struct node *lchild,*rchild;
}BTNode;

typedef struct pnode        
{
	int key;                   
	int data;                  
	struct pnode *lchild,      
		         *rchlid,      
				 *parent;      
	int lrflag,space,level;                  
}PBTNode;


BTNode* CreateBTNode(char *s)
{
	char ch;
	BTNode *p=NULL,	*b=NULL,*ps[MaxSize];
	int top=-1,tag=-1;
	ch=*s;
	while(ch)
	{
		switch(ch)
		{
		case '(':ps[++top]=p;tag=1;break;
		case ',':tag=2;break;
		case ')':top--;break;
		default:
				p=(BTNode*)malloc(sizeof(BTNode));
				p->data=ch;
				p->lchild=p->rchild=NULL;
				if(b==NULL)
					b=p;
				else
				{
					switch(tag)
					{
					case 1:ps[top]->lchild=p;break;
					case 2:ps[top]->rchild=p;break;
					}
				}
		}
		ch=*(++s);
	}
	return b;
}

void DispBTNode(BTNode *b)//打印结点序列 
{
	if(b!=NULL)
	{
		printf("%c",b->data);
		if(b->lchild!=NULL||b->rchild!=NULL)
		{
			printf("(");
			DispBTNode(b->lchild);
			if(b->rchild!=NULL)printf(",");
			DispBTNode(b->rchild);
			printf(")");
		}
	}
}
int BTNodeHeight(BTNode *b)//得知树的深度 
{
	int lchildh,rchildh;
	if(b==NULL)return 0;
	else
	{
		lchildh=BTNodeHeight(b->lchild);
		rchildh=BTNodeHeight(b->rchild);
		return (lchildh>rchildh)?(lchildh+1):(rchildh+1);
	}
}


void SetPBTNodeInfo(BTNode *b,PBTNode *parent,PBTNode *pb,int level,int lrflag)
{
	int f=3;
	pb->data=b->data;
	pb->key =b->key;
	pb->parent=parent;
	pb->level=level;
	pb->lrflag=lrflag;
	pb->space=-1;
}


int CreatePBTNode(BTNode *b,PBTNode *pqu[])
{
	BTNode *p;
	BTNode *qu[MaxSize];
	int front=-1,rear=-1;
	rear++;
	qu[rear]=b;
	pqu[rear]=(PBTNode*)malloc(sizeof(PBTNode));
	SetPBTNodeInfo(b,NULL,pqu[rear],1,-1);
	while(rear!=front)
	{
		front++;
		p=qu[front];
		if(p->lchild!=NULL)
		{
			rear++;
			qu[rear]=p->lchild;
			pqu[rear]=(PBTNode*)malloc(sizeof(PBTNode));
			SetPBTNodeInfo(p->lchild,pqu[front],pqu[rear],pqu[front]->level+1,0);
		}
		if(p->rchild!=NULL)
		{
			rear++;
			qu[rear]=p->rchild;
			pqu[rear]=(PBTNode*)malloc(sizeof(PBTNode));
			SetPBTNodeInfo(p->rchild,pqu[front],pqu[rear],pqu[front]->level+1,1);
		}
	}
	return rear;
}


void PBTNodePrint(PBTNode *pb[],int n,int h)
{
	int l=-1,r=0,i,j,k,end;
	char c;
	PBTNode *p;
	if(n<=0||h<=0)
	{
		return;
	}
	else if(n==1)
	{
		for(i=0;i<pb[0]->space;i++)
			printf(" ");
		printf("%c",pb[0]->data);
		printf("\n");
		return;
	}
	h=h-pb[0]->level+2;
	for(k=0;k<h;k++)
	{
		j=0;
		l--;
		r++;
		for(i=0;i<n;i++)
		{
			p=pb[i];
			end=(p->lrflag==0)?l:r;
			end+=p->parent->space;
			for(;j<end;j++)
				printf(" ");
			c=(p->lrflag==0)?'/':'\\';
			printf("%c",c);
		}
		printf("\n");
	}
	for(i=0;i<n;i++)
	{
		p=pb[i];
		if(p->lrflag==0)
			p->space=p->parent->space+l;
		else
			p->space=p->parent->space+r;
	}
	for(i=0,j=0;i<n;i++)
	{
		p=pb[i];
		for(;j<p->space;j++)
			printf(" ");
		printf("%c",p->data);
	}
	printf("\n");
}
 
void DispBTree(BTNode *b)
{
	int n,i,j,high,level;
	PBTNode *p;
	PBTNode *pqu[MaxSize];
	PBTNode *levelpqu[MaxSize];
	n=CreatePBTNode(b,pqu);
	high=BTNodeHeight(b);
	j=0;
	level=1;
	pqu[0]->space=Pstart;
	for(i=0;i<=n;i++)
	{
		p=pqu[i];
		if(p->level==level)
		{
			levelpqu[j]=p;
			j++;
		}
		else
		{
			PBTNodePrint(levelpqu,j,high);
			level=p->level;
			j=0;
			levelpqu[j]=p;
			j++;
		}
	}
	PBTNodePrint(levelpqu,j,high);
}
int main()
{
	int iDepth=0,iWidth=0,iCount=0;
	//哈夫曼树完整的先序遍历序列（个人）
	char * str0="*(*(*(*(*(f,w),s),e),*(*(n,i),a)),*(*(*(o,r),*(*(l,*(v,p)),*(*(*(k,b),u),*(*(g,i),m)))),*(*(t,*(h,*(*(D,.),*(c,*(*(A,*(W,*(:,B))),*(*(*(E,S),*(q,x)),*(N,T))))))),K)))";
	
	//左子树 
	char * str1="*(*(*(*(*(f,w),s),e),*(*(n,i),a)),*)" ;
	
	
	//右子树的左子树 
	char * str2="*(*(o,r),*(*(l,*(v,p)),3))";
	char * str3="*(*(*(k,b),u),*(*(g,i),m))";
	
	
	//右子树的右子树 
	char * str4="*(*(t,*(h,*(*(D,.),*(c,*(*(A,*(W,*(:,B))),4))))),K)";
	char * str5="*(*(*(E,S),*(q,x)),*(N,T))";
	printf("哈夫曼树中的左子树为：\n"); 
	BTNode *b=CreateBTNode(str1);
	printf("\n");
	DispBTree(b);
	printf("哈夫曼树中的右子树的左子树为：\n"); 
	b=CreateBTNode(str2);
	printf("\n");
	DispBTree(b);
	printf("哈夫曼树中的右子树的左子树3结点及以下的结点为：");
	b=CreateBTNode(str3);
	printf("\n");
	DispBTree(b);
	
	printf("哈夫曼树中的右子树的右子树为：\n"); 
	b=CreateBTNode(str4);
	printf("\n");
	DispBTree(b);
	printf("哈夫曼树中的右子树的右子树4结点及以下的结点为：\n");
	b=CreateBTNode(str5);
	printf("\n");
	DispBTree(b); 
	
	b=CreateBTNode(str0);
	iDepth=BTNodeHeight(b);
	printf("该哈夫曼树中的先序遍历结点序列为：\n"); 
	DispBTNode(b);
	printf("\n"); 
	printf("\n"); 
	printf("该哈夫曼树的深度为：\n"); 
	printf("Depth:%d\n",iDepth);
	
	system("pause");
}