目录
7-4
7-3
7-4
输入样例:
21 14 1 4 0 2
输出样例:
112 4 13
u1s1这个题目虚节点会不会合法给出我有点不大明白
不知道虚节点下面到底有没有数
概念理解应该也没有问题
完全二叉树：用二维数组记录 且 数组前面部分都能填满的二叉树
中序遍历： 左 根 右
深度: 层数（用数学公式得）应该这里没问题（换底公式）
由pow(2,n)=lay 得到如下公式
int t = (ceil)(log(n +1.0) / log(2.0)) ;//深度
之前还用了这个计算公式
int t = (int)(log(n *1.0) / log(2.0)) +1;//深度
感觉这个会有问题，但是改了后也不对
思路：
找到最左端子叶（遇到0终止下找）
ps:一开始是从左下角开始找起但是如果根节点和左下角的值之间有虚节点也会找到错误的开端如：1 0 2 3 4 0 6于是从根节点开始找最左子叶（遇到0终止）
打印 给标记
返回上一层
检测左右分支是否都被标记
是，一直向上返回至没被标记的分支
否，进入未被标记的分支进入（都是先左子树 后右子树）
终止条件：i=1 （回到根节点）并且i=1已经被标记
代码：
#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>#include<string.h>#include<cmath>using namespace std;//string a = "1245367", b = "4251637";//string a, b;int T, n;int a[1010];//数据数组int b[1010];//标记数组int i, j, k;int main(){/*debug logs*样例 one 1 2 3 4 0 5*two 1 2 3 0 4 0 5*three1 2 3 4 5 0 0 6**/cin >> T;while (T--){k = 0;//格式控制memset(b, 0, sizeof(b));memset(a, 0, sizeof(a));cin >> n;//int t = (ceil)(log(n +1.0) / log(2.0)) ;//深度for (i = 1; i <= n; i++){cin >> a[i];}i = 1;int temp = t;/*while (--t)//找初始下标(最左子叶 为虚节点没关系）{i = i * 2;}*/while(a[2*i]!=0)i*=2;////printf("开始下标：%d\n", i);//system("pause");while (1){if (a[i] != 0&&b[i]!=1)// b[i]!=1 写不写没影响貌似{if (k != 0){printf(" ");}printf("%d",a[i]);b[i] = 1;k++;}if (a[2 * i] != 0 && b[2 * i] == 0)//左孩子未被标记且值非0{i = 2 * i;// continue;}else if ( a[2 * i + 1] != 0 &&b[2 * i + 1]==0)//右孩子{//要找右孩子的左叶子i = 2 * i + 1;while (a[2 * i] != 0&&b[2*i]==0)i = i * 2;//continue;}else//左右都被标记 或 值为0{i = i / 2; //返回上一级while (b[i] == 1)//上一级被标记 一直返回{i = i / 2; //第一次遇见i=1不会终止if (i == 0)break;//终止}if (i == 0)break;//终止}}printf("\n");printf("%d\n", temp);}}
有点小难找了，不知道是错在哪里
下面是另一份错误代码
经过1时转换成搜索左子树模式
但是若是最后一行中间是虚节点
而最右下角是实节点就会被忽略
#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>#include<string.h>#include<cmath>using namespace std;//string a = "1245367", b = "4251637";//string a, b;int T, n;int a[1010];//数据数组int b[1010];//标记数组int i, j, k;int main(){/*debug日志*样例 one 123405*two 1 2 3 0 4 0 5*three1 2 3 4 5 0 0 6 *1 2 3 4 5 6 7 8 0 0 0 0 0 0 9 找不到*/cin >> T;while (T--){k = 0;//格式控制memset(b, 0, sizeof(b));memset(a, 0, sizeof(a));cin >> n;//int t = (int)(log(n * 1.0) / log(2.0)) + 1;//深度int num = 0;//节点数for (i = 1; i <= n; i++){cin >> a[i];if (a[i] != 0)num++;}if (n == 1){cout << a[1]<<endl;cout << "1" << endl;continue;}if(n==2){cout <<a[2]<<" "<<a[1]<<endl;cout << "2" << endl;continue;}i = 1;int temp = t;t--;while (--t)//找初始下标{i = i * 2;}//倒数的二层左端开始//左子树模式while (1){if (a[2 * i] != 0&& b[2 * i] ==0){if (k != 0)cout << " ";cout << a[2 * i];b[2 * i] = 1;k++;}if (k != 0&&a[i]!=0)cout << " ";cout << a[i];b[i] = 1;k++;if (i == 1)break;if (a[2 * i + 1] != 0 && b[2 * i + 1] == 0){if (k != 0)cout << " ";cout << a[2 * i + 1];b[2 * i + 1] = 1;k++;}i /= 2;}//右子树模式i = 3;while (i * 2 < num)//找到的a[i]不为0{i *= 2;}if(k<num)while (1){if (a[2 * i] != 0 && b[2 * i] == 0){if (k != 0)cout << " ";cout << a[2 * i];b[2 * i] = 1;k++;if (k == num)break;}if (k != 0 )cout << " ";cout << a[i];b[i] = 1;k++;if (k == num)break;if (a[2 * i + 1] != 0 && b[2 * i + 1] == 0){if (k != 0)cout << " ";cout << a[2 * i + 1];b[2 * i + 1] = 1;k++;if (k == num)break;}i /= 2;}printf("\n");printf("%d\n", temp);}}
7-3
一个很巧妙的方法
根据前序遍历特点
将前序遍历的数字 看做 中序遍历的数字里面的根节点
而当前根节点又将该区间分成两部分
如果左边还有数（分支）也就是pos>left2
进入左支
右边同理
都没有数开始打印
返回上一层，继续上一层的任务，和常规递归很像，但是更巧妙
这题是数值，不好用string
#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>#include<string>using namespace std;//string a = "1245367", b = "4251637";//string a, b;int a[100], b[100];void pro_digui(int L1, int R1, int L2, int R2);int n;int main(){//cin >> a >> b;cin >> n;if(n){for (int i = 0; i < n; i++){//scanf_s("%d", &a[i]);cin >> a[i];}//getchar();for (int i = 0; i < n; i++){//scanf_s("%d", &b[i]);cin >> b[i];}pro_digui(0, n-1, 0,n-1);}}void pro_digui(int L1, int R1, int L2, int R2){int pos = 0;int i, j;for (i = 0; i < n; i++){if (b[i] == a[L1]){pos = i;break;}}if (pos > L2){pro_digui(L1 + 1, R1 + pos - L2, L2, pos - 1);}if (pos < R2){pro_digui(L1 + pos - L2 + 1, R1, pos + 1, R2);}cout << a[L1]<<" ";}
