展示型网站建设流程,济南建设工程信息网,浙江网站建设,网站建设人力调配范文二叉树——根节点到特定节点路径查找
一、思路二、代码实现 一、思路 使用二叉链表创建的二叉树#xff0c;这里我的思路是用链栈来存放找寻二叉树特定节点中#xff0c;用来存放节点元素 个人思路#xff1a;创建链栈#xff0c;遍历二叉树并把路径中节点元素存放到栈中这里我的思路是用链栈来存放找寻二叉树特定节点中用来存放节点元素 个人思路创建链栈遍历二叉树并把路径中节点元素存放到栈中如下图所示 L 为一开始创建的链栈头指针 flag 1作为标记符表示还没在一条路径中找到要找的特定节点元素 二、代码实现 思路理解不了可以结合运行结果图加上自己画图理解运行结果在最下方 #includestdio.h
#includestdlib.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(SNULL){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-nextNULL) // 栈空{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(TNULL){return;} if(flag1) // 标记符flag 还是1时表示还没找到要找的节点 {printf(入栈元素为: %d\n,T-Data);PushStack(T-Data); // 入栈}if(T-Data data) // 已经在二叉树中遍历到要找的节点元素 {printf(元素找到元素为: %d\n,T-Data);flag 0;return; }CherkNode(T-LChild,data); // 遍历这个节点左子树为NULL时才结束递归返回上一级节点CherkNode(T-RChild,data); // 遍历这个节点的右子树为NULL时返回上一级节点if(flag1) // 递归遍历二叉树每条路径中寻找由于遍历一个节点 { // 就会让元素入栈以便将后面元素不是要找路径之中的元素从栈中清除 printf(出栈元素: %d\n,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(TNULL) // 空树 {return;}CherkNode(T,data); // 搜索二叉树中要找的节点进行入栈出栈操作 for(i0;L-next;i){temp[i] PopStack(); // 找到的路径元素逆序存放在数组temp[]中 } printf(路径寻找成功路径如下:\n);for(i--;i0;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;
}运行结果
