机试准备第14天

首先进行树的学习。树的存储分为链式存储与顺序存储。完全二叉树是可以顺序存储的，将各个节点从上往下，从左往右存储。

第一题是找位置，好兄弟给的一道题，一遍过了。

#include <stdio.h>
#include <map>
#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;
struct word{char a;int firstpos;
};
bool cmp(word left, word right){if(left.firstpos < right.firstpos) return true;else return false;
}
int main(){string str;getline(cin, str);map<char, int> repeat;//初始化repeatfor(char i = 'a'; i < 'z';i++){repeat.insert({i, 0});}for(char i = 'A'; i < 'Z';i++){repeat.insert({i, 0});}for(char i = '1'; i < '9';i++){repeat.insert({i, 0});}for(int i = 0; i<str.size();i++){repeat[str[i]]++;}vector<char> rep;//重复元素数组map<char, int>::iterator it;for(it = repeat.begin();it!=repeat.end();it++){if(it->second > 1) rep.push_back(it->first);}vector<word> rep2;//记录重复元素的第一次出现位置for(int i = 0;i<rep.size();i++){word val;val.a = rep[i];for(int j = 0; j<str.size();j++){if(str[j] == rep[i]){val.firstpos = j;break;}}rep2.push_back(val);}sort(rep2.begin(), rep2.end(),cmp);for(int i = 0; i <rep2.size();i++){printf("%c:%d", rep2[i].a, rep2[i].firstpos);for(int j = (rep2[i].firstpos+1); j < str.size();j++){if(str[j] == rep2[i].a) {printf(",%c:%d", rep2[i].a, j);}}printf("\n");}}

第二题是二叉树。

#include <stdio.h>using namespace std;int main() {int m, n;while (1) {scanf("%d%d", &m, &n);if (m == 0 && n == 0) {break;}int i = 1; // 获取层数 从1开始int begin_level; // 存储子树的根在第几层int final_level; // 大树总共有几层// 2^(i-1) ~ 2^i-1// 1 << i ==> 2^iwhile (1) {if (m >= 1 << (i - 1) && m < 1 << i) {begin_level = i;}if (n >= 1 << (i - 1) && n < 1 << i) {final_level = i;break;}++i;}int left_side = m;int right_side = m;for (i = begin_level; i < final_level; ++i) {left_side = 2 * left_side;right_side = 2 * right_side + 1;}int treeNum;// left_side > n 说明 实际的最左最右孩子在倒数第2层// 子树 是一颗 从 begin_level ~ final_level-1 满二叉树if (left_side > n) {treeNum = (1 << (final_level - begin_level)) - 1;}else if (n <= right_side) {treeNum = (1 << (final_level - begin_level)) - 1;treeNum += n - left_side + 1;}else {treeNum = (1 << (final_level - begin_level + 1)) - 1;}printf("%d\n", treeNum);}return 0;}

链式存储的树节点，包含数据域与指针域，指针域分为left与right，指向左右孩子。使用struct定义节点类型。层序建树时要使用队列维持插入位置的信息。层序建树的步骤：1.创建树节点，作为根节点插入，将其left与right位置入队。2.再来新的数据，若数据不是“#”，创建树节点，获取对首，出队，根据对首做插入。新节点的left right位置也要入队。若数据是“#”，直接出队。

#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;
struct Treenode{char data;Treenode *left;//这里必须用指针 我们已知指针的长度Treenode *right;//Treenode *parent;
};
struct QueueNode{Treenode* parent;bool isleft;
};
void buildTree(Treenode* &proot, queue<QueueNode *> &pos, char data){if(data != '#' ){//  申请一个树节点Treenode * pNew = new Treenode;//(*pNew).data = data;//点的优先级高于*号pNew->data = data;//->与(*).是等价的//申请一个队列的节点QueueNode * pQueueNode = new QueueNode;pQueueNode->parent = pNew;//在队列节点中，保存刚创建的新节点位置pQueueNode->isleft = false;pos.push(pQueueNode);if(proot == NULL){//插入根节点proot = pNew;}else {QueueNode * pCur = pos.front();if(pCur->isleft == false){pCur->parent->left = pNew;pCur->isleft = true;}else {pCur->parent->right = pNew;pos.pop();delete pCur;}}}else {if(proot != NULL){QueueNode* pCur = pos.front();if(pCur->isleft == false){pCur->parent->left =NULL;pCur->isleft = true;}else {pCur->parent->right == NULL;pos.pop();delete pCur;}}}
}
int main(){Treenode* proot = NULL;//有一个指向根节点的指针//若proot为NULL，说明这是一个空树char data;queue<QueueNode*> pos;while(1){scanf("%c", &data);if(data=='\n') break;buildTree(proot, pos, data);}return 0;
}

下面学习树的遍历。分为挂广度优先与深度优先。广度优先即层序遍历，利用队列辅助遍历，深底优先需要借助递归机制，有先序（根左右），中序（左根右），后序（左右根）之分。

层序遍历：

void levelOrder(Treenode *proot){queue<Treenode*> pos;pos.push(proot);while(!pos.empty()){Treenode *pCur = pos.front();pos.pop();printf("%c", pCur->data);if(pCur->left!=NULL) pos.push(pCur->left);if(pCur->right!=NULL) pos.push(pCur->right);}printf("\n");
}

深度遍历：

void PreOrder(Treenode * proot){if(proot == NULL) return;else {printf("%c", proot->data);PreOrder(proot->left);PreOrder(proot->right);}
}
void Inorder(Treenode * proot){if(proot == NULL) return;else {Inorder(proot->left);printf("%d", proot->data);Inorder(proot->right);}
}
void PostOrder(Treenode * proot){if(proot == NULL) return;else {PostOrder(proot->right);PostOrder(proot->left);printf("%d",proot->data);}
}

第三题是二叉树。先构建树，在找节点到根的路径，找交点，距离求和。

#include <stdio.h>
#include <vector>
using namespace std;
struct Treenode{int data;Treenode* left;Treenode* right;Treenode* parent;
};
int main(){int T;scanf("%d", &T);for(int i = 0; i<T;i++){int n,m;scanf("%d%d", &n, &m);vector<Treenode*> nodearr(n+1);for(int j = 1; j<=n;j++){nodearr[j] = new Treenode;nodearr[j]->data = j;}nodearr[1]->parent = NULL;for(int j =1;j<=n;j++){int left,right;scanf("%d%d", &left, &right);if(left!=-1){nodearr[j]->left = nodearr[left];nodearr[left]->parent = nodearr[j];}else{nodearr[j]->left =NULL;}if(right!=-1){nodearr[j]->right = nodearr[right];nodearr[right]->parent = nodearr[j];}else nodearr[j]->right =NULL;}int lhs, rhs;for(int j = 0;j<m;j++){scanf("%d%d", &lhs,&rhs);vector<int> lvec;//得到节点到根的路径vector<int> rvec;Treenode*p = nodearr[lhs];while(p!=NULL){lvec.push_back(p->data);p = p->parent;}p = nodearr[rhs];while(p!=NULL){rvec.push_back(p->data);p = p->parent;}int l = lvec.size()-1;int r = rvec.size()-1;while(1){if(l<0||r<0||lvec[l]!=rvec[r]){break;}--l;--r;}printf("%d\n", l+r+2);}}
}

第四题是二叉树遍历。使用分治法，首先扫描序列，然后读取字符，想要构建树，先设置根，设置左子树，设置右子树。不断分解直到扫描到空叶子"#"。

#include <stdio.h>
using namespace std;
struct TreeNode{char data;TreeNode* left;TreeNode* right;
};
TreeNode* bulitTree(int &i, char str[]){char c = str[i];i++;if(c=='#'){return NULL;}else {TreeNode* pNew = new TreeNode;pNew->data = c;pNew->left = bulitTree(i,str);pNew->right = bulitTree(i, str);return pNew;}
}
void Inorder(TreeNode* root){if(root == NULL){return;}else{Inorder(root->left);printf("%c ", root->data);Inorder(root->right);}
}
int main()
{char str[1000];while(scanf("%s", str)!=EOF){int i =0;TreeNode* proot = bulitTree(i, str);Inorder(proot);printf("\n");}return 0;
}

第五题是重建二叉树。经典老题。已知先序，先找到根，拿根找中序，分解原来的先序与中序，递归处理。

#include <stdio.h>
#include <string>
using namespace std;
struct Treenode{char data;Treenode* left;Treenode* right;
};
Treenode* rebuild(string Preorder, string Inorder){if(Preorder.size() == 0) return NULL;else {char rootdata = Preorder[0];Treenode* node = new Treenode;node->data = rootdata;int pos;for(int i = 0; i< Inorder.size();i++){if(rootdata == Inorder[i]) pos = i;}node->left = rebuild(Preorder.substr(1, pos), Inorder.substr(0, pos));node->right = rebuild(Preorder.substr(pos+1), Inorder.substr(pos+1));return node;}
}
void Postorder(Treenode * root){if(root == NULL){return;}else{Postorder(root->left);Postorder(root->right);printf("%c", root->data);}
}
int main(){char Preorder[30];char Inorder[30];while(scanf("%s%s", Preorder, Inorder)!=EOF){string Preorder1 = Preorder;string Inorder2 = Inorder;Treenode* root = rebuild(Preorder1, Inorder2);Postorder(root);printf("\n");}}

第六题是二叉树。

#include <stdio.h>
#include <vector>
using namespace std;
int main(){int x,y;scanf("%d%d", &x, &y);vector<int> res1;vector<int> res2;if(x==1||y==1) {printf("1");return 0;}else{while(x>1){res1.push_back(x);x=x/2;}res1.push_back(1);while(y>1){res2.push_back(y);y=y/2;}res2.push_back(1);//找到第一个不相等的位置int l = res1.size()-1;int r = res2.size()-1;while(1){if(l<0||r<0||res1[l]!=res2[r]) break;l--;r--;}if(l<0) {printf("%d", res1[0]);return 0;}else if(r<0){printf("%d", res2[0]);return 0;}else {printf("%d", res1[l+1]);return 0;}}
}

第七题是树查找，是找数学关系的一道题。

#include <stdio.h>
#include <vector>
using namespace std;
int main(){int n;scanf("%d", &n);vector<int> vec(n+1);for(int i = 1;i<=n;i++){scanf("%d", &vec[i]);}int k;scanf("%d", &k);//第k层的节点编号为2^(k-1) ~ 2^k - 1int left = 1<<(k-1);int right = (1<<k)-1;if(left>n) printf("EMPTY");else if(left<=n&&right>=n) {while(left<=n){printf("%d ", vec[left]);left++;}}else if(n>right){for(int i =left;i<=right;i++){printf("%d ", vec[i]);}}
}

第八题是前序遍历。爆内存了。

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
struct Treenode{int data;Treenode* left;Treenode* right;
};
Treenode* built(vector<int> Postorder, vector<int> Inorder){if(Postorder.size() == 0) return NULL;else {int rootdata = Postorder[Postorder.size()-1];int pos =0;//根节点在中序序列中的位置for(int i = 0;i<Inorder.size();i++){if(Inorder[i] == rootdata){pos = i;break;} }Treenode* proot = new Treenode;proot->data = rootdata;vector<int> newPosterosderleft;vector<int> newPosterosderright;vector<int> newInorderleft;vector<int> newInorderright;for(int i = 0;i<pos;i++){newInorderleft.push_back(Inorder[i]);}for(int i = pos+1;i<Inorder.size();i++){newInorderright.push_back(Inorder[i]);}for(int i = 0; i<newInorderleft.size();i++){newPosterosderleft.push_back(Postorder[i]);}for(int i = newPosterosderleft.size();i<Postorder.size()-1;i++){newPosterosderright.push_back(Postorder[i]);}proot->left = built(newPosterosderleft, newInorderleft);proot->right = built(newPosterosderright, newInorderright);return proot;}
}
void Preorder(Treenode* root, int &num){if(root == NULL) return;else{num = root->data;//printf("%d", num);Preorder(root->left, num);Preorder(root->right, num);}
}
int main(){int n;scanf("%d", &n);vector<int> Postorder(n);vector<int> Inorder(n);for(int i = 0;i<n;i++){scanf("%d", &Postorder[i]);}for(int i = 0;i<n;i++){scanf("%d", &Inorder[i]);}//读入序列Treenode* root= built(Postorder, Inorder);int res=0;Preorder(root, res);printf("%d", res);
}