纯C 生成二叉树广义表 根据广义表重构二叉树

讲解很多都写在注释里了，重构二叉树的过程后面单独拿出来讲

直接上代码：

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <limits.h>
typedef struct BiTree
{
	int data;
	struct BiTree* next[2];
} BiTree;
BiTree* BiTree_init(int val)//节点初始化
{
	BiTree* p = (BiTree*)malloc(sizeof(BiTree));
	if (p == NULL) return NULL;
	p->data = val;
	p->next[0] = p->next[1] = NULL;
	return p;
}
void BiTree_clear(BiTree* root)
{
	if (root == NULL) return;
	BiTree_clear(root->next[0]);
	BiTree_clear(root->next[1]);
	free(root);
}
BiTree* BiTree_insert(BiTree* root, int val)
{
	if (root == NULL) return BiTree_init(val);
	int pos = rand() % 2;
	root->next[pos] = BiTree_insert(root->next[pos], val);
	return root;
}
void BiTree_BFS(BiTree* root)
{
	if (root == NULL) return;
	BiTree* q[100] = { NULL };
	int head = 0, tail = 0;
	q[tail++] = root;
	printf("%2d\n", root->data);
	while (head != tail)
	{
		if (q[head]->next[0])
		{
			q[tail] = q[head]->next[0];
			printf("%2d > %2d (L)\n", q[head]->data, q[tail]->data);
			tail++;
		}
		if (q[head]->next[1])
		{
			q[tail] = q[head]->next[1];
			printf("%2d > %2d (R)\n", q[head]->data, q[tail]->data);
			tail++;
		}
		head++;
	}
}
void BiTree_convertToGeneList_sub(BiTree* root, int* ret, int* top)
{//就是一个深搜的过程，只不过是在前中后分别加上'(' ',' ')'
	//多封装一层是为了在不使用全局变量的前提下实现入栈
	if (root == NULL) return;
	ret[++(*top)] = root->data + 128;//为了避免数据的ASCII码值和'(' ',' ')'重合，数据存储时+128，打印时-128
	if (root->next[0] || root->next[1])//左右子树都空就不带'(,)'
	{
		ret[++(*top)] = '(';
		BiTree_convertToGeneList_sub(root->next[0], ret, top);
		ret[++(*top)] = ',';
		BiTree_convertToGeneList_sub(root->next[1], ret, top);
		ret[++(*top)] = ')';
	}
}
int* BiTree_convertToGeneList(BiTree* root)
{
	if (root == NULL) return NULL;
	int* ret = (int*)malloc(sizeof(int) * 1000);//临时变量出函数后空间就被释放了，必须malloc
	int top = -1;
	BiTree_convertToGeneList_sub(root, ret, &top);
	ret[++top] = INT_MAX;//以INT_MAX作为广义表形式的结束标志，防止占用其他数据
	return ret;
}
BiTree* BiTree_rebuild_GeneList_sub(int* arr, int* p)
{
	if (arr == NULL || arr[*p] == INT_MAX) return NULL;
	BiTree* root = BiTree_init(arr[*p] - 128);
	if (arr[*p + 1] == ',' && arr[*p] >= 128) return root;
	if (arr[*p + 1] == INT_MAX) return root;
	int memory = arr[*p + 1];
	if (arr[*p + 1] == '(') *p += 2;
	if (arr[*p] == ',')
	{
		*p += 1;
		root->next[1] = BiTree_rebuild_GeneList_sub(arr, p);
		if (memory == '(') *p += 1;
	}
	else if (arr[*p + 1] != ')')//arr[*p] == data
	{
		root->next[0] = BiTree_rebuild_GeneList_sub(arr, p);
		*p += 2;
		if (arr[*p] >= 128)
		{
			root->next[1] = BiTree_rebuild_GeneList_sub(arr, p);
			if (memory == '(') *p += 1;
		}
	}
	return root;
}
BiTree* BiTree_rebuild_GeneList(int* arr)
{
	if (arr == NULL || arr[0] == INT_MAX) return NULL;
	int p = 0;//多封装一层也是为了不用全局变量
	BiTree* root = BiTree_rebuild_GeneList_sub(arr, &p);
	return root;
}
void BiTree_test()
{
	BiTree* root = NULL;
	int i;
	for (i = 0; i < 30; i++) root = BiTree_insert(root, rand() % 100);//随机生成一颗有30个节点的二叉树
	BiTree_BFS(root);//打印二叉树，以便检验重构二叉树是否正确
	printf("\n\n");
	int* arr = BiTree_convertToGeneList(root);//生成二叉树广义表形式
	BiTree* rebuild = BiTree_rebuild_GeneList(arr);//根据二叉树广义表形式重构二叉树
	BiTree_BFS(rebuild);
	BiTree_clear(root);
	BiTree_clear(rebuild);
}
int main()
{
	//不写srand()是为了方便Debug
	BiTree_test();
	return 0;
}

