PTA-学校-数据结构（求根结点到x结点的路径）

2-2 求根结点到x结点的路径

分数 4

作者 王东

单位 贵州师范学院

求根结点到x结点的路径（假定结点不重复）。

输入样例：

输入一行字符序列先序递归构建二叉树。每个字符对应一个结点，#表示空结点。第二行输入一个结点值x。

52#3##41##6##
3

输出样例：

输出从根到结点x的路径。

5 2 3 

解析

#include <iostream>
#include <cstdlib> 
#include <queue>
using namespace std;
// 二叉树节点结构
typedef struct BiTNode {
	char data;
	struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;

BiTNode* buildTree(const string& pre, int& index) {
	char c = pre[index];
	index++;
	if (c == '#') {
		return NULL;
	}
	BiTNode* node = (BiTNode*)malloc(sizeof(BiTNode));
	node->data = c;
	node->lchild = buildTree(pre, index);
	node->rchild = buildTree(pre, index);
	return node;
}

bool findPath(BiTree node, char x, char* path, int& len) {
	if (node == NULL) {
		return false;
	}
	path[len++] = node->data;
	if (node->data == x) {
		return true;
	}
	// 递归左子树，若找到则直接返回
	if (findPath(node->lchild, x, path, len)) return true;

	// 递归右子树，若找到则直接返回
	if (findPath(node->rchild, x, path, len)) return true;

	// 左右子树均未找到，回溯（移除当前节点）
	len--;
	return false;
}

int main() {
	string preorder;
	char x;
	cin >> preorder >> x;

	int index = 0;
	BiTNode* root = buildTree(preorder, index);
	char path[1000];
	int pathlen = 0;
	findPath(root, x, path, pathlen);

	for (int i = 0; i < pathlen; i++) {
		cout << path[i] << " ";
	}

	return 0;
}