Interview questions
二叉树的构建
#include<iostream>
#include<vector>
#include<string>
#include<queue>
using namespace std;
struct Node{
char data;
Node* left ;
Node* right ;
Node(){
data = ' ';
left = nullptr;
right = nullptr;
}
Node(char a){
data = a;
left = nullptr;
right = nullptr;
}
};
// 创建二叉树
//注意这里是传指针的指针，或者指针的引用 为什么？
//如果是传指针，传指针本质也是值传递，就是拷贝一份指针，
//如果给指针赋值，也只是对拷贝的指针赋值，而对原来的指针没有影响。
//数组中 假设 索引下标 i 为根结点 左孩子的下标为2*i+1, 右孩子的下标为2*i+2
void createTree(Node *&root, int i, string& tree,int& length)
{
if(i > length-1 || tree[i] == '#')//#表示值为空
return ;
root = new Node(tree[i]);
createTree(root->left, 2*i+1, tree,length);
createTree(root->right, 2*i+2, tree,length);
}
// 前序打印
void prePrintTree(Node *root)
{
if(root == nullptr)
return ;
cout<<root->data;
prePrintTree(root->left);
prePrintTree(root->right);
}
// 中序打印
void inPrintTree(Node *root)
{
if(root == nullptr)
return ;
inPrintTree(root->left);
cout<<root->data;
inPrintTree(root->right);
}
// 后序打印
void postPrintTree(Node *root)
{
if(root == nullptr)
return ;
postPrintTree(root->left);
postPrintTree(root->right);
cout<<root->data;
}
void levelPrintTree(Node *root){
if(root == nullptr)
return;
queue<Node*> q;
q.push(root);
while(!q.empty()){
int level_s = q.size();
for(int i=0;i<level_s;i++){
cout<<q.front()->data;
if(q.front()->left) q.push(q.front()->left);
if(q.front()->right) q.push(q.front()->right);
q.pop();
}
cout<<endl;
}
}
int main(){
string tree = "ABC#DEF";
Node *head = nullptr;
int length = sizeof(tree);
createTree(head, 0, tree,length);
cout<<"prePrintTree"<<endl;
prePrintTree(head);
cout<<endl;
cout<<"inPrintTree"<<endl;
inPrintTree(head);
cout<<endl;
cout<<"postPrintTree"<<endl;
postPrintTree(head);
cout<<endl;
cout<<"levelPrintTree"<<endl;
levelPrintTree(head);
cout<<endl;
return 0;
}
打印三角形
*
***
*****
*******
*********
--------------------------------
Process exited after 0.02422 seconds with return value 0
请按任意键继续. . .我们怎么才能做到这样呢？
1、首先分析图形的结构
我们可以看到，图形共5行，那么，我们是否可以建立一个for循环语句，使其控制在5行？答案是肯定的。
for(int i = 1 ;i <= 5 ;i++ ){
}2、然后，分析图形是怎样构成的，我们可以把图形拆分为以下几部分：
1 *
** *
*** **
**** ***
***** ****
2 3我们可以把图形拆分为这样三个三角形。
3、建立1号空白三角形
可以看，第一行是输出4个空格，第二行输出3个空格，第三行输出2个，第四行输出1个，第五行没有
从这个规律可以看出，是依次递减的规律，那么如何实现呢？
我们可以想象从1到5，中间有四个数字；从2到5中间有3个数字，从3到5……
是不是可以利用这个原理呢？答案是当然的。那么如何实现？请看代码：
for(int i = 1;i<=5 ;i++) {
for(int j = 5; j >= i ; j--)//建立1号图形
cout<<" ";
cout<<endl;
}第一个for语句就是刚才定义的五次循环语句
第二个for循环，我们来进行解析:
首先 定义一个int类型的j变量，给j赋值为5
然后我们想，既然要缩短距离，那么每次循环j就-1，那么刚好符合我们的要求：
第一次大循环 i=1，j=5, 所以符合j>=i的条件然后输出一个空格，然后j-1，现在j的值为4符合j>=i,再输出
……
一直到j=0,j>=i不符合，跳出内循环
现在到cout<<endl; 换行
现在回到外循环 i++ ,i变成2，符合i<=5,进入内循环
定义j=5 , j>=i,符合，输出一个空格，j-1
j现在为4 ，j>=i，符合，输出一个空额，j-1
……
一直到j=1,j>=i，不成立，跳出内循环，然后换行
然后i+1 然后再进入内循环……
如此循环下去 形成了一个四行的倒三角，1号图案形成。
4、建立2号图形，和1号图形原理完全相同，不过正好相反
for(int i = 1 ;i<=5 ;i++){
for(int j = 5; j >= i ; j--)//建立1号图形
cout<<" ";
for(int j = 1; j <= i; j++)//建立2号图形
cout<<"*";
cout<<endl;
}如建立1号图形相同,大家可以自己理解，如此2号建立
5、建立3号图形
for(int i = 1; i <= 5; i++){
for(int j = 5 ;i <= j; j--)//建立1号图形
cout<<" ";
for(int j = 1; j <= i; j++)//建立2号图形
cout<<"*";
for(int j = 1; j < i; j ++)//建立3号图形
cout<<"*";
}同样，如同1号二号相同，建立3号图形原理相同
但是大家注意一点，3号图形没有在第一行输出，所以要在第一次大循环中掐断它，让它在第二次大循环中输出
所以 这次的判断条件为 j < i 去掉了等于。
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main(){
// int n;
// cin>>n;
for(int i=1;i<=5;i++){
for(int j=5; i<=j; j--)
cout<<(" ");
for(int j=1; j<=i; j++)
cout<<("*");
for(int j=1; j<i; j++)
cout<<("*");
cout<<endl;
}
return 0;
}