选做3 浪漫侧影
“侧影”就是从左侧或者右侧去观察物体所看到的内容。例如上图中男生的侧影是从他右侧看过去的样子，叫“右视图”；女生的侧影是从她左侧看过去的样子，叫“左视图”。
520 这个日子还在打比赛的你，也就抱着一棵二叉树左看看右看看了……
我们将二叉树的“侧影”定义为从一侧能看到的所有结点从上到下形成的序列。例如下图这棵二叉树，其右视图就是 { 1, 2, 3, 4, 5 }，左视图就是 { 1, 6, 7, 8, 5 }。
于是让我们首先通过一棵二叉树的中序遍历序列和后序遍历序列构建出一棵树，然后你要输出这棵树的左视图和右视图。
输入格式：
输入第一行给出一个正整数 N (≤20)，为树中的结点个数。随后在两行中先后给出树的中序遍历和后序遍历序列。树中所有键值都不相同，其数值大小无关紧要，都不超过 int 的范围。
输出格式：
第一行输出右视图，第二行输出左视图，每行结尾不许有多余空格，格式如样例所示。
输入样例：
8
6 8 7 4 5 1 3 2
8 5 4 7 6 3 2 1
输出样例：
R: 1 2 3 4 5
L: 1 6 7 8 5
#include<iostream>
using namespace std;
typedef struct TNode {
int data;
struct TNode* lchild, * rchild;
int level;
}TNode, * Tree;
Tree Create(int a[], int b[], int n);
int Getdepth(Tree T);
void Rightview(Tree T);
void Leftview(Tree T);
int main() {
int n, i;
int a[25], b[25];
cin >> n;
for (i = 0; i < n; i++)
cin >> a[i];
for (i = 0; i < n; i++)
cin >> b[i];
Tree bt = Create(a, b, n);
Rightview(bt);
Leftview(bt);
return 0;
}
Tree Create(int a[], int b[], int n) {
if (!n) return NULL;
Tree bt = new TNode;
bt->data = b[n - 1];
int i = n - 1;
while (a[i] != b[n - 1]) i--;
bt->lchild = Create(a, b, i);
bt->rchild = Create(a + i + 1, b + i, n - i - 1);
return bt;
}
int Getdepth(Tree T) {
if (!T) return 0;
int leftdep = Getdepth(T->lchild);
int rightdep = Getdepth(T->rchild);
return leftdep > rightdep ? leftdep + 1 : rightdep + 1;
}
void Rightview(Tree T) {
if (T == NULL) return;
int i, j;
Tree queue[100], p;
int front = 0, rear = 0;
Tree arr[100];
int cnt = 0;
queue[rear++] = T;
T->level = 1; //根结点层数为1
while (front != rear) {
p = queue[front++];
arr[cnt++] = p;
if (p->rchild) {
queue[rear++] = p->rchild;
p->rchild->level = p->level + 1;
}
if (p->lchild) {
queue[rear++] = p->lchild;
p->lchild->level = p->level + 1;
}
}
int depth = Getdepth(T);
cout << "R: ";
for (i = 0, j = 1; i < cnt && j <= depth; i++) {
if (arr[i]->level == j) {
if (i == 0) cout << arr[i]->data;
else cout << ' ' << arr[i]->data;
j++;
}
}
cout << endl;
}
void Leftview(Tree T) {
if (T == NULL) return;
int i, j;
Tree queue[100], p;
int front = 0, rear = 0;
Tree arr[100];
int cnt = 0;
queue[rear++] = T;
T->level = 1;
while (front != rear) {
p = queue[front++];
arr[cnt++] = p;
if (p->lchild) {
queue[rear++] = p->lchild;
p->lchild->level = p->level + 1;
}
if (p->rchild) {
queue[rear++] = p->rchild;
p->rchild->level = p->level + 1;
}
}
int depth = Getdepth(T);
cout << "L: ";
for (i = 0, j = 1; i < cnt && j <= depth; i++) {
if (arr[i]->level == j) {
if (i == 0) cout << arr[i]->data;
else cout << ' ' << arr[i]->data;
j++;
}
}
cout << endl;
}一点也不浪漫好吗？
原文地址：https://blog.csdn.net/2301_80348267/article/details/143822900
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！