bintree.cpp

数据结构关于二叉树操作的源码

//创建一个二叉树,并遍历之
#include <stdio.h>
#include <malloc.h>

#define MAX 30//定义结点数目最大为30
typedef struct bnode
{
	int data;
	struct bnode *lchild;
	struct bnode *rchild;
}btree;

btree *find(btree *p,int x)
{
	btree *q;
	if(p==NULL) return(NULL);
	else if(p->data==x) return (p);
		else
		{
			q=find(p->lchild,x);
			if(q==NULL)
				return(find(p->rchild,x));
			else return(q);
		}
}

btree *create()
{
	int pvalue,cvalue,type,i=1;
	btree *p,*q,*s,*head;
	printf ("输入建立二叉树(以-1表示输入结束)\n");
	printf("第%d个结点=>\n	根结点值:",i++);
	scanf("%d",&cvalue);
	if (cvalue!=-1)	
	{
		head=(btree *) malloc(sizeof(btree));
		head->data=cvalue;
		head->lchild=NULL;
		head->rchild=NULL;
	}
	else return (NULL);
	do
	{
		printf("第%d个结点=>\n	父结点值:",i++);
		scanf("%d",&pvalue);
		if(pvalue!=-1)
		{
			do
			{
				printf("左(0)或右(1)结点:");
				scanf("%d",&type);
			}while(type!=0&&type!=1);
			printf("	当前结点值");
			scanf("%d",&cvalue);
		}
		if(pvalue!=-1)
		{
			p=head;
			q=find(p,pvalue);
			if(q!=NULL)
			{
				s=(btree *)malloc(sizeof(btree));
				s->data=cvalue;
				s->lchild=NULL;
				s->rchild=NULL;
				if(type==0) q->lchild=s;
				if(type==1) q->rchild=s;
			}
			else
			{
				printf("已建的二叉树中没有指定值的结点\n");
				i--;
			}
		}
	}while(pvalue!=-1);
	return(head);
}

void inorder(btree *b)
{
	btree *stack[MAX],*p;
	int top=0;
	p=b;
	while(p!=NULL||top>0)
	{
		if(p!=NULL)
		{
			top++;
			stack[top]=p;
			p=p->lchild;
		}
		else{
			p=stack[top];			//p所指结点为无左子树的结点或其左子树已遍历过
			top--;
			printf("%d ",p->data);	//访问结点
			p=p->rchild;			//扫描右子树
		}
	}
}

void main()
{	//以下为验证程序
	btree *p;
	p=create();
	inorder(p);
}