DS|树结构及应用

题目一：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(){queue<BNode*> 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行至第N+1行，每个树的先序遍历

输出要求：

每行表示一个叶结点对应的二进制编码

输入样例：

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(vector<char>& preStr, vector<char>& inStr) {if (preStr.empty()) return NULL;BNode* root = new BNode();root->data = preStr[0];vector<char>::iterator mid = find(inStr.begin(), inStr.end(), preStr[0]);int left_nodes = mid - inStr.begin();vector<char> left_inStr(inStr.begin(), mid);vector<char> right_inStr(mid + 1, inStr.end());vector<char> left_preStr(preStr.begin() + 1, preStr.begin() + 1 + left_nodes);vector<char> 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;}
};vector<char> getCharArray(string str) {vector<char> res;for (char c : str) res.push_back(c);return res;
}int main() {string preOrder;string inOrder;int nodeCount;//本题给出了结点总数，要求输入那就输出进来，防止报错，实际并没有用到；cin >> nodeCount;cin >> preOrder >> inOrder;vector<char> preStr = getCharArray(preOrder);vector<char> 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(vector<char>& postStr, vector<char>& inStr) {if (postStr.empty()) return NULL;BNode* root = new BNode();root->data = postStr[postStr.size() - 1];vector<char>::iterator mid = find(inStr.begin(), inStr.end(), postStr[postStr.size() - 1]);int left_nodes = mid - inStr.begin();vector<char> left_inStr(inStr.begin(), mid);vector<char> right_inStr(mid + 1, inStr.end());vector<char> left_postStr(postStr.begin(), postStr.begin() + left_nodes);vector<char> 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;}
};vector<char> getCharArray(string str) {vector<char> res;for (char c : str) res.push_back(c);return res;
}int main() {string postOrder;string inOrder;cin >> postOrder >> inOrder;vector<char> postStr = getCharArray(postOrder);vector<char> inStr = getCharArray(inOrder);BTree tree;tree.root = tree.getTree(postStr, inStr);tree.Preorder(tree.root);cout << endl;return 0;
}