📄 6-2-2.txt

📁 数据结构源程序
💻 TXT
字号:
/*二叉树的基本运算与实现*/
#include <stdio.h>
#define MAXNODE 256
typedef int datatype;
typedef struct BiTNode
{
	datatype data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct
{
	BiTree link;
	int flag;
}stacktype;

void menu();
int Initiate(BiTree *bt,datatype x);
BiTree InsertL(BiTree bt,datatype x,BiTree parent);
BiTree InsertR(BiTree bt,datatype x,BiTree parent);
BiTree DeleteL(BiTree bt,BiTree parent);
BiTree DeleteR(BiTree bt,BiTree parent);
void PreOrder(BiTree bt);
void InOrder(BiTree bt);
void PostOrder(BiTree bt);
BiTree Find(BiTree parent,datatype a);
void NRPreOrder(BiTree bt);
void NRInOrder(BiTree bt);
void NRPostOrder(BiTree bt);

void main()
{
	int n,m=1;
	BiTree t;

	/*clrscr();*/
	while(m)
	{
		menu();
		scanf("%d",&n);
		switch(n)
		{
			case 1:{/*初始化*/
				int flag;
				datatype x;
				printf("please input head point x:\n");
				scanf("%d",&x);
				flag=Initiate(&t,x);
				if(flag==1)
					printf("\nInitiate success!");
				else
					printf("\nInitiate fail!");
				break;
				}
			case 2:{/*建树*/
				break;
				}
			case 3:{/*插入结点x作为a的左孩子*/
				datatype a,x;/*x作为a的左孩子*/
				BiTree parent=t;
				printf("please input a and x:\n");
				scanf("%d%d",&a,&x);
				parent=Find(parent,a);
				parent=InsertL(t,x,parent);
				if(parent!=NULL)
					t=parent;
				break;
				}
			case 4:{/*插入结点x作为a的右孩子*/
				datatype a,x;/*x作为a的右孩子*/
				BiTree parent=t;
				printf("please input a and x:\n");
				scanf("%d%d",&a,&x);
				parent=Find(parent,a);
				parent=InsertR(t,x,parent);
				if(parent!=NULL)
					t=parent;
				break;
				}
			case 5:{/*删除结点a的左孩子*/
				datatype a;
				BiTree parent=t;
				printf("please input a:\n");
				scanf("%d",&a);
				parent=Find(parent,a);
				parent=DeleteL(t,parent);
				if(parent!=NULL)
					t=parent;
				break;
				}
			case 6:{/*删除结点a的左孩子*/
				datatype a;
				BiTree parent=t;
				printf("please input a:\n");
				scanf("%d",&a);
				parent=Find(parent,a);
				parent=DeleteR(t,parent);
				if(parent!=NULL)
					t=parent;
				break;
				}
			case 7:{/*递归先序遍历*/
				PreOrder(t);
				break;
				}
			case 8:{/*递归中序遍历*/
				InOrder(t);
				break;
				}
			case 9:{/*递归后序遍历*/
				PostOrder(t);
				break;
				}
			case 10:{/*先序遍历的非递归实现*/
				NRPreOrder(t);
				break;
				}
			case 11:{/*中序遍历的非递归实现*/
				NRInOrder(t);
				break;
				}
			case 12:{/*后序遍历的非递归实现*/
				NRPostOrder(t);
				break;
				}
			case 0:m=0;
		}
	}
}
void menu()
{
	/*clrscr();*/
	printf("\n");
	printf("\t\t1.initiate\n\n");
	printf("\t\t2.create thread\n\n");
	printf("\t\t3.insert Left\n\n");
	printf("\t\t4.insert Right\n\n");
	printf("\t\t5.delete Left\n\n");
	printf("\t\t6.delete Right\n\n");
	printf("\t\t7.preorder\n\n");
	printf("\t\t8.inorder\n\n");
	printf("\t\t9.postorder\n\n");
	printf("\t\t10.nrpreorder\n\n");
	printf("\t\t11.nrinorder\n\n");
	printf("\t\t12.nrpostorder\n\n");
	printf("\t\t0.exit\n\n");
	printf("\n\n\n\tplease select:");
}
int Initiate(BiTree *bt,datatype x)
{
	if((*bt=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
		return 0;
	(*bt)->data=x;
	(*bt)->lchild=NULL;
	(*bt)->rchild=NULL;
	return 1;
}
BiTree InsertL(BiTree bt,datatype x,BiTree parent)
{
	BiTree p;
	if(parent==NULL)
	{
		printf("\nerror!\n");
		return NULL;
	}
	if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
		return NULL;
	p->data=x;
	p->lchild=NULL;
	p->rchild=NULL;
	if(parent->lchild==NULL)
		parent->lchild=p;
	else
	{
		p->lchild=parent->lchild;
		parent->lchild=p;
	}
	return bt;
}
BiTree InsertR(BiTree bt,datatype x,BiTree parent)
{
	BiTree p;
	if(parent==NULL)
	{
		printf("\nerror!\n");
		return NULL;
	}
	if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
		return NULL;
	p->data=x;
	p->lchild=NULL;
	p->rchild=NULL;
	if(parent->rchild==NULL)
		parent->rchild=p;
	else
	{
		p->rchild=parent->rchild;
		parent->rchild=p;
	}
	return bt;
}
BiTree DeleteL(BiTree bt,BiTree parent)
{
	BiTree p;
	if(parent==NULL||parent->lchild==NULL)
	{
		printf("\ndelete error!");
		return NULL;
	}
	p=parent->lchild;
	parent->lchild=NULL;
	free(p);
	return bt;
}
BiTree DeleteR(BiTree bt,BiTree parent)
{
	BiTree p;
	if(parent==NULL||parent->rchild==NULL)
	{
		printf("\ndelete error!");
		return NULL;
	}
	p=parent->rchild;
	parent->rchild=NULL;
	free(p);
	return bt;
}
void PreOrder(BiTree bt)
{
	if(bt==NULL)
		return;
	printf("%5d",bt->data);
	PreOrder(bt->lchild);
	PreOrder(bt->rchild);
}
void InOrder(BiTree bt)
{
	if(bt==NULL)
		return;
	InOrder(bt->lchild);
	printf("%5d",bt->data);
	InOrder(bt->rchild);
}
void PostOrder(BiTree bt)
{
	if(bt==NULL)
		return;
	PostOrder(bt->lchild);
	PostOrder(bt->rchild);
	printf("%5d",bt->data);
}
BiTree Find(BiTree parent,datatype a)
{
	BiTree p;
	if(parent==NULL)
		p=NULL;
	else if(parent->data==a)
		p=parent;
	else
	{
		p=Find(parent->lchild,a);
		if(p==NULL)
			p=Find(parent->rchild,a);
	}
	return p;
}
void NRPreOrder(BiTree bt)
{
	BiTree stack[MAXNODE],p;
	int top;
	if(bt==NULL)
	{
		printf("Tree is empty!\n");
		return;
	}
	top=-1;
	p=bt;
	while((p!=NULL)||(top!=-1))
	{
		while(p!=NULL)
		{
			printf("%5d",p->data);
			if(top==MAXNODE-1)
			{
				printf("Stack overflow!\n");
				return;
			} /* end if */
			else
			{
				top++;
				stack[top]=p;
			} /* end if-else */
			p=p->lchild;
		} /* end while p */
		p=stack[top];
		top--;
		p=p->rchild;
	} /* end while p && top */
}
void NRInOrder(BiTree bt)
{
	BiTree stack[MAXNODE],p;
	int top;
	if(bt==NULL)
	{
		printf("Tree is empty!\n");
		return;
	}
	top=-1;
	p=bt;
	while((p!=NULL)||(top!=-1))
	{
		while(p!=NULL)
		{
			if(top==MAXNODE-1)
			{
				printf("Stack overflow!\n");
				return;
			} /* end if */
			else
			{
				top++;
				stack[top]=p;
			} /* end if-else */
			p=p->lchild;
		} /* end while p */
		p=stack[top];
		top--;
		printf("%5d",p->data);
		p=p->rchild;
	} /* end while p && top */
}
void NRPostOrder(BiTree bt)
{
	stacktype stack[MAXNODE];
	BiTree p;
	int top,sign;
	if(bt==NULL)
	{
		printf("Tree is empty!\n");
		return;
	}
	top=-1;
	p=bt;
	while((p!=NULL)||(top!=-1))
	{
		if(p!=NULL) /*结点第一次入栈*/
		{
			top++;
			stack[top].link=p;
			stack[top].flag=1; /*标记第一次入栈*/
			p=p->lchild;
		} /* end if */
		else
		{
			p=stack[top].link;
			sign=stack[top].flag;
			top--;
			if(sign==1) /*结点第二次入栈*/
			{
				top++;
				stack[top].link=p;
				stack[top].flag=2; /*标记第二次入栈*/
				p=p->rchild;
			} /* end if */
			else
			{
				printf("%5d",p->data);
				p=NULL;
			} /* end if-else */
		} /* end if-else */
	} /* end while */
}
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -