编辑代码

// 输入 A(B(D,E(G,)),C(,F))
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
 
#define Maxsize 100
 
typedef char Elemtype;
 
/*树的存储结构二叉链表*/
typedef struct BiTNode
{
	Elemtype data;
	struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;
 
/*栈的存储结构*/
typedef struct Stack
{
	BiTree data[Maxsize]; // 存放栈中元素
	int top;		// 栈顶指针
}SqStack;
 
/*初始化栈*/
void InitStack(SqStack* S);
/*入栈*/
bool Push(SqStack* S, BiTree x);
/*出栈*/
bool Pop(SqStack* S, BiTree* x);
 
/*利用广义表构建二叉树*/
void CreateBiTree2(BiTree* T, char* str2);
 
/*先序遍历*/
void PreOrder(BiTree T);
 
/*输出树结点*/
void visit(BiTree T);
 
/*以广义表输出二叉树*/
void DispBiTree(BiTree T);
 
/*获取一个由二叉树构成的广义表字符*/
void GetStr(char* str);
 
int main(void)
{
	BiTree T = NULL;
	char str[50];
	GetStr(str);
	CreateBiTree2(&T, str);
	printf("二叉树的先序遍历：\n");
	PreOrder(T);
	printf("二叉树的括号表示法：");
	DispBiTree(T);
	return 0;
}
 
/*初始化栈*/
void InitStack(SqStack* S)
{
	S->top = -1;
}
 
/*入栈*/
bool Push(SqStack* S, BiTree x)
{
	if (S->top == Maxsize - 1)   // 栈满
		return false;
	S->data[++(S->top)] = x;
	return true;
}
 
/*出栈*/
bool Pop(SqStack* S, BiTree* x)
{
	if (S->top == -1) // 栈空
		return false;
	*x = S->data[(S->top)--];
	return true;
}
 
/*利用广义表构建二叉树*/
void CreateBiTree2(BiTree* T, char* str)
{
	SqStack S;			// 辅助栈
	BiTree p = NULL, x;	// 辅助指针
	InitStack(&S);		// 初始化栈
	char ch;
	int i = 0, k;
	ch = str[i];
	while (ch != '\0')  // str未扫描完时循环
	{
		switch (ch)
		{
		case '(': Push(&S, p);		// 入栈,准备链接左孩子
			k = 1;
			break;
		case ')': Pop(&S, &x);		// 出栈
			break;
		case ',': k = 2;			// 准备链接右孩子结点
			break;
		default:
			p = (BiTree)malloc(sizeof(BiTNode));
			p->data = ch; p->lchild = p->rchild = NULL;
			if ((*T) == NULL)		// p为二叉树的根结点
				(*T) = p;
			else					// 已建立二叉树的根结点,根据k值链接左孩子还是右孩子
			{
				switch (k)
				{
				case 1: S.data[S.top]->lchild = p; break; // 链接左孩子
				case 2: S.data[S.top]->rchild = p; break; // 链接右孩子
				}
			}
		}
		i++;
		ch = str[i]; // 继续扫描str
	}
}
 
/*先序遍历*/
void PreOrder(BiTree T)
{
	if (T != NULL)
	{
		visit(T);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}
 
/*输出树结点*/
void visit(BiTree T)
{
	printf("树结点的值：%c\n", T->data);
}
 
/*获取一个由二叉树构成的广义表字符*/
void GetStr(char* str)
{
	printf("请输入由二叉树构成的广义表字符串：");
	scanf("%s", str);
}
 
/*以广义表输出二叉树*/
void DispBiTree(BiTree T)
{
	if (T != NULL)
	{
		printf("%c", T->data);
		if (T->lchild != NULL || T->rchild != NULL) //左右子树不为空
		{
			printf("(");
			DispBiTree(T->lchild);					// 递归处理左子树
			if (T->rchild != NULL)
				printf(",");
			DispBiTree(T->rchild);					//递归处理右子树
			printf(")");
		}
	}
}