bi-tree.cpp

本程序包括三个功能：按前序遍历的方式创建二叉树、前序遍历显示二叉树、完全二叉树的判断。其中

#include <stdio.h>
#include <stdlib.h>

typedef struct BiTNode {
	char data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

int flag =0;

/*
//采用前序遍历的形式创建二叉树，空格表示空树
void create(BiTree T) 
{
	char ch;	
	scanf("%c", &ch);
	
	if(ch=='#') T=NULL;
	else {
		T=(BiTree)malloc(sizeof(BiTNode));
		T->data=ch;
		printf("%c\n", T->data);
		
		create(T->lchild);
		create(T->rchild);
	}
	return;
}
*/

//采用前序遍历的形式创建二叉树，空格表示空树
BiTree create() 
{
	BiTree T;
	char ch;	
	scanf("%c", &ch);
	
	if(ch!='#')
	{
		T=(BiTree)malloc(sizeof(BiTNode));
		T->data=ch;
		
		T->lchild=create();
		T->rchild=create();
	}
	else  T=NULL;
	return T;
}

//前序遍历二叉树,并判断是否为完全二叉树
//若是，返回0；否，返回1
int traverse(BiTree T)
{
	if(T) {
		if(!T->lchild && T->rchild) flag=1;
		printf("%c ", T->data);
		traverse(T->lchild);
		traverse(T->rchild);
	}
	else printf("# ");
	return flag;
}

void main()
{
	BiTree T;
	
	T=create();
	int ctree=traverse(T);
	printf("\n");
	if(ctree) printf("非完全二叉树！\n");
	else printf("完全二叉树！\n");
}