DS|动态查找

题目一：DS二叉排序树 -- 创建和插入

题目描述：

给出一个数据序列，建立二叉排序树，并实现插入功能。

在建立和插入操作后，都输出二叉树的先序遍历结果i

输入要求：

第1行输入n，表示序列包含n个数据

第2行输入n个数据，都是自然数且互不相同，数据之间用空格隔开

第3行输入m，表示要插入m个数据

输入m行，每行一个要插入的数据，都是自然数且和前面的数据不等

输出要求：

第一行输出一开始构建的二叉排序树的先序遍历结果

从第二行起，输出m行，每行输出插入一个数据到二叉排序树后的先序遍历结果

每行输出的遍历结果中，每个数据后面都带一个空格，最后一个数据也带。

输入样例：

6
22 33 55 66 11 44
3
77
50
10

6
33 55 22 66 11 44
3
25
88
50

输出样例：

22 11 33 55 44 66 
22 11 33 55 44 66 77 
22 11 33 55 44 50 66 77 
22 11 10 33 55 44 50 66 77 

33 22 11 55 44 66 
33 22 11 25 55 44 66 
33 22 11 25 55 44 66 88 
33 22 11 25 55 44 50 66 88 

代码示例：

#include <iostream>
using namespace std;

struct BTNode {
public:
	int data;
	BTNode* lChild;
	BTNode* rChild;
};

class BTree {
public:
	BTNode* root;
	BTree() :root(NULL) {}
	void Preorder(BTNode* cur) {
		if (cur != NULL) {
			cout << cur->data << " ";
			Preorder(cur->lChild), Preorder(cur->rChild);
		}
	}

	BTNode* insertBST(BTNode* bt, int x) {
		if (bt == NULL) {
			BTNode* s = new BTNode;
			s->data = x;
			s->lChild = s->rChild = NULL;
			return s;
		}
		else if (bt->data > x) bt->lChild = insertBST(bt->lChild, x);
		else bt->rChild = insertBST(bt->rChild, x);
		return bt;
	}
};
int main() {
	int n, t;
	cin >> t;
	BTree tree;
	while (t--) {
		cin >> n;
		tree.root = tree.insertBST(tree.root, n);
	}

	tree.Preorder(tree.root);
	cout << endl;
	cin >> t;
	while (t--) {
		cin >> n;
		tree.root = tree.insertBST(tree.root, n);
		tree.Preorder(tree.root);
		cout << endl;
	}
}

题目二：DS二叉排序树 -- 查找

题目描述：

给出一个数据序列，建立二叉排序树，并实现查找功能

输入要求：

第1行输入n，表示首个序列包含n个数据

第2行输入n个数据，都是自然数且互不相同，数据之间用空格隔开

第3行输入m，表示要查找m个数据

接着输入m行，每行一个要查找的数据，都是自然数

以此类推输入下一个示例

输出要求：

第一行输出有序的数据序列，对二叉排序树进行中序遍历可以得到

从第二行起，输出查找结果，如果查找成功输出查找次数，如果查找失败输出-1

输入样例：

6
22 33 55 66 11 44
7
11
22
33
44
55
66
77

6
33 22 55 11 66 44
4
88
11
44
66

输出样例：

11 22 33 44 55 66 
2
1
2
4
3
4
-1

11 22 33 44 55 66 
-1
3
3
3

代码示例：

#include <iostream>
using namespace std;

struct BTNode {
public:
	int data;
	BTNode* lChild;
	BTNode* rChild;
};

class BTree {
public:
	BTNode* root;
	BTree() :root(NULL) {}
	void Preorder(BTNode* cur) {
		if (cur != NULL) {
			cout << cur->data << " ";
			Preorder(cur->lChild), Preorder(cur->rChild);
		}
	}

	void Inorder(BTNode* cur) {
		if (cur != NULL) {
			Inorder(cur->lChild);
			cout << cur->data << " ";
			Inorder(cur->rChild);
		}
	}

	BTNode* insertBST(BTNode* bt, int x) {
		if (bt == NULL) {
			BTNode* s = new BTNode;
			s->data = x;
			s->lChild = s->rChild = NULL;
			return s;
		}
		else if (bt->data > x) bt->lChild = insertBST(bt->lChild, x);
		else bt->rChild = insertBST(bt->rChild, x);
		return bt;
	}

