利用后序和中序创建一棵二叉树（链树）

利用后序和中序创建一棵二叉树（链树）

一次数据结构的作业，奈何除了菜啥也没有的我对它如此动心

先上题目

已知后序为“GDBEFCA”

已知中序为“DGBAECF”

1. ）根据上述遍历，画出对应的二叉树，写出先序遍历序列（答案请画图或拍照上传）

2. )设计程序利用上述后续和中序创建内存中二叉链表结构并输出线性序列，可以选择以下任一种

   ① 二叉树的括号表示法（参考答案：A(B(D(,G),),C(E,F))）

   ② 教材P131的空格表示法（参考答案：ABD#G###CE##F##）

分析需求：

靠中序和后序的到唯一的二叉树
就要分析中序和后序和二叉树的关系

思路

这里分析左子树，右子树一样分析
后序的最后一位是根节点，再到中序中定位到根节点，根节点左边就是左子树的中序，右边就是右子树的中序，一直这样找下去，找到每一层子树的根节点，就可以画出二叉树了

想采用迭代的手法，把后序序列和中序序列划分，直到序列中只有一个元素或是没有元素了，就找打的叶子节点，然后再返回上一层，直到返回的根节点

上码

#include 
#include 
#define MaxSize 100
#define N 10
typedef char ElemType;
typedef struct BTNode
{
	ElemType data;			//数据元素
	struct BTNode* lchild;	//指向左孩子节点
	struct BTNode* rchild;	//指向右孩子节点
} BTNode,*BITree;

//pos:后序，in：中序，n：节点个数
BTNode* creatBITree(char* pos, char* in, int n) {
	if (n == 0)return NULL;
	char rpos[N], lpos[N], rin[N], lin[N];
	int lnum = 0, rnum = 0;     //左右子树节点个数
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)return NULL;
	node->data = pos[n - 1];        //后序的最后一位是根节点
	int root = -1;                  //中序中根节点的下标
	for (int i = 0; i < n; i++) {
		if (in[i] == pos[n - 1]) {
			root = i;
			break;
		}
	}
	for (int i = 0; i < root; i++) {
		lin[lnum++] = in[i];           //左子树的中序
	}
	for (int i = root + 1; i < n; i++) {
		rin[rnum++] = in[i];           //右子树的中序
	}
	for (int i = 0; i < lnum; i++) {   //左子树的后序
		lpos[i] = pos[i];
	}
	for (int i = 0; i < rnum; i++) {
		rpos[i] = pos[i+lnum];        //右子树的后序
	}

	node->lchild = creatBITree(lpos, lin, lnum);
	node->rchild = creatBITree(rpos, rin, rnum);
	return node;
}

显示二叉树

void DispBTree(BTNode* b)
{
	if (b != NULL)
	{
		printf("%c", b->data);
		if (b->lchild != NULL || b->rchild != NULL)
		{
			printf("(");						//有孩子节点时才输出(
			DispBTree(b->lchild);				//递归处理左子树
			if (b->rchild != NULL) printf(",");	//有右孩子节点时才输出,
			DispBTree(b->rchild);				//递归处理右子树
			printf(")");						//有孩子节点时才输出)
		}
	}
}

测试

int main() {
	char pos[N], in[N];
	int n ,num=0;
	char c;
	printf("输入后序序列：");
	while (true) {
		c = getchar();
		if (c == 'n')break;
		else pos[num++] = c;

	}
	printf("输入中序序列：");
	for (int i = 0; i < num; i++) {
		in[i] = getchar();
	}

	//printf("n后序：n");
	//for (int i = 0; i < num; i++) {
	//	printf("%c", pos[i]);
	//}

	//printf("n中序：n");
	//for (int i = 0; i < num; i++) {
	//	printf("%c", in[i]);
	//}
	BITree tree = creatBITree(pos, in, num);
	printf("n后序：n");
	PosOrder(tree);
	printf("n中序:n");
	InOrder(tree);
	printf("n二叉树：n");
	DispBTree(tree);
	return 0;
}

结果

小结

1. 在调试的过程中也存在一些问题

• 0x77c26c43 (ntdll.dll)处(位于 bitree.exe 中)引发的异常: 0xc0000374: 堆已损坏

在malloc的时候，并没有free，可能导致推满了，然后手动加大堆的大小

加大到50MB，就不信还不够用

• LNK2019 无法解析的外部符号 _main，函数 “int __cdecl invoke_main(void)” (?invoke_main

去网上查了一些解决方案：
更改项目属性中预处理器的部分值

然后更改系统下的子系统

我照着这两个改好了之后，仍然报错，猛男落泪

然后捣鼓一下，把子系统再调回控制台就好了
我也不知道干了什么