二叉树查找结点及父结点

6 二叉树查找结点及父结点 (5分)

编写程序在二叉树中查找给定结点及父结点。二叉树结点的数据域值不等于0的整数。

输入格式:

输入第1行为一组用空格间隔的整数，表示带空指针信息的二叉树先根序列，其中空指针用0表示。例如1 5 8 0 0 0 6 0 0表示如下图的二叉树。第2行为整数m，表示查询个数。接下来m行，每行为一个不等于0的整数K，表示要查找的结点的数据值。m不超过100，二叉树结点个数不超过150000，高度不超过6000。输入数据保证二叉树各结点数据值互不相等。

输出格式:

输出为m行，每行1个整数，表示被查找结点K的父结点数据值，若二叉树中无结点K或结点K无父结点，则输出0。

输入样例:

1 5 8 0 0 0 6 0 0
3
8
1
6

输出样例:

5
0
1

#include <iostream>
#include <queue>
#include <string>
#include<sstream>
#include <unordered_map>
using namespace std;

class BTree;
class BNode {
	string data;
	BNode *lch, *rch;
public:
	BNode() :lch(NULL), rch(NULL) {}
	BNode(string item, BNode *left = NULL, BNode *right = NULL) :data(item), lch(left), rch(right) {}
	void Release();
	friend class BTree;
};

class BTree {
private:
	BNode *root;
public:
	BTree() :root(NULL) {}
	~BTree();
	void PreOderBuild(BNode*& BT, int& index, BNode* father, unordered_map<string, string>* mpFindFaher);
	BNode *SF(string Value);
};

vector<string> tree;
BNode *BT = NULL;
int CntLeft, CntRight;

void BNode::Release() {
	if (lch) {
		
		lch->Release();
		delete lch;
		lch = NULL;
	}
	if (rch) {
	
		rch->Release();
		delete rch;
		rch = NULL;
	}
}

BTree::~BTree() {  //析构
	if (BT) {
		BT->Release();
		delete BT;
		BT = NULL;
	}
}

void BTree::PreOderBuild(BNode *&BT, int &index, BNode* father, unordered_map<string, string>* mpFindFaher) {  //建树
	if (tree[index] == "0") {
		BT = NULL;
		index++;
	}
	else {	
		BT = new BNode;
		BT->data = tree[index];
		if ((*mpFindFaher).find(BT->data) != (*mpFindFaher).end()) {
			if (father != NULL) {
				(*mpFindFaher)[BT->data] = father->data;
			}
		}
		index++;
		PreOderBuild(BT->lch, index, BT, mpFindFaher);
		PreOderBuild(BT->rch, index, BT, mpFindFaher);
	}
}

queue<BNode*> Q;
BNode* BTree::SF(string Value) {	//寻找父结点
	Q.push(BT);
	BNode*ptr;
	ptr = Q.front();
	while (!Q.empty()) {
		ptr = Q.front();
		Q.pop();
		if (ptr->lch ) {
			if (ptr->lch->data == Value) {
				cout << ptr->data << endl;
				return ptr;
			}
		}
		if (ptr->rch) {
			if (ptr->rch->data == Value) {
				cout << ptr->data << endl;
				return ptr;
			}
		}
		if (ptr->lch) {
			Q.push(ptr->lch);
		}
		if (ptr->rch) {
			Q.push(ptr->rch);
		}
	}
	cout << 0 << endl;
}

int main() {
	string str = "1 5 8 0 0 0 6 0 0";
	getline(cin, str);
	stringstream sstream(str);
	while (sstream) {
		string substr;
		sstream >> substr;
		tree.push_back(substr);
	}
	BTree L;
	int index = 0;

	int m;
	cin >> m;
	string child;
	vector<string> vec_child;
	unordered_map<string, string> mp;
	while (m--) {
		cin >> child;
		mp[child]="0";
		vec_child.push_back(child);
	}
	L.PreOderBuild(BT, index, NULL, &mp);
	for (auto str : vec_child) {
		cout << mp[str] << endl;
	}
		
	L.~BTree();
	return 0;
}
/*
1 5 8 0 0 0 6 0 0
*/