资源下载网站wordpress,wordpress百度主动推送代码,安徽万户网络,wordpress 儿童主题题目一#xff1a;DS树 -- 树的先根遍历#xff08;双亲转先序#xff09;
题目描述#xff1a;
给出一棵树的双亲表示法结果#xff0c;用一个二维数组表示#xff0c;位置下标从0开始#xff0c;如果双亲位置为-1则表示该结点为根结点
编写程序#xff0c;输出该树…题目一DS树 -- 树的先根遍历双亲转先序
题目描述
给出一棵树的双亲表示法结果用一个二维数组表示位置下标从0开始如果双亲位置为-1则表示该结点为根结点
编写程序输出该树的先根遍历结果。
输入要求
第一个输入t表示有t棵树
接着每棵树输入3行
第1行输入n表示树有n个结点
第2行输入n个英文字母表示每个树结点的数值
第3行输入n个整数表示每个结点的双亲在数组的下标
以此类推输入下一棵树
输出要求
共输出t行每行输出一棵树的先根遍历结果
输入样例
2
7
A B C D E F G
-1 0 0 0 1 1 3
10
A B C D R E F G H K
4 4 4 0 -1 0 2 6 6 6输出样例
ABEFCDG
RADEBCFGHK
代码示例
#include iostream
#include string
#include cstring
#include iomanip
#include algorithm
#include cmath
#include queue
using namespace std;const int N 10010;struct TNode {char data;int parent;
};struct Tree {TNode node[N];int n;
};void CreateTree(Tree t) {cin t.n;for (int i 0; i t.n; i) cin t.node[i].data;for (int i 0; i t.n; i) cin t.node[i].parent;
}void PreOrder(Tree t, int x) {for (int i 0; i t.n; i) {if (t.node[i].parent x) {cout t.node[i].data;PreOrder(t, i);}}
}
int main() {int t;cin t;while (t--) {Tree tree;CreateTree(tree);PreOrder(tree, -1);cout endl;}
}
题目二DS树 -- 树的后根遍历孩子链表法
题目描述
根据树的孩子链表表示法构建一棵树并输出树的后根遍历
下标位置从0开始
输入要求
第一行输入两个参数第一个参数n表示树有n个结点第二个参数r表示根结点的数组下标
接着n行每行先输入一个结点的数值用单个字母表示再输入结点的孩子的下标最后以-1结尾
如果该结点没有孩子则一行只输入结点的数值和-1
输出要求
只有一行输出树的后根遍历结果
输入样例
10 4
A 3 5 -1
B -1
C 6 -1
D -1
R 0 1 2 -1
E -1
F 7 8 9 -1
G -1
H -1
K -1输出样例
DEABGHKFCR
代码示例
#include iostream
#include string
#include cstring
#include iomanip
#include algorithm
#include cmath
#include queue
using namespace std;const int N 110;struct TNode {char data;int child[110];
};struct Tree {TNode node[N];
};void CreateTree(Tree t, int n) {for (int i 0; i n; i) {cin t.node[i].data;for (int j 0;; j) {cin t.node[i].child[j];if (t.node[i].child[j] -1) break;}}
}void Postorder(Tree t, int x) {for (int i 0; t.node[x].child[i] ! -1; i) Postorder(t, t.node[x].child[i]);cout t.node[x].data;
}int main() {int n, r;cin n r;Tree tree;CreateTree(tree, n);Postorder(tree, r);cout endl;return 0;
}
题目三DS树 -- 树结构转换先序转双亲
题目描述
给出一棵二叉树的特定字符先序遍历结果空子树用字符#表示构建该二叉树并输出该二叉树的双亲表示法结果
双亲表示法的数组下标从0开始根结点必定是在下标0元素且根结点的双亲下标为-1左右孩子按下标递增顺序排列,
结点下标是层次遍历顺序。
输入要求
第一个输入t表示有t棵二叉树
接着t行每行输入含特定字符的二叉树先序遍历序列
输出要求
共输出2t行
每棵二叉树输出两行第一行输出各个结点的数值第二行输出各结点的双亲下标
输入样例
3
AB#C##D##
ABD##E##C##
AB##CDW###E#F##
输出样例
A B D C
-1 0 0 1
A B C D E
-1 0 0 1 1
A B C D E W F
-1 0 0 2 2 3 4
代码示例
#include iostream
#include string
#include cstring
#include iomanip
#include algorithm
#include cmath
#include queue
using namespace std;struct BNode {char data;BNode* lChild;BNode* rChild;BNode* Parent;
};class BTree {
public:BNode* root;BNode* node[100];int pos[100];//双亲下标int len;//两个数组的长度BTree() :root(NULL) {}BNode* creatBTree(BNode* father) {BNode* tmp;char ch;cin ch;if (ch #) tmp NULL;else {tmp new BNode;tmp-data ch;tmp-Parent father;tmp-lChild creatBTree(tmp);tmp-rChild creatBTree(tmp);}return tmp;}int findNode(BNode* btn){if (btn NULL) return -1;for (int i 0; i 100; i) if (btn node[i]) return i;}void BFS(){queueBNode* q;int index 0;if (root ! nullptr) {q.push(root);while (!q.empty()) {node[index] q.front();pos[index] findNode(q.front()-Parent);index;if (q.front()-lChild ! NULL) q.push(q.front()-lChild);if (q.front()-rChild ! NULL) q.push(q.front()-rChild);q.pop();}}len index;}void Display(){for (int i 0; i len; i) {cout node[i]-data;if (i len - 1) cout endl;else cout ;}for (int i 0; i len; i){cout pos[i];if (i len - 1) cout endl;else cout ;}}
};int main() {int t;cin t;while (t--) {BTree tree;tree.root tree.creatBTree(NULL);tree.BFS();tree.Display();}
}
题目四DS树 -- 树结构转换双亲转孩子链表
题目描述
给出一棵树的双亲表示法结果用一个二维数组表示位置下标从0开始如果双亲位置为-1则表示该结点为根结点
编写程序输出该树的孩子链表表示法结果。
输入要求
输入一棵树的双亲表示法共3行
第1行输入n表示树有n个结点
第2行输入n个英文字母表示每个树结点的数值
第3行输入n个整数表示每个结点的双亲在数组的下标
输出要求
按输入的结点顺序输出n行每行输出结点孩子链表结果先输出结点的数值再输出结点的孩子的下标以空格隔开最后一个数据后面也有空格
如果链表为空则输出结点数值后输出-1带空格具体看样式
输入样例
7
A B C D E F G
-1 0 0 0 1 1 3
输出样例
A 1 2 3
B 4 5
C -1
D 6
E -1
F -1
G -1
代码示例
#include iostream
#include string
#include cstring
#include iomanip
#include algorithm
#include cmath
#include queue
using namespace std;const int N 110;struct TNode {char data;int parent;
};struct Tree {TNode node[N];int n;
};void createTree(Tree tree) {cin tree.n;for (int i 0; i tree.n; i) cin tree.node[i].data;for (int i 0; i tree.n; i) cin tree.node[i].parent;
}void Display(Tree tree) {for (int i 0; i tree.n; i) {cout tree.node[i].data ;bool mark false;for (int j 0; j tree.n; j) {if (tree.node[j].parent i) {mark true;cout j ;}}if (!mark) cout -1 ;cout endl;}
}int main() {Tree tree;createTree(tree);Display(tree);
}
题目五DS树 -- 森林叶子编码
题目描述
给定一组森林编写程序生成对应的二叉树输出这颗二叉树叶结点对应的二进制编码.规定二叉树的左边由0表示二叉树的右边由1表示。
输入要求
N B 表示N个树每结点最多B个分支
第2行至第N1行每个树的先序遍历
输出要求
每行表示一个叶结点对应的二进制编码
输入样例
3 3
A B 0 0 0 C 0 0 0 D 0 0 0
E F 0 0 0 0 0
G H 0 0 0 I J 0 0 0 0 0 0输出样例
0 1 1
1 0
1 1 0 1 0
代码示例
#include iostream
#include string
#include cstring
#include iomanip
#include algorithm
#include cmath
using namespace std;int B, N;struct BTNode {char data;BTNode* lChild;BTNode* rChild;
};struct TNode {char e;TNode** Child;TNode() {Child new TNode * [B];for (int i 0; i B; i) Child[i] NULL;}
};
class Tree {
private:TNode* root;//创建一般树TNode* createTree() {TNode* T NULL;char ch;cin ch;if (ch ! 0) {T new TNode();T-e ch;for (int i 0; i B; i) T-Child[i] createTree();}return T;}//转化成根节点没有右子树的二叉树BTNode* Trans(TNode* T) {BTNode* p NULL;if (T){p new BTNode;p-data T-e;int cnt 0;while (!T-Child[cnt] cnt B) cnt;if (cnt B) p-lChild Trans(NULL);else p-lChild Trans(T-Child[cnt]);if (p-lChild){BTNode* q p-lChild;for (int i cnt 1; i B; i){q-rChild Trans(T-Child[i]);if (q-rChild) q q-rChild;}}}return p;}
public://生成树void Create() { root createTree(); }BTNode* Trans() { return Trans(root); }
};
class BTree {
private:BTNode* root;//二叉树的编码输出void print(BTNode* t, string s) {if (t) {if (t-lChild NULL t-rChild NULL) {s s.substr(0, s.size() - 1);cout s endl;}print(t-lChild, s 0 );print(t-rChild, s 1 );}}
public:BTree() {}//将森林合成二叉树void emerge(BTNode** t) {root t[0];for (int i 0; i N - 1; i) t[i]-rChild t[i 1];}//编码输出void print() {string str ;print(root, str);}
};int main() {cin N B;Tree* ts new Tree[N];BTNode** btn new BTNode * [N];//读取一般树for (int i 0; i N; i) ts[i].Create();//把每个一般树转化成不含有右子树二叉树for (int i 0; i N; i) btn[i] ts[i].Trans();BTree btree;//将不含右子树的二叉树合并btree.emerge(btn);btree.print();return 0;
}
题目六先序中序还原二叉树
题目描述
给定一棵二叉树的先序遍历序列和中序遍历序列要求计算该二叉树的高度。
输入要求
输入首先给出正整数N≤50为树中结点总数。下面两行先后给出先序和中序遍历序列均是长度为N的不包含重复英文字母区别大小写的字符串。
输出要求
输出为一个整数即该二叉树的高度。
输入样例
9
ABDFGHIEC
FDHGIBEAC
输出样例
5
代码示例
简单求解只针对还原后求高度
#include iostream
using namespace std;int DFS(char* pre, char* in, int n) {if (n 0) return 0;int i;for (i 0; i n; i) if (in[i] pre[0]) break;int left DFS(pre 1, in, i);int right DFS(pre i 1, in i 1, n - i - 1);return max(left, right) 1;
}int main() {int n;cin n;char* pre new char[n];char* in new char[n];cin pre in;cout DFS(pre, in, n);return 0;
}
正常还原树方法
#include iostream
#include string
#include cstring
#include iomanip
#include algorithm
#include cmath
#include queue
using namespace std;struct BNode {char data;BNode* lChild;BNode* rChild;
};class BTree {
public:BNode* root;BTree() :root(NULL) {}BNode* creatBTree() {BNode* tmp;char ch;cin ch;if (ch 0) tmp NULL;else {tmp new BNode;tmp-data ch;tmp-lChild creatBTree();tmp-rChild creatBTree();}return tmp;}void Preorder(BNode* cur) {if (cur ! NULL) {cout cur-data;Preorder(cur-lChild), Preorder(cur-rChild);}}void Inorder(BNode* cur) {if (cur ! NULL) {Inorder(cur-lChild);cout cur-data;Inorder(cur-rChild);}}void Postorder(BNode* cur) {if (cur ! NULL) {Postorder(cur-lChild), Postorder(cur-rChild);cout cur-data;}}int TreeHeight(BNode* cur) {if (cur NULL) return 0;else return max(TreeHeight(cur-lChild), TreeHeight(cur-rChild)) 1;}BNode* getTree(vectorchar preStr, vectorchar inStr) {if (preStr.empty()) return NULL;BNode* root new BNode();root-data preStr[0];vectorchar::iterator mid find(inStr.begin(), inStr.end(), preStr[0]);int left_nodes mid - inStr.begin();vectorchar left_inStr(inStr.begin(), mid);vectorchar right_inStr(mid 1, inStr.end());vectorchar left_preStr(preStr.begin() 1, preStr.begin() 1 left_nodes);vectorchar right_preStr(preStr.begin() 1 left_nodes, preStr.end());root-lChild getTree(left_preStr, left_inStr);root-rChild getTree(right_preStr, right_inStr);return root;}
};vectorchar getCharArray(string str) {vectorchar res;for (char c : str) res.push_back(c);return res;
}int main() {string preOrder;string inOrder;int nodeCount;//本题给出了结点总数要求输入那就输出进来防止报错实际并没有用到cin nodeCount;cin preOrder inOrder;vectorchar preStr getCharArray(preOrder);vectorchar inStr getCharArray(inOrder);BTree tree;tree.root tree.getTree(preStr, inStr);cout tree.TreeHeight(tree.root) endl;return 0;
}
根据后序中序还原二叉树先输入后序结果
#include iostream
#include string
#include cstring
#include iomanip
#include algorithm
#include cmath
#include queue
using namespace std;struct BNode {char data;BNode* lChild;BNode* rChild;
};class BTree {
public:BNode* root;BTree() :root(NULL) {}BNode* creatBTree() {BNode* tmp;char ch;cin ch;if (ch 0) tmp NULL;else {tmp new BNode;tmp-data ch;tmp-lChild creatBTree();tmp-rChild creatBTree();}return tmp;}void Preorder(BNode* cur) {if (cur ! NULL) {cout cur-data;Preorder(cur-lChild), Preorder(cur-rChild);}}void Inorder(BNode* cur) {if (cur ! NULL) {Inorder(cur-lChild);cout cur-data;Inorder(cur-rChild);}}void Postorder(BNode* cur) {if (cur ! NULL) {Postorder(cur-lChild), Postorder(cur-rChild);cout cur-data;}}int TreeHeight(BNode* cur) {if (cur NULL) return 0;else return max(TreeHeight(cur-lChild), TreeHeight(cur-rChild)) 1;}BNode* getTree(vectorchar postStr, vectorchar inStr) {if (postStr.empty()) return NULL;BNode* root new BNode();root-data postStr[postStr.size() - 1];vectorchar::iterator mid find(inStr.begin(), inStr.end(), postStr[postStr.size() - 1]);int left_nodes mid - inStr.begin();vectorchar left_inStr(inStr.begin(), mid);vectorchar right_inStr(mid 1, inStr.end());vectorchar left_postStr(postStr.begin(), postStr.begin() left_nodes);vectorchar right_postStr(postStr.begin() left_nodes , postStr.end() - 1);root-lChild getTree(left_postStr, left_inStr);root-rChild getTree(right_postStr, right_inStr);return root;}
};vectorchar getCharArray(string str) {vectorchar res;for (char c : str) res.push_back(c);return res;
}int main() {string postOrder;string inOrder;cin postOrder inOrder;vectorchar postStr getCharArray(postOrder);vectorchar inStr getCharArray(inOrder);BTree tree;tree.root tree.getTree(postStr, inStr);tree.Preorder(tree.root);cout endl;return 0;
}
