二叉树应用-折纸问题

六月丶

发布于 2022-12-26 17:46:42

20300

代码可运行

文章被收录于专栏：六月-游戏开发六月-游戏开发

运行总次数：0

代码可运行

题目

一道微软以前的面试题，题目大概是，用一张长条纸，将其中一面保持对向自己，将它向上对折一次，展开后会有一个凹的折痕，而对折一次时再向上对折一次，展开后有三条折痕，从上到下为凹凹凸，以此类推，求向上对折n次展开后从上至下的凹凸顺序。

思路

如果反复实验会发现一个规律，第一次对折会生成一个凹折痕，此后每次对折会在现有的每个折痕上边加一个凹折痕，下边加一个凸折痕。所以可以用二叉树结构来做这题，对折n次就生成一个高n的满二叉树，头节点为凹，每个左节点为凹，每个右节点为凸，然后来一遍中序遍历打印即可。

代码

#include<iostream>
#include<string>
#include<queue>
using namespace std;

struct Node{
    string value;
    Node *left = NULL;
    Node *right = NULL;
};
Node *getNode(string value);
//根据对折次数返回一颗二叉树 
Node *getTree(int n){
    if(n<1)return NULL;
    int t = 1;
    Node *tree = getNode("凹");
    queue<pair<Node *,int> > que;
    que.push(make_pair(tree,1));
    while(t<n){
        pair<Node *,int> pair = que.front();
        if(pair.second==n)break;
        que.pop();
        Node *tmp = pair.first;
        tmp->left = getNode("凹");
        tmp->right = getNode("凸");
        que.push(make_pair(tmp->left,pair.second+1));
        que.push(make_pair(tmp->right,pair.second+1));
    }
    return tree;
}
//中序遍历 
void midPrint(Node *tree){
    if(tree==NULL)return;
    midPrint(tree->left);
    cout << tree->value << " ";
    midPrint(tree->right);
}
int main(){
    Node *tree;
    int n;
    cin >> n;
    tree = getTree(n);
    midPrint(tree);

    return 0;
}
Node *getNode(string value){
    Node *p = new Node();
    p->value = value;
    return p;
}

但其实可以用更简便的方式，不需要特意生成二叉树，直接把按中序遍历改一下即可，代码如下：

#include<iostream>
using namespace std;
//（层数，对折次数也是最大层数，是否打印凹）
void printAllFolds(int i,const int N,bool down){
    if(i>N)return;
    printAllFolds(i+1,N,true);
    cout << (down?"凹":"凸");
    printAllFolds(i+1,N,false);
} 

int main(){
    int n;
    cin >> n;
    printAllFolds(1,n,true);

    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020 年 04 月，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树