（C语言-数据结构与算法）还原二叉树@慕课网原创_慕课网

因为看到一篇文章，是搞编程的学长写的，他在求职的时候，面试官说他提前看过了学长的博客，我在想我也应该把自己写代码的一些心得一些问题写出来，虽然在上大学之前，从来没有这样接触电脑，除了玩游戏以外，我连装系统都不会，但是对于写代码我也有自己的想法，我并非热爱编程，可能因为从来没有过目标，所以对什么也不感兴趣。我现在刚上大一，目前是大一下学期，正在学习数据结构和算法，偶然一次问老师一道题，根据先序遍历和中序遍历，还原二叉树，老师说这个可以用代码实现，我就第一次尝试自己写一份代码，之前的代码一部分是自己的思想，一部分是复制粘贴别人的代码，成就感不强，这次的代码从头到尾全是我自己写的，写完很激动。

题目：先序：“abdgcefh”;中序：“dgbaechf”;，还原这棵二叉树

我是这样处理这问题的，首先我并不懂如何还原，我要知道还原的原理是什么，我百度了一下，这样的题是如何求解的，于是有了答案，我把步骤分解一下：

先序的第一个一定是树根，根据树根，中序当中可以分为三部分，根据中序分的部分，先序也可以分成三部分

先序的三部分：a bdg cefh，中序的三部分：dgb a echf

从这部分可以看出，a是根，左孩子是“bdg”这部分，右孩子是“echf”这部分，然后采用递归的思想对左右孩子进行同样的步骤。

我的算法思想很快就形成了，可实现起来，还是走了一点弯路，首先，我一开始就想直接对数组的地址进行操作，于是百度到了一个函数char *strchr(const char *string, int 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;
};
void subLm(char A[], char B[], char C);//获取中序遍历的左边
void subRm(char A[], char B[], char C);//获取中序遍历的右边
int subLp(char A[], char B[], int C);//获取先序遍历的左边
void subRp(char A[], char B[], int C);//获取先序遍历的右边
int strlength(char * str);//计算长度
char captureA(char temp[]);//该函数返回值为传递字符串的首字符，并且字符串全体向前移动1格，覆盖掉首字符
void formPrint(TreeNode *T);//后序输出二叉树
TreeNode *restore(TreeNode *&T, char Pc[], char Mc[]);//还原二叉树
void main()
{
 TreeNode *T = NULL;//定义头结点然后初始化
 restore(T, preOrder, midOrder);//传递全局变量先序和后序的字符串
 formPrint(T);
}
int strlength(char * str)
{
 int a = 0;
 while (*str++ != '\0')
  a++;
 return(a);
}
void subLm(char A[], char B[], char C)
{
 int i = 0;
 while (1)
 {
  if (B[i] == C)
  {
   A[i] = '\0';
   break;
  }
  else
  {
   A[i] = B[i];
   i++;
  }
 }
}
void subRm(char A[], char B[], char C)
{
 int i = 0, j = 0;
 while (B[i++] != C);
 do
 {
  A[j] = B[i++];
 } while (A[j++]);
}
char captureA(char temp[])
{
 char row = temp[0];
 for (int i = 0; temp[i] != '\0'; i++)
 {
  temp[i] = temp[i + 1];
 }
 return(row);
}
TreeNode * restore(TreeNode *&T, char Pc[], char Mc[])
{
 int m, n, k;
 char temp;
 char mLc[MAX], mRc[MAX], pLc[MAX], pRc[MAX];
 temp = captureA(Pc);
 subLm(mLc, Mc, temp);//执行完该函数，mLc字符数组将获得以temp为参考，之前的字符串
 subRm(mRc, Mc, temp);//mRc字符数组将获得temp之后的字符串
 m = strlength(mLc);//计算中序字符串中temp左边的字符串的长度
 k = strlength(mRc);//计算中序字符串中temp右边的字符串的长度
 n = subLp(pLc, Pc, m);//由已知的m传递参数，subLp的返回值是先序字符串temp之后的位置+1
 subRp(pRc, Pc, n);//pLc是先序字符串去除temp后，第1-第m个字符，pRc是第m+1个到最后
 T = new TreeNode;
 T->data = temp;
 if (m == 0)
 {
  T->Lnode = NULL;
 }
 else
 {
  restore(T->Lnode, pLc, mLc);
 }
 if (k == 0)
 {
  T->Rnode = NULL;
 }
 else
 {
  restore(T->Rnode, pRc, mRc);
 }
 return(T);
}int subLp(char A[], char B[], int C)
{
 int i = 0;
 for (; i < C; i++)
 {
  A[i] = B[i];
 }
 A[i] = '\0';
 return(i);
}
void subRp(char A[], char B[], int C)
{
 int i = 0;
 do
 {
  A[i] = B[C++];
 } while (A[i++]);
}
void formPrint(TreeNode *T)
{
 if (T == NULL)
  return;
 formPrint(T->Lnode);
 formPrint(T->Rnode);
 printf("%c", T->data);
}

（C语言-数据结构与算法）还原二叉树原创