重构二叉树：

先定义函数功能：以根节点+括号对为单位进行处理

根据 arr & p 还原二叉树，返回其根节点，并令 *p 指向队列中的合适位置

(如碰到 '(' 就要在函数结束前再令 *p 后移一位，以跳出括号对)

再写函数框架：

以根节点为单位进行处理时，先看第一个节点，因为确保这个节点是根节点

所以直接创建并初始化

它的右边要么是 INT_MAX (结束)，要么是 '(' (左右子树)

BiTree* BiTree_rebuild_GeneList_sub(int* arr, int* p)
{
	if (arr == NULL || arr[*p] == INT_MAX) return NULL;//特殊情况判断
	BiTree* root = BiTree_init(arr[*p] - 128);//节点创建并初始化
	if (arr[*p + 1] == INT_MAX) return root;//下一个位置就结束时直接返回
    int memory = arr[*p + 1];//memory记录下一位置信息，如果是'('
    //若下一位置是'('，函数结束前 *p 要向后移动一位，以跳出')'
	if (arr[*p + 1] == '(') *p += 2;//下一个位置是'('时令指针指向括号内部，准备生成左右子树
	return root;
}

再详细完善进入第一个括号对后应进行的操作

BiTree* BiTree_rebuild_GeneList_sub(int* arr, int* p)
{
	if (arr == NULL || arr[*p] == INT_MAX) return NULL;
	BiTree* root = BiTree_init(arr[*p] - 128);
	if (arr[*p + 1] == INT_MAX) return root;
	int memory = arr[*p + 1];
	if (arr[*p + 1] == '(') *p += 2;
	if (arr[*p] == ',')
	{//进入括号对内部后，若第一个碰到的就是','，说明该根节点无左子树，*p += 1 后生成右子树
		*p += 1;
		root->next[1] = BiTree_rebuild_GeneList_sub(arr, p);
		if (memory == '(') *p += 1;//跳出')'
	}
	else//arr[*p] == data，生成左子树，并根据情况生成右子树
	{
		root->next[0] = BiTree_rebuild_GeneList_sub(arr, p);
		*p += 2;//移动到','的下一位
		if (arr[*p] >= 128)//','下一位仍是数据，说明该根节点左右子树都有，生成右子树
		{
			root->next[1] = BiTree_rebuild_GeneList_sub(arr, p);
			if (memory == '(') *p += 1;//也要注意跳出')'
		}
	}
	return root;
}

最后补充后续根节点+括号对会碰到的特殊情况

原根节点的左孩子若无左右子树，队列后面紧跟着的是 ','

原根节点的右孩子若无左右子树，队列后面紧跟着的是 ')'

BiTree* BiTree_rebuild_GeneList_sub(int* arr, int* p)
{
	if (arr == NULL || arr[*p] == INT_MAX) return NULL;
	BiTree* root = BiTree_init(arr[*p] - 128);
	if (arr[*p + 1] == ',' && arr[*p] >= 128) return root;//原根节点左孩子无左右子树
	if (arr[*p + 1] == INT_MAX) return root;
	int memory = arr[*p + 1];
	if (arr[*p + 1] == '(') *p += 2;
	if (arr[*p] == ',')
	{
		*p += 1;
		root->next[1] = BiTree_rebuild_GeneList_sub(arr, p);
		if (memory == '(') *p += 1;
	}
	else if (arr[*p + 1] != ')')//原根节点右孩子有左右子树
	{
		root->next[0] = BiTree_rebuild_GeneList_sub(arr, p);
		*p += 2;
		if (arr[*p] >= 128)
		{
			root->next[1] = BiTree_rebuild_GeneList_sub(arr, p);
			if (memory == '(') *p += 1;
		}//这两个对 *p 的操作都是让其指向合适的位置
	}
	return root;
}

思路正确后耐心 Debug 即可，主要就是各种 if