数据结构——二叉树根节点到特定节点路径（C语言版）

Bertha 。 2022-12-27 11:30 169阅读 0赞

### 二叉树——根节点到特定节点路径查找 ###

*  一、思路
 *  二、代码实现

# 一、思路 #

> 使用二叉链表创建的二叉树，这里我的思路是用链栈来存放找寻二叉树特定节点中，用来存放节点元素

**个人思路：创建链栈，遍历二叉树并把路径中节点元素存放到栈中（如下图所示）：**

> L 为一开始创建的链栈头指针  
> flag = 1，作为标记符，表示还没在一条路径中，找到要找的特定节点元素

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoaW5lc2Vrb2Jl_size_16_color_FFFFFF_t_70_pic_center]

# 二、代码实现 #

> 思路理解不了，可以结合运行结果图，加上自己画图理解，运行结果在最下方

#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("入栈元素为: %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(flag==1)		//	递归遍历二叉树每条路径中寻找，由于遍历一个节点 
    	{
        				//	就会让元素入栈，以便将后面元素不是要找路径之中的元素，从栈中清除 
    		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(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;
    }

运行结果：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoaW5lc2Vrb2Jl_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoaW5lc2Vrb2Jl_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/0eaa8d18913e4c3ab167fb07f8f394f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoaW5lc2Vrb2Jl_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201210210603703.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoaW5lc2Vrb2Jl,size_16,color_FFFFFF,t_70