	BTNode* searchItem(BTNode* bt, int key) {
		if (bt == NULL) return NULL;
		if (bt->data == key) return bt;
		else if (bt->data > key) return searchItem(bt->lChild, key);
		else return searchItem(bt->rChild, key);
	}
	int searchItemCount(BTNode* bt, int key, int count) {
		if (bt == NULL) return -1;
		if (bt->data == key) return count;
		else if (bt->data > key) return searchItemCount(bt->lChild, key, ++count);
		else return searchItemCount(bt->rChild, key, ++count);
	}
};
int main() {
	int n, t;
	cin >> t;
	BTree tree;
	while (t--) {
		cin >> n;
		tree.root = tree.insertBST(tree.root, n);
	}

	tree.Inorder(tree.root);
	cout << endl;
	cin >> t;
	while (t--) {
		cin >> n;
		int cnt = tree.searchItemCount(tree.root, n, 1);
		cout << cnt << endl;
	}
}

题目三：DS二叉排序树 -- 删除

题目描述：

给出一个数据序列，建立二叉排序树，并实现删除功能

对二叉排序树进行中序遍历，可以得到有序的数据序列

输入要求：

第一行输入t，表示有t个数据序列

第二行输入n，表示首个序列包含n个数据

第三行输入n个数据，都是自然数且互不相同，数据之间用空格隔开

第四行输入m，表示要删除m个数据

从第五行起，输入m行，每行一个要删除的数据，都是自然数

以此类推输入下一个示例

输出要求：

第一行输出有序的数据序列，对二叉排序树进行中序遍历可以得到

从第二行起，输出删除第m个数据后的有序序列，输出m行

以此类推输出下一个示例的结果

输入样例：

1
6
22 33 55 66 11 44
3
66
22
77

输出样例：

11 22 33 44 55 66 
11 22 33 44 55 
11 33 44 55 
11 33 44 55 

代码示例：

#include <iostream>
using namespace std;

struct BTNode {
public:
	int data;
	BTNode* lChild;
	BTNode* rChild;
};

class BTree {
public:
	BTNode* root;
	BTree() :root(NULL) {}
	void Preorder(BTNode* cur) {
		if (cur != NULL) {
			cout << cur->data << " ";
			Preorder(cur->lChild), Preorder(cur->rChild);
		}
	}

	void Inorder(BTNode* cur) {
		if (cur != NULL) {
			Inorder(cur->lChild);
			cout << cur->data << " ";
			Inorder(cur->rChild);
		}
	}

	BTNode* insertBST(BTNode* bt, int x) {
		if (bt == NULL) {
			BTNode* s = new BTNode;
			s->data = x;
			s->lChild = s->rChild = NULL;
			return s;
		}
		else if (bt->data > x) bt->lChild = insertBST(bt->lChild, x);
		else bt->rChild = insertBST(bt->rChild, x);
		return bt;
	}

	BTNode* searchItem(BTNode* bt, int key) {
		if (bt == NULL) return NULL;
		if (bt->data == key) return bt;
		else if (bt->data > key) return searchItem(bt->lChild, key);
		else return searchItem(bt->rChild, key);
	}
	int searchItemCount(BTNode* bt, int key, int count) {
		if (bt == NULL) return -1;
		if (bt->data == key) return count;
		else if (bt->data > key) return searchItemCount(bt->lChild, key, ++count);
		else return searchItemCount(bt->rChild, key, ++count);
	}

	BTNode* searchAndDelete(BTNode* bt, int key) {
		if (bt == NULL) return NULL;
		if (bt->data == key) {
			if (bt->lChild == NULL && bt->rChild == NULL) {
				delete bt;
				return NULL;
			}
			else if (bt->lChild != NULL && bt->rChild == NULL) {
				BTNode* temp = bt->lChild;
				delete bt;
				return temp;
			}
			else if (bt->lChild == NULL && bt->rChild != NULL) {
				BTNode* temp = bt->rChild;
				delete bt;
				return temp;
			}
			else {
				BTNode* parent = bt;
				BTNode* successor = bt->rChild;
				while (successor->lChild != NULL) {
					parent = successor;
					successor = successor->lChild;
				}
				bt->data = successor->data;
				if (parent == bt) parent->rChild = successor->rChild;
				else parent->lChild = successor->rChild;

				delete successor;
				return bt;
			}
		}
		else if (bt->data > key) bt->lChild = searchAndDelete(bt->lChild, key);
		else bt->rChild = searchAndDelete(bt->rChild, key);
		return bt;
	}
};
int main() {
	int t;
	cin >> t;
	while (t--) {
		BTree tree;
		int n, number;
		cin >> n;
		while (n--) {
			cin >> number;
			tree.root = tree.insertBST(tree.root, number);
		}
		tree.Inorder(tree.root);
		cout << endl;

		cin >> n;
		while (n--) {
			cin >> number;
			tree.root = tree.searchAndDelete(tree.root, number);
			tree.Inorder(tree.root);
			cout << endl;
		}
	}
}

