二叉数与广义表互相转换

//二叉树广义表互转
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define MAX 10
typedef struct Node {
	int key;
	struct Node* lchild, * rchild;
}Node;
 
Node* getNewNode(int key) {
	Node* p = (Node*)malloc(sizeof(Node));
	p->key = key;
	p->lchild = p->rchild = NULL;
	return p;
}
 
Node* insert(Node* root, int key) {
	if (root == NULL) return getNewNode(key);
	if (rand() % 2) root->lchild = insert(root->lchild, key);
	else root->rchild = insert(root->rchild, key);
	return root;
}
 
Node* getRandomBinaryTree(int n) {
	Node* root = NULL;
	for (int i = 0; i < n; i++) root = insert(root, rand() & 100);
	return root;
}
 
void clear(Node* p) {
	if (p == NULL) return;
	clear(p->lchild);
	clear(p->rchild);
	free(p);
	return;
}
 
 
//二叉树转广义表
char str[1000]; //广义表信息存到str中
int len = 0;
void __serialize(Node* root) {
	if (root == NULL) return;
	len += sprintf(str + len, "%d", root->key);
	if (!root->lchild && !root->rchild) return;
	len += sprintf(str + len, "(");
	__serialize(root->lchild);
	if (root->rchild) len += sprintf(str + len, ",");
	__serialize(root->rchild);
	len += sprintf(str + len, ")");
	return;
}
void serialize(Node* root) {
	memset(str, 0, sizeof(str));
	len = 0;
	__serialize(root);
	return;
}
 
void output(Node* root) {
	if (root == NULL) return;
	printf("%d(%d, %d)\n", 
		root->key, 
		root->lchild ? root->lchild->key : -1, 
		root->rchild ? root->rchild->key : -1);
	output(root->lchild);
	output(root->rchild);
	return;
}
 
 
//广义表转二叉树
Node* deserialize(char* str, int n) {
	Node** sta = (Node**)malloc(sizeof(Node*) * MAX);
 
	int top = -1, flag = 0, scode = 0;
	//flag表示当前节点该连在栈顶结点的左边还是右边
	//scode为状态码，0：任务分发  遇到关键字赋为1 遇到左括号赋为2 遇到逗号赋为3 遇到右括号赋为4 
 
	Node* p = NULL, *root = NULL;
	//p指针指向当前要处理的结点
	//root永远指向最后出栈的元素
 
	for (int i = 0; str[i]; i++) {
		switch (scode){
		case 0: {
			//做任务分发
			if (str[i] >= '0' && str[i] <= '9') scode = 1;
			else if (str[i] == '(') scode = 2;
			else if (str[i] == ',') scode = 3;
			else scode = 4;
			//分发了任务，没有处理当前字符，为了抵消for循环中的i++
			i -= 1;
		}break;
		case 1: {
			//当前位置指向关键字，不考虑负数
			int key = 0;
			while (str[i] <= '9' && str[i] >= '0') {
				key = key * 10 + (str[i] - '0');
				i++;
			}
			p = getNewNode(key);
 
			//flag为1，连在栈顶结点的左边；flag为2，连在栈顶结点的右边
			if (top >= 0 && flag == 0) sta[top]->lchild = p;
			if (top >= 0 && flag == 1) sta[top]->rchild = p;
 
			//读入关键字后i指向关键字下一位，for循环后i会加1，那么关键字下一位就没有被处理
			//所以i减一
			scode = 0, i--;
		}break;
		case 2: {
			//左括号，说明p结点有子结点，则p入栈
			sta[++top] = p;
			flag = 0;
			scode = 0;
		} break;
		case 3: { 
			//逗号，说明下一节点为栈顶结点的右结点
			flag = 1;
			scode = 0; 
		} break;
		case 4: { 
			//右括号，说明栈顶结点没有子节点了，出栈
			root = sta[top--];
			scode = 0; 
		} break;
		}
	}
	return root;
}
 
int main() {
	srand(time(0));
 
	//建立二叉树并输出
	Node* root = getRandomBinaryTree(MAX);
	output(root); printf("\n");
 
	//序列化并输出
	serialize(root);
	printf("str : %s\n\n", str);
 
	//反序列化并输出
	Node* new_root = deserialize(str, len);
	output(new_root);
	return 0;
 }