手记

(C语言-数据结构与算法)还原二叉树

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


题目:先序:"abdgcefh";中序:"dgbaechf";,还原这棵二叉树


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


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


先序的三部分:a  bdg  cefh,中序的三部分:dgb  a  echf


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


我的算法思想很快就形成了,可实现起来,还是走了一点弯路,首先,我一开始就想直接对数组的地址进行操作,于是百度到了一个函数char *strchr(const char *string, int c);,如果进行递归,中序部分无法进行辨识,而我还在对地址较劲。我改变思路,自己定义一个数组,来存放每一次分离出来的左右部分,对这左右部分分别递归,形成二叉树,在写这个算法的时候,没有考虑时间复杂度也没考虑代码效率,当时没有懂这么多,我写完这份代码,很快就进行了一点“美化”,然后就用邮箱发给了老师(老师只看邮件,不加QQ,后来才知道以后工作几乎都用邮箱,说是邮箱的安全性高)老师是这么回复我的:



对于问题本身,你能正确输出后序序列,说明二叉树已经正确建立了


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

1. void subLm(char A[], char B[], char C);//获取中序遍历的左边

这些函数的参数,数组类型用了大写字母,单个的字符用小写字母更好一些,对于可读性


2. 具体实现的时候,你使用了很多的临时数组变量,其实是可以避免的:

由始至终先序和中序字符串都没改变,因此,每次只需要记录下临时数组对应的左右两个位置即可、而不用把数组的这些元素复制出来,这样函数的参数只需要传递这左右两个位置变量即可


我仔细看了这些建议,可一直没有时间来改进,有点懒了。

我的代码如下:

/*根据先序和中序遍历输出的字符串还原二叉树,然后输出后序遍历*/#include<stdio.h>#include<stdlib.h>#define MAX 20char 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);}


0人推荐
随时随地看视频
慕课网APP