题目四：DS二叉排序树 -- 二叉树平衡因子

题目描述：

二叉树用数组存储，将二叉树的结点数据依次自上而下,自左至右存储到数组中，一般二叉树与完全二叉树对比，比完全二叉树缺少的结点在数组中用0来表示。

计算二叉树每个结点的平衡因子，并按后序遍历的顺序输出结点的平衡因子。

输入要求：

测试次数t

每组测试数据一行，数组元素个数n，后跟n个字符，二叉树的数组存储。

输出要求：

对每组测试数据，按后序遍历的顺序输出树中结点的平衡因子（测试数据没有空树）

输入样例：

2
6 ABC00D
24 ABCD0EF0000H00000000000I

输出样例：

B 0
D 0
C 1
A -1
D 0
B 1
I 0
H 1
E 2
F 0
C 2
A -2

代码示例：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int calcHeight(char* arr, int n) {
    if (arr[n] == '0') return 0;
    return max(calcHeight(arr, n * 2 + 1), calcHeight(arr, n * 2 + 2)) + 1;
}

void printNodeDetails(char* arr, int n) {
    if (arr[n] == '0') return;

    printNodeDetails(arr, n * 2 + 1);
    printNodeDetails(arr, n * 2 + 2);

    int lh = calcHeight(arr, n * 2 + 1);
    int rh = calcHeight(arr, n * 2 + 2);

    cout << arr[n] << " " << lh - rh << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        char* arr;
        int n;
        cin >> n;
        int size = 2;
        while (size / 2 < n) {
            size *= 2;
        }
        arr = new char[size + 3];
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        for (int i = n; i < size; i++) {
            arr[i] = '0';
        }
        printNodeDetails(arr, 0);
    }
    return 0;
}

题目五：DS二叉排序树 -- 搜索树判断

题目描述：

对于二叉搜索树，我们规定任一结点的左子树仅包含严格小于该结点的键值，而其右子树包含大于或等于该结点的键值。如果我们交换每个节点的左子树和右子树，得到的树叫做镜像二叉搜索树。

现在我们给出一个整数键值序列，请编写程序判断该序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，如果是，则输出对应二叉树的后序遍历序列。

输入要求：

输入的第一行包含一个正整数N（≤1000），第二行包含N个整数，为给出的整数键值序列，数字间以空格分隔。

输出要求：

输出的第一行首先给出判断结果，如果输入的序列是某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，则输出YES，否侧输出NO。如果判断结果是YES，下一行输出对应二叉树的后序遍历序列。数字间以空格分隔，但行尾不能有多余的空格。

输入样例：

7
8 6 5 7 10 8 11

输出样例：

YES
5 7 6 8 11 10 8

代码示例：

#include <iostream>
using namespace std;

const int N = 1010;

int arr[N], arr1[N], arr2[N];

int cnt, cnt1 = 0, cnt2 = 0;

struct BTNode {
public:
	int data;
	BTNode* lChild;
	BTNode* rChild;
};

class BTree {
public:
	BTNode* root;
	BTree() :root(NULL) {}
	void Preorder(BTNode* cur) {
		if (cur != NULL) {
			cout << cur->data << " ";
			Preorder(cur->lChild), Preorder(cur->rChild);
		}
	}

	void Preorder1(BTNode* cur) {
		if (cur != NULL) {
			arr1[cnt1++] = cur->data;
			Preorder1(cur->lChild), Preorder1(cur->rChild);
		}
	}
	void Preorder2(BTNode* cur) {
		if (cur != NULL) {
			arr2[cnt2++] = cur->data;
			Preorder2(cur->lChild), Preorder2(cur->rChild);
		}
	}

	void Inorder(BTNode* cur) {
		if (cur != NULL) {
			Inorder(cur->lChild);
			cout << cur->data << " ";
			Inorder(cur->rChild);
		}
	}

	void Postorder(BTNode* cur) {
		if (cur != NULL) {
			Postorder(cur->lChild), Postorder(cur->rChild);
			cout << cur->data << " ";
		}
	}

