二叉树——根节点到特定节点路径查找 一、思路二、代码实现
一、思路
使用二叉链表创建的二叉树，这里我的思路是用链栈来存放找寻二叉树特定节点中，用来存放节点元素
个人思路：创建链栈，遍历二叉树并把路径中节点元素存放到栈中（如下图所示）：
L 为一开始创建的链栈头指针
flag = 1，作为标记符，表示还没在一条路径中，找到要找的特定节点元素
思路理解不了，可以结合运行结果图，加上自己画图理解，运行结果在最下方
#include<stdio.h>#include<stdlib.h>//二叉树结构体 typedef struct TreeLink{int Data;struct TreeLink *LChild;//左子树指针struct TreeLink *RChild;//右子树指针}T_LINK,*TLINK;//链栈 typedef struct STACK{int data;struct STACK *next;}StackNode,*Stack; int flag;//标记符 Stack L;//链栈头节点指针 //************************* 二叉树 ***********************// //创建二叉树 TLINK Create_TreeLink(){TLINK T;int data;int temp; scanf("%d",&data);temp = getchar();//吸收scanf带来的回车 if(data == -1){//输入-1表示该节点下左树或者右树下不存数据,返回到上一级节点 return NULL;}else{T = (TLINK)malloc(sizeof(T_LINK));//每个节点开辟空间 T->Data = data;printf("请输入%d节点下左节点数据: ",data);T->LChild = Create_TreeLink();printf("请输入%d节点下右节点数据: ",data);T->RChild = Create_TreeLink();return T;}}//先序遍历二叉树void ShowXianXu(TLINK S){if(S==NULL){return;}printf("%d ",S->Data);ShowXianXu(S->LChild);ShowXianXu(S->RChild);} //************************* 链 栈 *********************////入栈void PushStack(int x){Stack top;top = (Stack)malloc(sizeof(StackNode));top->data = x;top->next = L;//第一次是让一开始的头节点存入元素，尾巴指向NULL已经初始化好L = top;//之后便是创建新的链栈节点和之前的串起来} //出栈int PopStack(){int x;if(L->next==NULL)//栈空{printf("出栈完毕n");exit(-1);}else{Stack p;x = L->data;p = L;//让原来的L变成P L = p->next;//原来头节点next指向的变成新的头节点 free(p);//释放原来的头节点 return x;//返回原来头节点里头的元素 }} //进入二叉树搜索特定节点void CherkNode(TLINK T,int data){if(T==NULL){return;}if(flag==1)//标记符flag 还是1时，表示还没找到要找的节点 {printf("入栈元素为: %dn",T->Data);PushStack(T->Data); //入栈}if(T->Data == data)//已经在二叉树中遍历到要找的节点元素 {printf("元素找到，元素为: %dn",T->Data);flag = 0;return; }CherkNode(T->LChild,data);//遍历这个节点左子树，为NULL时才结束递归，返回上一级节点CherkNode(T->RChild,data);//遍历这个节点的右子树，为NULL时返回上一级节点if(flag==1)//递归遍历二叉树每条路径中寻找，由于遍历一个节点 {//就会让元素入栈，以便将后面元素不是要找路径之中的元素，从栈中清除 printf("出栈元素: %dn",T->Data); PopStack();//清除非要寻找路径上的栈中元素}} //搜索路径 void SearchPath(TLINK T,int data){int temp[30];//用来存最后找到的路径各个节点里头的数据 int i;flag = 1;//标记符 L = (Stack)malloc(sizeof(StackNode));//分配空间给指针 L->next = NULL;//让第一个节点指针指向NULL，最后也就是栈底指针 if(T==NULL)//空树 {return;}CherkNode(T,data);//搜索二叉树中要找的节点，进行入栈出栈操作 for(i=0;L->next;i++){temp[i] = PopStack();//找到的路径元素逆序存放在数组temp[]中 } printf("路径寻找成功，路径如下:n");for(i--;i>=0;i--){printf("%d ",temp[i]);}}//主函数 int main(){TLINK T;//创建二叉树指针 int Node;printf("请输入第一个节点（输入-1表示该节点下无其他节点）n");T = Create_TreeLink();printf("先序遍历如下:n"); ShowXianXu(T); putchar('n');printf("请输入你要找的特定节点:n");scanf("%d",&Node);SearchPath(T,Node);//开始搜索节点return 0;}运行结果：