有一棵二叉树，如下图所示：

其中 # 表示空结点。

先序遍历：A B D E G C F

问题：怎么得到从根结点到任意结点的路径呢？

示例：输入 G，怎么得到从结点 A 到结点 G 的路径呢？

很明显，我们一眼就能看出来路径是 A B E G。如何通过程序得到这条路径就是我们需要做的。

定义二叉树的 链式存储结构 如下：

typedef struct BiTNode {
	char data;
	struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;// 二叉树结点的存储结构

二叉树的遍历有三种方式：即先序遍历，中序遍历，后序遍历。

这里采用先序遍历，因为我们需要的是到达指定结点即可。没必要其他多余的操作。而先序就是先访问结点再递归子树。满足要求。

由于需要 路径 而不是输出先序遍历的结果，因此需要一个 栈 来保存路径。由于数据是 字符型 的，但是不知道路径长度，因此采用 链栈。

链栈 结构如下：

typedef struct StackNode {
	char data;
	struct StackNode* next;
}StackNode, * Stack;// 链栈

完整代码：

/*************************************************************************
	实现功能：	输出从根结点到指定结点的路径
	编译环境：	Visual Studio 2019
	更新日期：	2019年10月8日23:01:29
	作者：		wowpH
*************************************************************************/
#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>// exit，malloc头文件

#define EMPTY_NODE '#'

typedef struct BiTNode {
	char data;
	struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;// 二叉树的链式存储结构

typedef struct StackNode {
	char data;
	struct StackNode* next;
}StackNode, * Stack;// 链栈

// 创建二叉树结点
BiTree createBiTNode();
// 创建二叉树
void createBiTree(BiTree* T);
// 创建栈结点
Stack createStackNode();
// 查找结点并返回路径头结点
void findNode(Stack S, BiTree T, char nodeToFind);
// 输出路径
void outputPath(Stack S);
// 输出提示
void outputTips();

int main() {
	outputTips();

	printf("输入二叉树：");
	BiTree root = NULL;
	createBiTree(&root);
	char enter = getchar();

	printf("输入指定结点：");
	char nodeToFind = getchar();
	Stack stack = createStackNode();
	findNode(stack, root, nodeToFind);
	// 输出路径信息
	if (stack->next == NULL) {
		printf("未找到结点'%c'\n", nodeToFind);
	} else {
		printf("路径：");
		outputPath(stack);
		printf("\n");
	}

	return 0;
}

// 创建二叉树结点
BiTree createBiTNode() {
	BiTree bt = (BiTree)malloc(sizeof(BiTNode));
	if (bt == NULL) {
		printf("错误：创建二叉树结点错误！\n");
		exit(0);
	}
	bt->lchild = NULL;
	bt->rchild = NULL;
	return bt;
}

// 创建二叉树
void createBiTree(BiTree* T) {
	char ch = getchar();
	if (ch == '\n' || ch == EMPTY_NODE) {
		return;
	}
	*T = createBiTNode();
	(*T)->data = ch;
	createBiTree(&(*T)->lchild);// 左子树
	createBiTree(&(*T)->rchild);// 右子树
}

// 创建栈结点
Stack createStackNode() {
	Stack ret = (Stack)malloc(sizeof(StackNode));
	if (ret == NULL) {
		printf("错误：创建栈结点错误！\n");
		exit(0);
	}
	ret->next = NULL;
	return ret;
}

// 查找结点
void findNode(Stack S, BiTree T, char nodeToFind) {
	if (S->next != NULL && S->next->data == nodeToFind) {
		return;// 已找到
	}
	if (T == NULL) {// 空树
		return;
	}
	// 入栈
	Stack sNew = createStackNode();
	sNew->data = T->data;
	sNew->next = S->next;
	S->next = sNew;
	// 查找子树
	findNode(S, T->lchild, nodeToFind);
	findNode(S, T->rchild, nodeToFind);
	// 若不是要查找的结点，出栈
	if (S->next->data != nodeToFind) {
		Stack delete = S->next;
		S->next = delete->next;
		free(delete);
	}
}

// 输出路径，递归
void outputPath(Stack S) {
	if (S->next != NULL) {
		outputPath(S->next);
		printf(" ");
	}
	printf("%c", S->data);
}

// 输出提示
void outputTips() {
	printf("1、先序输入二叉树\n");
	printf("2、空结点用'%c'表示\n", EMPTY_NODE);
	printf("3、Enter表示输入结束\n");
	printf("4、不能输入多余的字符\n");
	printf("5、查找的字符不能是换行符和'%c'\n\n", EMPTY_NODE);
}

/*************************************************************************
1、先序输入二叉树
2、空结点用'#'表示
3、Enter表示输入结束
4、不能输入多余的字符
5、查找的字符不能是换行符和'#'

示例1：
输入二叉树：ABD##EG###CF###
输入指定结点：G
路径：A B E G

示例2：
输入二叉树：124##56##7##3##
输入指定结点：7
路径：1 2 5 7
*************************************************************************/