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;
}