[二叉树] 6.70 根据 广义表GList 创建 二叉树BiTree

【题目】6.70
如果用大写字母标识二叉树结点，则一棵二叉树可以用符合下面语法图的字符序列表示。试写一个递归算法，由这种形式的字符序列，建立相应的二叉树的二叉链表存储结构

【思路】递归定义使用递归函数

【测试数据】A(B(#,D(#,#)),C(E(#,F(#,#)),#))

【答案】

// 6.70 由广义表形式的输入建立二叉链表
Status CreateBiTreeByGList(BiTree *pT) {
	char c;
	BiTNode *p;

	c = getchar();
	if (c=='#') p=NULL; //空子树
	else {
		p = (BiTNode *)malloc(sizeof(BiTNode)); if (!p) exit(OVERFLOW);
		p->data=c; //赋值

		if (getchar()!='(') return ERROR; //格式错误
		if ( !CreateBiTreeByGList( &p->lchild ) ) return ERROR; //建立左子树
		if (getchar()!=',') return ERROR; //格式错误
		if ( !CreateBiTreeByGList( &p->rchild ) ) return ERROR; //建立右子树
		if (getchar()!=')') return ERROR; //格式错误
	}

	*pT = p; //把p传出去
	return TRUE;
}

【完整代码】

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

#ifndef BASE
#define BASE
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int bool;
#endif

#define TElemType char //固定为char，若修改需要修改方法
typedef struct BiTNode { // 结点结构
    TElemType      data;
    struct BiTNode  *lchild, *rchild; // 左右孩子指针
}BiTNode, *BiTree;
void visit(TElemType e) {
	printf("%c", e);
}
// 先序遍历二叉树
void PreOrder(BiTree T) { // - 递归
	if (!T) return ;
	visit(T->data);
	PreOrder(T->lchild);
	PreOrder(T->rchild);
}
// 中序遍历二叉树
void InOrder(BiTree T) { // - 递归
	if (!T) return ;
	InOrder(T->lchild);
	visit(T->data);
	InOrder(T->rchild);
}
// 后序遍历二叉树
void PostOrder(BiTree T) { // - 递归
	if (!T) return ;
	PostOrder(T->lchild);
	PostOrder(T->rchild);
	visit(T->data);
}
// 6.70 由广义表形式的输入建立二叉链表
Status CreateBiTreeByGList(BiTree *pT) {
	char c;
	BiTNode *p;

	c = getchar();
	if (c=='#') p=NULL; //空子树
	else {
		p = (BiTNode *)malloc(sizeof(BiTNode)); if (!p) exit(OVERFLOW);
		p->data=c; //赋值

		if (getchar()!='(') return ERROR; //格式错误
		if ( !CreateBiTreeByGList( &p->lchild ) ) return ERROR; //建立左子树
		if (getchar()!=',') return ERROR; //格式错误
		if ( !CreateBiTreeByGList( &p->rchild ) ) return ERROR; //建立右子树
		if (getchar()!=')') return ERROR; //格式错误
	}

	*pT = p; //把p传出去
	return TRUE;
}

int main() {
/* 6.70测试数据
A(B(#,D(#,#)),C(E(#,F(#,#)),#))
*/

	BiTree T;
	int cnt;

	cnt = CreateBiTreeByGList(&T);

	if (cnt) {
		printf("二叉链表：\n");
		PreOrder(T);printf("\n");
		InOrder(T);printf("\n");
		PostOrder(T);printf("\n");
	} else {
		printf("输入不规范\n");
	}

	return 0;
}