	BTNode* insertBST(BTNode* bt, int x) {
		if (bt == NULL) {
			BTNode* s = new BTNode;
			s->data = x;
			s->lChild = s->rChild = NULL;
			return s;
		}
		else if (bt->data > x) bt->lChild = insertBST(bt->lChild, x);
		else bt->rChild = insertBST(bt->rChild, x);
		return bt;
	}

	BTNode* searchItem(BTNode* bt, int key) {
		if (bt == NULL) return NULL;
		if (bt->data == key) return bt;
		else if (bt->data > key) return searchItem(bt->lChild, key);
		else return searchItem(bt->rChild, key);
	}
	int searchItemCount(BTNode* bt, int key, int count) {
		if (bt == NULL) return -1;
		if (bt->data == key) return count;
		else if (bt->data > key) return searchItemCount(bt->lChild, key, ++count);
		else return searchItemCount(bt->rChild, key, ++count);
	}

	BTNode* searchAndDelete(BTNode* bt, int key) {
		if (bt == NULL) return NULL;
		if (bt->data == key) {
			if (bt->lChild == NULL && bt->rChild == NULL) {
				delete bt;
				return NULL;
			}
			else if (bt->lChild != NULL && bt->rChild == NULL) {
				BTNode* temp = bt->lChild;
				delete bt;
				return temp;
			}
			else if (bt->lChild == NULL && bt->rChild != NULL) {
				BTNode* temp = bt->rChild;
				delete bt;
				return temp;
			}
			else {
				BTNode* parent = bt;
				BTNode* successor = bt->rChild;
				while (successor->lChild != NULL) {
					parent = successor;
					successor = successor->lChild;
				}
				bt->data = successor->data;
				if (parent == bt) parent->rChild = successor->rChild;
				else parent->lChild = successor->rChild;

				delete successor;
				return bt;
			}
		}
		else if (bt->data > key) bt->lChild = searchAndDelete(bt->lChild, key);
		else bt->rChild = searchAndDelete(bt->rChild, key);
		return bt;
	}

	void mirrorTree(BTNode* bt) {
		if (bt != NULL) {
			mirrorTree(bt->lChild);
			mirrorTree(bt->rChild);
			swap(bt->lChild, bt->rChild);
		}
	}
};
int main() {
	int n, t;
	cin >> t;
	cnt = t;
	BTree tree;
	for (int i = 0; i < t; i++) {
		cin >> n;
		arr[i] = n;
		tree.root = tree.insertBST(tree.root, n);
	}


	tree.Preorder1(tree.root);
	tree.mirrorTree(tree.root);
	tree.Preorder2(tree.root);
	for (int i = 0; i < t; i++) {
		if (arr[i] != arr1[i]) break;
		if (i == t - 1) {
			cout << "YES" << endl;
			tree.mirrorTree(tree.root);
			tree.Postorder(tree.root);
			return 0;
		}
	}
	for (int i = 0; i < t; i++) {
		if (arr[i] != arr2[i]) break;
		if (i == t - 1) {
			cout << "YES" << endl;
			tree.Postorder(tree.root);
			return 0;
		}
	}
	cout << "NO" << endl;
}

题目六：DS二叉排序树 -- 二叉搜索树的最近公共祖先

题目描述：

给定一棵二叉搜索树的先序遍历序列，要求你找出任意两结点的最近公共祖先结点（简称 LCA）。

输入要求：

输入的第一行给出两个正整数：待查询的结点对数 M（≤?1 000）和二叉搜索树中结点个数 N（≤?10 000）。随后一行给出 N 个不同的整数，为二叉搜索树的先序遍历序列。最后 M 行，每行给出一对整数键值 U 和 V。所有键值都在整型int范围内。

输出要求：

对每一对给定的 U 和 V，如果找到?A?是它们的最近公共祖先结点的键值，则在一行中输出?LCA of U and V is A.。但如果 U 和 V 中的一个结点是另一个结点的祖先，则在一行中输出?X is an ancestor of Y.，其中?X?是那个祖先结点的键值，Y?是另一个键值。如果 二叉搜索树中找不到以 U 或 V 为键值的结点，则输出?ERROR: U is not found.?或者?ERROR: V is not found.，或者?ERROR: U and V are not found.。

输入样例：

6 8
6 3 1 2 5 4 8 7
2 5
8 7
1 9
12 -3
0 8
99 99

