巴彦淖尔市网站建设,东莞网站建设 手袋厂,中国建设人才服务信息网是不是假冒网站,华为网上商城手机官网假设二叉树采用二叉链表方式存储#xff0c; root指向根结点#xff0c;node 指向二叉树中的一个结点#xff0c; 编写函数 path#xff0c;计算root到 node 之间的路径#xff0c;#xff08;该路径包括root结点和 node 结点#xff09;。path 函数声明如下#xff1a…假设二叉树采用二叉链表方式存储 root指向根结点node 指向二叉树中的一个结点 编写函数 path计算root到 node 之间的路径该路径包括root结点和 node 结点。path 函数声明如下
bool path(BiTNode* root, BiTNode* node, Stack* s); 其中root指向二叉树的根结点node指向二叉树中的另一结点s 为已经初始化好的栈 该栈用来保存函数所计算的路径如正确找出路径则函数返回 true此时root在栈底node在栈顶 如未找到则函数返回 false, 二叉树的相关定义如下
#include bitree.h //请不要删除否则检查不通过
#include stdio.h
#include stdlib.hbool path(BiTNode* root, BiTNode* node, Stack* s)
{BiTNode *p, *q; // ElemType p;int i 0;p root;q NULL;init_stack(s);if (p NULL || node NULL)return false;if (p node) {push(s, p);return true;}while (p ! NULL || !is_empty(s)) {while (p) {push(s, p);//非空就先压进去 if (p node)//node已经压进去了 return true;p p-left;//先根遍历 }top(s, p); //回到分支的根if (p-right q || p-right NULL) {q p;//第一个判断条件很关键, 判是否已经遍历过 pop(s, p);//左子树前面的while遍历了, 该结点的右子树遍历了或者为空就不要这个节点了 p NULL; //置空就不会被再次压入 ,过前面的while循环, 等待下一次top赋值, 层次-1//这里指针断了 //需要注意的是p虽然指向该节点但是置空, 该结点任然存在, 并且q结点指向避免再次访问 } else {p p-right;}}return false;
}
