二叉树示例
其中#表示空节点。
第一个遍历： ABD##EG###CF###
中顺序扫描： #D#B#G#E#A#F#C#
后面的排线： ##D##G#EB##F#CA
问题是如何得到从根节点到任意节点的路径？
例)输入g，如何得到从节点a到节点g的路径？
很明显，一目了然路径是ABEG。 如何通过程序得到这条路径，是我们接下来要做的。
存储结构使用链式存储结构保存二叉树信息，结构如下。
typedef struct BiTNode {char data； //数据struct BiTNode* lchild，* rchild； //左子代，右子代}BiTNode，* BiTree； //二叉树节点的存储结构用链栈保存路径，结构如下。
typedefstructstacknode { chardata； //数据结构堆栈* next； //下一个节点}StackNode，* Stack； //链栈函数声明二叉树相关函数//创建二叉树节点，并创建二叉树节点BiTree createBiTNode (； //创建二叉树并返回根节点BiTree createBiTree ()； //初始化二叉树并返回根节点BiTree initBiTree ()； //清除二叉树的字节(bitreet )； 创建堆栈相关函数//堆栈节点，初始化创建的堆栈节点Stack createStackNode(//堆栈，返回到堆栈的开头节点Stack initStack ()； //堆栈是否初始化intisstackexist(stacks )； //堆栈是否为空intisstackempty(stacks )； //堆栈charpush(stacks，char data )； //堆栈charpop(stacks )； //查看堆栈顶部元素charpeek(stacks )//清空堆栈VoidClearStack(Stacks )； 查找路径相关函数//路径，并返回是否找到了目标节点intsearchpath(bitreet，Stack S )； //是否找到目标节点intisfindtargetnode(stacks )； //路径显示voidshowpath(stacks )//输出路径voidoutputpath(stacks )； 函数的定义有点多，所以不单独列出。 参见完整的代码。
知识点作为回顾性质的文章。 相关的知识点有二叉树、结构体、链表、链栈、递归、指针、DFS。 还算全面。
完整代码：/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *代码实现功能：输出猫王指定节点路径编译环境： Visual Studio 2019更新日期： 2019年10月10日15:16:28更新内容：清空二叉树和堆栈函数优化if判断条件博客链接： https://bbit Arttah 102387839作者： wow ph * * * * * * * * * * * * * * * * * * * * * * * * * * * ph * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * free头文件# define empty _ node ' # ' # define true1# define false0# define stack _ empty true # define stack _ not _ empty false }BiTNode，* BiTree； //二叉链表typedefstructstacknode { chardata； struct StackNode* next； }StackNode，* Stack； 创建//链堆栈//二叉树节点，并返回创建的二叉树节点BiTree createBiTNode ()； //创建二叉树并返回根节点BiTree createBiTree ()； //初始化二叉树并返回根节点BiTree initBiTree ()； //清除二叉树的字节(bitreet )； //创建堆栈节点，并返回所创建的堆栈节点Stack createStackNode ()； //初始化堆栈，并返回到堆栈的第一个节点Stack initStack (； //堆栈是否初始化intisstackexist(stacks )； //堆栈是否为空intisstackempty(stacks )； //堆栈charpush(stacks，cha
r data);// 出栈char pop(Stack S);// 查看栈顶元素char peek(Stack S);// 清空栈void clearStack(Stack S);// 寻找路径，返回是否找到目标结点int searchPath(BiTree T, Stack S);// 是否找到目标结点int isFindTargetNode(Stack S);// 显示路径void showPath(Stack S);// 输出路径void outputPath(Stack S);// 输出程序提示信息void outputTips();int main() {outputTips();// 输出程序提示信息BiTree tree = initBiTree();Stack stack = initStack();// 头结点存储目标结点信息searchPath(tree, stack);// 寻找路径showPath(stack);// 输出路径信息clearBiTree(tree);// 清空二叉树clearStack(stack);// 清空栈return 0;}/******************************** 二叉树 ********************************/// 创建二叉树结点BiTree createBiTNode() {BiTree newNode = (BiTree)malloc(sizeof(BiTNode));if (newNode == NULL) {printf("错误（%d）：创建二叉树结点错误！n", __LINE__);exit(0);}newNode->lchild = NULL;newNode->rchild = NULL;return newNode;}// 创建二叉树BiTree createBiTree() {char ch = getchar();if (ch != 'n' && ch != EMPTY_NODE) {BiTree T = createBiTNode();T->data = ch;T->lchild = createBiTree();// 左子树T->rchild = createBiTree();// 右子树return T;}return NULL;}// 初始化二叉树BiTree initBiTree() {printf("输入二叉树：");BiTree tree = createBiTree();char enter = getchar();return tree;}// 清空二叉树void clearBiTree(BiTree T) {if (T != NULL) {clearBiTree(T->lchild);clearBiTree(T->rchild);free(T);}}/********************************** 栈 **********************************/// 创建栈结点Stack createStackNode() {Stack newNode = (Stack)malloc(sizeof(StackNode));if (newNode == NULL) {printf("错误（%d）：创建栈结点错误！n", __LINE__);exit(0);}newNode->next = NULL;return newNode;}// 初始化栈，并返回头结点Stack initStack() {printf("输入指定结点：");char targetNode = getchar();Stack stack = createStackNode();// 头结点存储目标结点数据stack->data = targetNode;return stack;}// 栈头结点是否存在int isStackExist(Stack S) {if (S == NULL) {printf("错误（%d）：栈的头结点未初始化！n", __LINE__);exit(0);}return TRUE;}// 栈是否为空int isStackEmpty(Stack S) {if (isStackExist(S) == FALSE) {return STACK_EMPTY;}if (S->next == NULL) {return STACK_EMPTY;}return STACK_NOT_EMPTY;}// 入栈，data是要入栈的结点的数据char push(Stack S, char data) {if (isStackExist(S) == TRUE) {Stack node = createStackNode();node->data = data;node->next = S->next;S->next = node;}return data;}// 出栈，返回栈顶结点的数据char pop(Stack S) {char ret = STACK_EMPTY;if (isStackEmpty(S) == STACK_NOT_EMPTY) {Stack delete = S->next;S->next = delete->next;ret = delete->data;free(delete);}return ret;}// 查看栈顶元素char peek(Stack S) {return isStackEmpty(S) == STACK_EMPTY ? STACK_EMPTY : S->next->data;}// 清空栈void clearStack(Stack S) {while (isStackEmpty(S) == STACK_NOT_EMPTY) {pop(S);}free(S);}/********************************* 路径 *********************************/// 寻找路径int searchPath(BiTree T, Stack S) {if (isFindTargetNode(S) == FOUND) {return FOUND;}if (T == NULL) {// 空树return NOT_FOUND;}push(S, T->data);// 查找子树if (searchPath(T->lchild, S) == FOUND) {return FOUND;}if (searchPath(T->rchild, S) == FOUND) {return FOUND;}pop(S);return NOT_FOUND;}// 是否找到目标结点int isFindTargetNode(Stack S) {if (isStackEmpty(S) == STACK_NOT_EMPTY && peek(S) == S->data) {return FOUND;}return NOT_FOUND;}// 输出路径，递归void outputPath(Stack S) {if (isStackEmpty(S) == STACK_NOT_EMPTY) {outputPath(S->next);if (isStackEmpty(S->next) == STACK_NOT_EMPTY) {printf(" ");}printf("%c", S->next->data);}}// 显示路径void showPath(Stack S) {if (isFindTargetNode(S) == FOUND) {printf("路径：");outputPath(S);printf("n");} else {printf("未找到结点'%c'n", S->data);}}// 输出提示void outputTips() {printf("1、先序输入二叉树n");printf("2、空结点用'%c'表示n", EMPTY_NODE);printf("3、Enter表示输入结束n");printf("4、字符个数必须正确n");}/*************************************************************************1、先序输入二叉树2、空结点用'#'表示3、Enter表示输入结束4、字符个数必须正确示例1：输入二叉树：ABD##EG###CF###输入指定结点：G路径：A B E G示例2：输入二叉树：124##56##7##3##输入指定结点：7路径：1 2 5 7*************************************************************************/ 参考1、C语言程序设计教程（第二版）. 细腻的口红 林萍 可耐的口红 编著. 清华大学出版社.
2、数据结构（C语言版）. 满意的发带 sldhb 编著. 清华大学出版社.
原文链接：https://blog.csdn.net/pfdvnah/article/details/102387839
- wowpH -