(C语言-数据结构)还原二叉树-改进@慕课网原创_慕课网

第一次写的算法老师给予了建议如下：
对于问题本身，你能正确输出后序序列，说明二叉树已经正确建立了

对于代码，有些可改进的地方

void subLm(char A[], char B[], char C);//获取中序遍历的左边
这些函数的参数，数组类型用了大写字母，单个的字符用小写字母更好一些，对于可读性
具体实现的时候，你使用了很多的临时数组变量，其实是可以避免的：
由始至终先序和中序字符串都没改变，因此，每次只需要记录下临时数组对应的左右两个位置即可、而不用把数组的这些元素复制出来，这样函数的参数只需要传递这左右两个位置变量即可

#include<stdio.h>
#include<stdlib.h>
#define MAX 20
char preOrder[MAX] = "abdgcefh";//定义全局变量，先序字符串
char midOrder[MAX] = "dgbaechf";//中序字符串
struct TreeNode{
	char data;
	TreeNode *Lnode;
	TreeNode *Rnode;
};
int strlength(char * str){//计算长度
	int a = 0;
	while (*str++ != '\0')
		a++;
	return a;
}
void formPrint(TreeNode *T){//后序输出二叉树
	if (T == NULL)
		return;
	formPrint(T->Lnode);
	formPrint(T->Rnode);
	printf("%c", T->data);
}
int match(char target, char *data){
	int address = 0;//在data中找到target并返回target位置
	for (; data[address] != '\0'; address++)
		if (data[address] == target)
			return address;
	return -1;
}
int restore(TreeNode *&T,char *pc,char *mc,int &adrs,int head,int rear){
	char temp = pc[adrs++];//依次提取先序字符串中的单个字符
	int abc = match(temp, mc);//abc为temp在中序字符串中的位置
	//每一次把中序字符串分成两部分，以temp为参考的左边和右边
	//左边：记录左边的头mLch 尾mLcr 右边：头mRch 尾mRcr
	int mLch = head, mLcr = abc - 1;
	int mRch = mLcr + 2, mRcr = rear;
	int x = abc - mLch, y = mRcr - abc;//x为左边字符串长度，y为右边长度
	T = new TreeNode;
	T->data = temp;
	if (!x)
		T->Lnode = 0;
	else
		restore(T->Lnode,pc,mc,adrs,mLch,mLcr);
	if (!y)
		T->Rnode = 0;
	else
		restore(T->Rnode,pc,mc,adrs,mRch,mRcr);
	return 0;
}
int main(){
	TreeNode *T = NULL;//定义头结点然后初始化
	int i = 0,k=strlength(preOrder)-1;
	restore(T, preOrder, midOrder,i,0,k);
	//i为先序地址浏览整个先序数组，0为首地址，字符串首地址规定为0
	formPrint(T);
	return 0;
}

按照老师给的建议，不在定义临时数组只记录首尾，整体看上去很简洁，思路和上次的算法一样，唯一改变的是仅仅用首尾来记录数组

(C语言-数据结构)还原二叉树-改进原创