二叉树应用-折纸问题

题目

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

思路

如果反复实验会发现一个规律,第一次对折会生成一个凹折痕,此后每次对折会在现有的每个折痕上边加一个凹折痕,下边加一个凸折痕。所以可以用二叉树结构来做这题,对折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;
}
本文作者:六月丶

本文链接:https://hctra.cn/index.php/archives/604/

版权声明:如无特别声明,本文即为六月'blog原创,仅代表个人观点,如要转载请务必注明文章出处。
最后修改:2020 年 04 月 20 日 05 : 46 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论