输出样例：

LCA of 2 and 5 is 3.
8 is an ancestor of 7.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.

代码示例：

#include <iostream>
using namespace std;

const int N = 1010;

int arr[N], arr1[N], arr2[N];

int cnt, cnt1 = 0, cnt2 = 0;

struct BTNode {
public:
	int data;
	BTNode* lChild;
	BTNode* rChild;
};

class BTree {
public:
	BTNode* root;
	BTree() :root(NULL) {}
	void Preorder(BTNode* cur) {
		if (cur != NULL) {
			cout << cur->data << " ";
			Preorder(cur->lChild), Preorder(cur->rChild);
		}
	}

	void Inorder(BTNode* cur) {
		if (cur != NULL) {
			Inorder(cur->lChild);
			cout << cur->data << " ";
			Inorder(cur->rChild);
		}
	}

	void Postorder(BTNode* cur) {
		if (cur != NULL) {
			Postorder(cur->lChild), Postorder(cur->rChild);
			cout << cur->data << " ";
		}
	}

	BTNode* insertBST(BTNode* bt, int x) {
		if (bt == NULL) {
			BTNode* s = new BTNode;
			s->data = x;
			s->lChild = s->rChild = NULL;
			return s;
		}
		else if (bt->data > x) bt->lChild = insertBST(bt->lChild, x);
		else bt->rChild = insertBST(bt->rChild, x);
		return bt;
	}

	BTNode* searchItem(BTNode* bt, int key) {
		if (bt == NULL) return NULL;
		if (bt->data == key) return bt;
		else if (bt->data > key) return searchItem(bt->lChild, key);
		else return searchItem(bt->rChild, key);
	}
	int searchItemCount(BTNode* bt, int key, int count) {
		if (bt == NULL) return -1;
		if (bt->data == key) return count;
		else if (bt->data > key) return searchItemCount(bt->lChild, key, ++count);
		else return searchItemCount(bt->rChild, key, ++count);
	}

	BTNode* searchAndDelete(BTNode* bt, int key) {
		if (bt == NULL) return NULL;
		if (bt->data == key) {
			if (bt->lChild == NULL && bt->rChild == NULL) {
				delete bt;
				return NULL;
			}
			else if (bt->lChild != NULL && bt->rChild == NULL) {
				BTNode* temp = bt->lChild;
				delete bt;
				return temp;
			}
			else if (bt->lChild == NULL && bt->rChild != NULL) {
				BTNode* temp = bt->rChild;
				delete bt;
				return temp;
			}
			else {
				BTNode* parent = bt;
				BTNode* successor = bt->rChild;
				while (successor->lChild != NULL) {
					parent = successor;
					successor = successor->lChild;
				}
				bt->data = successor->data;
				if (parent == bt) parent->rChild = successor->rChild;
				else parent->lChild = successor->rChild;

				delete successor;
				return bt;
			}
		}
		else if (bt->data > key) bt->lChild = searchAndDelete(bt->lChild, key);
		else bt->rChild = searchAndDelete(bt->rChild, key);
		return bt;
	}

	void judgeLCA(BTNode* bt, int key1, int key2) {
		if (bt->data == key1) cout << key1 << " is an ancestor of " << key2 << "." << endl;
		else if (bt->data == key2) cout << key1 << "is an ancestor of " << key2 << "." << endl;
		else if ((bt->data > key1 && bt->data < key2) || (bt->data < key1 && bt->data > key2)) cout << "LCA of " << key1 << " and " << key2 << " is " << bt->data << "." << endl;
		else if (bt->data > key1 && bt->data > key2) judgeLCA(bt->lChild, key1, key2);
		else judgeLCA(bt->rChild, key1, key2);
	}
};
int main() {
	int m, n, t;
	cin >> m >> n;
	BTree tree;
	for (int i = 0; i < n; i++) {
		cin >> t;
		tree.root = tree.insertBST(tree.root, t);
	}
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		if (tree.searchItem(tree.root, u) && tree.searchItem(tree.root, v)) tree.judgeLCA(tree.root, u, v);
		else if (!tree.searchItem(tree.root, u) && tree.searchItem(tree.root, v)) cout << "ERROR: " << u << " is not found." << endl;
		else if (tree.searchItem(tree.root, u) && !tree.searchItem(tree.root, v)) cout << "ERROR: " << v << " is not found." << endl;
		else cout << "ERROR: " << u << " and " << v << " are not found." << endl;
	}
}