Demo entry 6339003

4.01

   

Submitted by anonymous on Dec 19, 2016 at 08:24
Language: C++. Code size: 2.2 kB.

#include "stdio.h"
#include "malloc.h"

#define MAXSIZE 100
typedef char elemtype;
typedef struct btnode
{
	elemtype data;
	struct btnode *lchild,*rchild;
}bitnode,*bitree;

typedef struct nodd
{
	bitree addr;
	int parent;
}sequre;

int n;
sequre seq[MAXSIZE];

bitree ins_node(bitree s,bitree t)
//将次二叉树的节点按层次遍历的顺序分层,并将各结点链接到二叉树
{
	int kk;
	if(n==1) t=s;
	else 
	{
		kk=n/2;
		if(n%2==0)
			seq[kk].addr->lchild=s;
		else
			seq[kk].addr->rchild=s;
	}
	return t;
}

bitree creat_ordbt()
{
	bitree t,s;
	elemtype x;
	t=NULL;
	printf("请按层顺序输入结点1的值(以#结束,0号为空的结点): ");
	scanf("%c",&x);
	getchar();
	while(x!='#')
	{
		n++;
		if(x!=0)
		{
			s=(bitree)malloc(sizeof(bitnode));
			s->data=x;
			s->lchild=NULL;
			s->rchild=NULL;
			seq[n].addr=s;
			t=ins_node(s,t);
		}
		else
			seq[n].addr=NULL;
		printf("请输入结点 %d 的值(以#结束,0号为空的结点): ",n+1);
		x=getchar();
		getchar();  //吸收回车符
	}
	return t;
}


void print_tree(bitree t)
{
	int i,j,k,nn,start,head,rear;
	sequre seqq[MAXSIZE];
	bitree p;
	if(t==NULL)
		return;
	head=0;nn=rear=0;
	seqq[rear].addr=t;
	for(;head<=rear&&nn<MAXSIZE;head++)
	{
		p=seqq[head].addr ;
		if(p->lchild!=NULL)
			seqq[++rear].addr=p->lchild;
		if(p->lchild!=NULL)
			seqq[++rear].addr=p->rchild;
	}
	for(head=0,j=1,k=1;head<=rear;)
	{
		printf("\n第%d层数据:",j);
		for(i=0,start=head;head<start+k;head++)
		{
			printf("%c  ",seqq[head].addr->data);
			if(seqq[head].addr->lchild==NULL)
				i=i-1;
			if(seqq[head].addr->rchild==NULL)
				i=i-1;
		}
		k=k*2+i;j++;
	}
}

void swap(bitree root)
{
	int top;
	bitree temp,stack[MAXSIZE];
	if(root!=NULL)
	{
		top=1;
		stack[top]=root;
		do
		{
			root=stack[top];
			top=top-1;
			if((root->lchild!=NULL) || (root->rchild!=NULL))
			{
				temp=root->lchild;
				root->lchild=root->rchild;
				root->rchild=temp;

			}
			if(root->lchild!=NULL)
			{
				top++;
				stack[top]=root->lchild;

			}
				if(root->rchild!=NULL)
			{
				top++;
				stack[top]=root->rchild;

			}
		}while(top!=0);
	}

}

int main()
{
	bitree tree;
	tree=creat_ordbt();
	print_tree(tree);
	swap(tree);
	printf("输出交换后的二叉树\n");
	print_tree(tree);
	return 0;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).