数据结构

开发平台：

Visual C++

Cpp1.cpp：源码内容

							#include <stdio.h>
#include <malloc.h>
#include <stdlib.h> 
#define MaxSize 100 //空间上限
typedef char ElemType;//数据单元定义为字符型
typedef struct node//标准二叉树型结构
{ ElemType data;
struct node *lchild;
struct node *rchild;
}BiTNode;
void CreateBiTNode(BiTNode *&b)//创建树
{
	BiTNode *St[MaxSize],*p=NULL;
	int top=-1,k,j=0,a;
	char ch0,ch;
	char str[MaxSize];
	b=NULL;
    printf("请输入一个格式为A(B,C)的二叉树：n以#结束n");
	ch0=getchar();
	for(a=0;ch0!='#';a++){
		str[a]=ch0;
		ch0=getchar();
	}
	ch=str[j];
	while(ch!='#')
	{
		switch(ch)
		{
		case'(':top++;St[top]=p;k=1;break;
		case')':top--;break;
		case',':k=2;break;
		default:p=(BiTNode *)malloc(sizeof(BiTNode));
			p->data=ch;p->lchild=p->rchild=NULL;
			if(b==NULL)
				b=p;
			else
			{ switch(k)
			{
		case 1:St[top]->lchild=p;break;
		case 2:St[top]->rchild=p;break;
			}
			}
		}
		j++;
		ch=str[j];
	}
}
void DispBiTNode(BiTNode *b)//由上至下深度遍历输出树
{
	if(b!=NULL)
	{ printf("%c",b->data);
	if (b->lchild!=NULL||b->rchild!=NULL)
	{ printf("(");
	DispBiTNode(b->lchild);
	if (b->rchild!=NULL)printf(",");
	DispBiTNode(b->rchild);
	printf(")");
	}
	}
}
void Path(BiTNode *b,ElemType path[],int pathlen)//倒序导出路径
{
int i;
if (b!=NULL)
{ 
	if(b->lchild==NULL&&b->rchild==NULL)
	{ 
		printf("%c到根结点路径:%c",b->data,b->data);
	    for(i=pathlen-1;i>=0;i--)
		  printf("%c",path[i]);
	    printf("n");
	}
	else
	{ 
		path[pathlen]=b->data;
	    pathlen++;
	    Path(b->lchild,path,pathlen);
	    Path(b->rchild,path,pathlen);
	    pathlen--;
	}
}
}
void Path0(BiTNode *b,ElemType path[],int pathlen)//正序导出路径
{
	int i;
if (b!=NULL)
{
	
  if (b->lchild!=NULL&&b->rchild!=NULL)
	{ 
		
        path[pathlen]=b->data;
		pathlen++;
		Path0(b->lchild,path,pathlen);
		Path0(b->rchild,path,pathlen);
	}
  else 
  {     printf("从根节点到子结点的路径:");    
	    for(i=0;i<=pathlen-1;i++)
	    printf("%c",path[i]);
        printf("%c",b->data);
		printf("n"); 
  }
}
}
void FroutBiTNode(BiTNode *b)//前序遍历输出，非递归
{
  BiTNode *code[MaxSize],*t;
  t=b;
  int tot=0;
  code[0]=b;
while (t!=NULL||tot!=-1)
  {
    while (t!=NULL)
	{ if (t!=b)  tot++; 
	  code[tot]=t;
	  printf("%c",t->data);
	  t=t->lchild;
	}
    t=code[tot];
	t=t->rchild;
	tot--;
  }
}
void main()
{   
	BiTNode*b;
	ElemType path[MaxSize];
	int i=0;
	CreateBiTNode(b);
	printf("二叉树b:");
	DispBiTNode(b);
	printf("n");
	Path(b,path,0);
	Path0(b,path,0);
printf("输出前序遍历结果：");
	FroutBiTNode(b);
}

						