二叉树（中南大学）

二叉树的先序序列查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 256 mb已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历但已知先序和后序却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及后序遍历结果要求输出其先序遍历结果。输入输出格式输入描述:第一行为中序序列 第二行为后续序列输出描述:输出为遍历二叉树得到的先序序列输入输出样例输入样例#:复制BFDAEGC FDBGECA输出样例#:复制ABDFCEG题目来源中南大学机试习题#includebits/stdc.h using namespace std; struct TreeNode{ char data; struct TreeNode *left; struct TreeNode *right; TreeNode(int val) : data(val), left(NULL), right(NULL){} }; void LevelOrder(TreeNode* root){ if(root NULL){ coutYendl; return; } queueTreeNode*s; bool total true; s.push(root); while(!s.empty()){ TreeNode* p s.front(); s.pop(); if(p NULL){//是空的就标记 total false; } else{ if(total false){ coutNendl; return; } s.push(p-left); s.push(p-right); } } coutYendl; return; } void preOrder(string in, string post){ if(in || post ){ return; } int n post.size(); char str post[n - 1]; int pos in.find(str); coutstr; preOrder(in.substr(0, pos), post.substr(0, pos));//pos是第4个 substr切割不包含pos preOrder(in.substr(pos 1), post.substr(pos, post.size() - pos - 1)); return; } int main() { int n; string in, post; while(cininpost){ // n post.size(); // char str post[n - 1]; // int pos in.find(str); // coutstr; // preOrder(in.substr(0, pos), post.substr(0, pos));//pos是第4个 substr切割不包含pos // preOrder(in.substr(pos 1), post.substr(pos, post.size() - pos - 1)); preOrder(in, post); coutendl; // BFDAEGC // FDBGECA } }二叉树的后序序列查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 256 mb已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历但已知先序和后序却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及先序遍历结果要求输出其后序遍历结果。输入输出格式输入描述:输入数据占2行其中第一行表示中序遍历结果第二行为先序遍历结果。输出描述:对测试数据输出后序遍历结果。输入输出样例输入样例#:复制BFDAEGC ABDFCEG输出样例#:复制FDBGECA题目来源中南大学机试习题#includebits/stdc.h using namespace std; struct TreeNode{ char data; struct TreeNode* left; struct TreeNode* right; TreeNode(int val) : data(val), left(NULL), right(NULL){} }; string result ; void preOrder(TreeNode *root){ if(root NULL){ return; } result result root-data; // cout root-data ; preOrder(root-left); preOrder(root-right); } void inOrder(TreeNode *root){ if(root NULL){ return; } inOrder(root-left); result result root-data; // cout root-data ; inOrder(root-right); } TreeNode* buildTree(string str){ } void levelOrder(TreeNode* root, int n){ if(root NULL){ coutNULLendl; return; } int count 0; queueTreeNode*s; s.push(root); while(!s.empty()){ TreeNode* p s.front(); s.pop(); count ; if(count n){ coutp-dataendl; return; } if(p-left){ s.push(p-left); } if(p-right){ s.push(p-right); } } } void postOrder(string in, string pre){ if(in || pre ){ return; } char str pre[0]; int pos in.find(str); postOrder(in.substr(0, pos), pre.substr(1, pos)); postOrder(in.substr(pos 1), pre.substr(pos 1)); coutstr; } int main(){ int n 0; string in, pre; while(cininpre){ postOrder(in, pre); coutendl; } }二叉树的深度查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 256 mb利用先序递归遍历算法创建二叉树并计算该二叉树的深度。先序递归遍历建立二叉树的方法为按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符#时表示该结点不需要创建否则创建该结点。最后再统计创建完成的二叉树的深度使用二叉树的后序遍历算法。需要注意输入数据序列中的#字符和非#字符的序列及个数关系这会最终决定创建的二叉树的形态。输入输出格式输入描述:输入为先序遍历二叉树结点序列。输出描述:对应的二叉树的深度。输入输出样例输入样例#:复制A## ABC#### AB##C## ABCD###E#F##G## A##B##输出样例#:复制1 3 2 4 1题目来源中南大学机试习题#includebits/stdc.h using namespace std; struct TreeNode{ char data; struct TreeNode* left; struct TreeNode* right; TreeNode(int val) : data(val), left(NULL), right(NULL){} }; void preOrder(TreeNode *root){ if(root NULL){ return; } // cout root-data ; preOrder(root-left); preOrder(root-right); } void inOrder(TreeNode *root){ if(root NULL){ return; } inOrder(root-left); // cout root-data ; inOrder(root-right); } int pos 0; TreeNode* buildTree(string str){ if(pos str.size()){ return NULL; } char data str[pos]; pos ; if(data #){ return NULL; } TreeNode* root new TreeNode(data); root-left buildTree(str); root-right buildTree(str); return root; } void levelOrder(TreeNode* root, int n){ if(root NULL){ coutNULLendl; return; } int count 0; queueTreeNode*s; s.push(root); while(!s.empty()){ TreeNode* p s.front(); s.pop(); count ; if(count n){ coutp-dataendl; return; } if(p-left){ s.push(p-left); } if(p-right){ s.push(p-right); } } } void postOrder(string in, string pre){ if(in || pre ){ return; } char str pre[0]; int pos in.find(str); postOrder(in.substr(0, pos), pre.substr(1, pos)); postOrder(in.substr(pos 1), pre.substr(pos 1)); coutstr; } int countDepth(TreeNode* root){ if(root NULL){ return 0; } int left countDepth(root-left); int right countDepth(root-right); return max(left, right) 1; } int main(){ int n 0; string in, pre; string str; while(cinstr){ pos 0; TreeNode* root buildTree(str); int count countDepth(root); coutcountendl; } }二叉树叶结点的个数查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 256 mb利用先序递归遍历算法创建二叉树并计算该二叉树叶结点的个数。先序递归遍历建立二叉树的方法为按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符#时表示该结点不需要创建否则创建该结点。最后再统计创建完成的二叉树叶结点的个数。需要注意输入数据序列中的#字符和非#字符的序列及个数关系这会最终决定创建的二叉树的形态。输入输出格式输入描述:接受键盘输入的由大写英文字符和#字符构成的一个字符串用于创建对应的二叉树。输出描述:输出对应的二叉树叶结点的个数。输入输出样例输入样例#:复制# A## ABC#### AB##C## ABCD###EF##G### A##B## #A输出样例#:复制0 1 1 2 3 1 0题目来源中南大学机试习题#includebits/stdc.h using namespace std; struct TreeNode{ char data; struct TreeNode *left; struct TreeNode *right; TreeNode(int val) : data(val), left(NULL), right(NULL){} }; void LevelOrder(TreeNode* root){ if(root NULL){ cout0endl; return; } queueTreeNode*s; s.push(root); int count 0; while(!s.empty()){ TreeNode* p s.front(); s.pop(); if(p-left NULL p-right NULL){ count ; } if(p-left){ s.push(p-left); } if(p-right){ s.push(p-right); } } coutcountendl; return; } void preOrder(string in, string post){ if(in || post ){ return; } int n post.size(); char str post[n - 1]; int pos in.find(str); coutstr; preOrder(in.substr(0, pos), post.substr(0, pos));//pos是第4个 substr切割不包含pos preOrder(in.substr(pos 1), post.substr(pos, post.size() - pos - 1)); return; } int pos 0; TreeNode* buildTree(string str){ if(pos str.size()){//最好写成 if(pos str.size())加个等号更安全防止访问到字符串的结束符 return NULL; } char data str[pos]; pos ; if(data #){ return NULL; } TreeNode* root new TreeNode(data); root-left buildTree(str); root-right buildTree(str); return root; } int countNode(TreeNode* root){ if(root NULL){ return 0; } if(root-left NULL root-right NULL){ return 1; } return countNode(root-left) countNode(root-right); } int main() { int n; string in, post; string str; while(cinstr){ pos 0; TreeNode* root buildTree(str); // LevelOrder(root); int count countNode(root); coutcountendl; // BFDAEGC // FDBGECA } }判断二叉树是否对称查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 256 mb层次遍历的方式输入一个二叉树判断这个二叉树的结构即不用管结点的值是否镜像对称。输入输出格式输入描述:输入一行字母其中#表示空节点字母长度小于1000。输出描述:如果输入的二叉树对称输出YES否则输出NO。输入输出样例输入样例#:复制ABC####输出样例#:复制YES题目来源东北大学机试题#includebits/stdc.h using namespace std; struct TreeNode{ char data; struct TreeNode* left; struct TreeNode* right; TreeNode(int val) : data(val), left(NULL), right(NULL){} }; void preOrder(TreeNode *root){ if(root NULL){ return; } // cout root-data ; preOrder(root-left); preOrder(root-right); } void inOrder(TreeNode *root){ if(root NULL){ return; } inOrder(root-left); // cout root-data ; inOrder(root-right); } int pos 0; TreeNode* buildTree(string str){ if(pos str.size()){ return NULL; } char data str[pos]; pos ; if(data #){ return NULL; } TreeNode* root new TreeNode(data); root-left buildTree(str); root-right buildTree(str); return root; } TreeNode* levelOrder(string str){ if(str #){ return NULL; } int count 0; queueTreeNode*s; char data str[0]; TreeNode* root new TreeNode(data); s.push(root); int i 1; while(!s.empty() i str.size()){ TreeNode* p s.front(); s.pop(); char left str[i]; if(left #){//左空 p-left NULL; } else{ p-left new TreeNode(left); s.push(p-left); } i; if(i str.size()){ break; } char right str[i]; i; if(right #){//右空 p-right NULL; } else{ p-right new TreeNode(right); s.push(p-right); } } return root; } bool mirror(TreeNode* p, TreeNode* q){ if(p NULL q NULL){ return true; } if(p NULL || q NULL){ return false; } return mirror(p-right, q-left) mirror(p-left, q-right); } void postOrder(string in, string pre){ if(in || pre ){ return; } char str pre[0]; int pos in.find(str); postOrder(in.substr(0, pos), pre.substr(1, pos)); postOrder(in.substr(pos 1), pre.substr(pos 1)); coutstr; } int countDepth(TreeNode* root){ if(root NULL){ return 0; } int left countDepth(root-left); int right countDepth(root-right); return max(left, right) 1; } int main(){ int n 0; string in, pre; string str; while(cinstr){ pos 0; TreeNode* root levelOrder(str); bool is_mirror true; is_mirror mirror(root-left, root-right); if(is_mirror) { coutYESendl; } else { coutNOendl; } } }找二叉树的最后一层的最后一个结点查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 256 mb寻找二叉树以的最后一层的最后一个结点并输出该结点的数据域的值如果是空树则输出NULL。输入输出格式输入描述:先序遍历序列输出描述:最后一个结点的值输入输出样例输入样例#:复制# ABC#### ABD##EG##H##C#FI####输出样例#:复制NULL C I题目来源中南大学机试习题#includebits/stdc.h using namespace std; struct TreeNode{ char data; struct TreeNode* left; struct TreeNode* right; TreeNode(int val) : data(val), left(NULL), right(NULL){} }; string result ; void preOrder(TreeNode *root){ if(root NULL){ return; } result result root-data; // cout root-data ; preOrder(root-left); preOrder(root-right); } void inOrder(TreeNode *root){ if(root NULL){ return; } inOrder(root-left); result result root-data; // cout root-data ; inOrder(root-right); } void postOrder(TreeNode *root){ if(root NULL){ return; } postOrder(root-left); postOrder(root-right); cout root-data ; } int pos 0; TreeNode* buildTree(string str){ if(pos str.size()){ return NULL; } char data str[pos]; pos ; if(data #){ return NULL; } TreeNode* root new TreeNode(data); root-left buildTree(str); root-right buildTree(str); return root; } void levelOrder(TreeNode* root, int n){ if(root NULL){ coutNULLendl; return; } int count 0; queueTreeNode*s; s.push(root); while(!s.empty()){ TreeNode* p s.front(); s.pop(); count ; if(count n){ coutp-dataendl; return; } if(p-left){ s.push(p-left); } if(p-right){ s.push(p-right); } } } int main(){ int n 0; string str; while(cinstr){ n 0; for(int i 0; i str.size(); i ){ if(str[i] A str[i] Z){ n ; } } pos 0;//重置一下 TreeNode* root buildTree(str); levelOrder(root, n); } }