C语言数据结构-树和二叉树-路径-假设二叉树采用二叉链表方式存储, root指向根结点,node 指向二叉树中的一个结点,编写函数 path,计算root到 node 之间的路径_神迹小卒的博客-程序员宝宝

技术标签: 数据结构与算法  

路径

假设二叉树采用二叉链表方式存储, root指向根结点,node 指向二叉树中的一个结点,编写函数 path,计算root到 node 之间的路径,(该路径包括root结点和 node 结点)。path 函数声明如下:

bool path(BiTNode* root, BiTNode* node, Stack* s);

其中,root指向二叉树的根结点,node指向二叉树中的另一结点,s 为已经初始化好的栈,该栈用来保存函数所计算的路径,如正确找出路径,则函数返回 true,此时root在栈底,node在栈顶;如未找到,则函数返回 false, 二叉树的相关定义如下:

typedef int DataType;

typedef struct Node{
    DataType data;
    struct Node* left;
    struct Node* right;
}BiTNode, *BiTree;

栈的相关定义及操作如下:

#define Stack_Size 50
typedef BiTNode* ElemType;
typedef struct{
    ElemType elem[Stack_Size];
    int top;
}Stack;

void init_stack(Stack *S); // 初始化栈
bool push(Stack* S, ElemType x); //x 入栈
bool pop(Stack* S, ElemType *px); //出栈,元素保存到px所指的单元,函数返回true,栈为空时返回 false
bool top(Stack* S, ElemType *px); //获取栈顶元素,将其保存到px所指的单元,函数返回true,栈满时返回 false
bool is_empty(Stack* S);  // 栈为空时返回 true,否则返回 false

在提示中,树用缩进的形式展示,如二叉树 ,其缩进形式为:

提供代码

#include <stdlib.h>
#include <stdio.h>
#include "bitree.h" //请不要删除,否则检查不通过

bool path(BiTNode* root, BiTNode* node, Stack* s){


}

参考代码

bool path(BiTNode* root, BiTNode* node, Stack* s)
{
    BiTree T = root, p=NULL;
    if (T == NULL || node == NULL || !is_empty(s))
        return false;
    while (T || !is_empty(s)) {
        while (T) {
            push(s, T);
            if (T == node)
                return true;
            T = T->left;
        }
        top(s, &T);
        if (!T->right || T->right == p) {
            p = T;
            pop(s, &T);
            T = NULL;
        } else
            T = T->right;
    }
    return false;
}

完整代码与解析

#include <stdio.h>
#include <malloc.h>
#include <conio.h>
 
typedef char DataType;
 
typedef struct Node
{
	DataType data;
	struct Node* LChild;
	struct Node* RChild;
}BiTNode, * BiTree;
 
 
void CreateBiTree(BiTree* bt)
{
	char ch;
	ch = getchar();
	if (ch == '.') *bt = NULL;
	else
	{
		*bt = (BiTree)malloc(sizeof(BiTNode)); //生成一个新结点
		(*bt)->data = ch;
		CreateBiTree(&((*bt)->LChild)); //生成左子树
		CreateBiTree(&((*bt)->RChild)); //生成右子树
	}
}
 
#define  NUM  20
 
void path(BiTree root, BiTNode* r)
{
	BiTNode* p, * q;
	int i, find = 0, top = 0;
	BiTNode* s[NUM];
	q = NULL;   /* 用q保存刚遍历过的结点 */
	p = root;
	while ((p != NULL || top != 0) && !find)
	{
		while (p != NULL)
		{
			top++;
			s[top] = p;
			p = p->LChild;
		}                /* 遍历左子树 */
		if (top > 0)
		{
			p = s[top];       /* 根结点 */
			if (p->RChild == NULL || p->RChild == q)
			{
				if (p == r)   /*找到r所指结点,则显示从根结点到r所指结点之间的路径*/
				{
					for (i = 1; i <= top; i++)
						printf("%c  ", s[i]->data);
					find = 1;
				}
				else
				{
					q = p;        /* 用q保存刚遍历过的结点 */
					top--;
					p = NULL;    /* 跳过前面左遍历,继续退栈 */
				}
			}
			else
				p = p->RChild;     /* 遍历右子树 */
		}
	}
}
/*
void path(BiTree root, char r)
{
	BiTNode  *p, *q;
	int i, find=0, top=0;
	BiTNode *s[NUM];
	q = NULL;   / * 用q保存刚遍历过的结点 * /
	p = root;
	while ( (p != NULL || top != 0) && !find )
	{
		while ( p != NULL )
		{
			top++;
			s[top] = p;
			p = p->LChild;
		}                / * 遍历左子树 * /
		if (top > 0)
		{
			p=s[top];       / * 根结点 * /
			if ( p->RChild == NULL || p->RChild == q )
			{
				if(p->data == r)   / *找到r所指结点,则显示从根结点到r所指结点之间的路径* /
				{
					for(i=1;i<=top;i++)
						printf("%c  ",s[i]->data);
					find=1;
				}
				else
				{
					q = p;        / * 用q保存刚遍历过的结点 * /
					top--;
					p = NULL;    / * 跳过前面左遍历,继续退栈 * /
				}
			}
			else
				p = p->RChild;     / * 遍历右子树 * /
		}
	}
}*/
 
 
void main()
{
	BiTree T;
	BiTNode* p;
	//	char c;
	printf("按扩展先序遍历序列建立二叉树T,请输入序列:\n");
	CreateBiTree(&T);
	/*
		printf("请输入一个字符:");
		fflush(stdin);
		scanf("%c",&c);*/
		//	path(T,c);
	p = T->LChild->RChild->LChild;
	path(T, p);
	getch();
}

解析:求从根结点到某结点间的路径

按扩展先序遍历序列建立二叉树T,请输入序列:
124..57..8..3.6..
1  2  5  7

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/aiqq136/article/details/115738902

智能推荐

SpringBoot框架_流星...的博客-程序员宝宝

SpringBoot框架一、SpringBoot简介1.1 SpringBoot是什么1.2 SpringBoot的特点1.3 SpringBoot的优缺点二、SpringBoot的使用2.1 创建SpringBoot项目2.2 SpringBoot的配置文件2.2.1 pom文件2.2.2 application.properties2.2.2 application.yml3.4 Spring...

远程桌面报错----要求的函数不受支持_努力奋斗的人生的博客-程序员宝宝

本来远程桌面还用的好好的,但是电脑自动更新过之后突然就不能远程了,报错信息如下:然后就在网上面搜索相关信息,基本全都是修改本地计算机策略的。然后按照网上的修改,发现还是不能连。(window10家庭版没有本地组策略?参考文章:win10没有本地组策略怎么办?)然后在网上继续查找,找到了一个解决办法:右击我的电脑(此电脑)--- 属性---远程设置(左上角),然后把红色箭头部分取消选中即可。然后再用我自己的电脑就能远程连上啦!如果这个方法还不行的话,去控制面板---卸载程序---查看已

Java图像处理工具类:实现图像缩放_机器熊技术大杂烩的博客-程序员宝宝

使用Java实现一个简单的图像处理工具类,可完成图像安装一定比例缩放,代码如下:import javax.imageio.ImageIO;import java.awt.*;import java.awt.image.BufferedImage;import java.io.File;import java.io.FileOutputStream;import java.io.IOEx...

【GDOI2018模拟7.10】C_Jacky35的博客-程序员宝宝_【gdoi2018模拟7.10】c

DescriptionInputOutput一行表示答案Sample Inputaa abSample Output2Solution这题直接递归暴力就行了 设暴力带3个参数x,y,l表示上面到x,下面到y,匹配长度为l 预处理一些东西,比如上面第x个字符匹配下面第y个字符之后的第一个是哪个等 加记忆化 就可以过了Code#include<cstdio>#include<cstring>

axios参考封装_wahaha-me的博客-程序员宝宝

http。js/**axios封装 * 请求拦截、相应拦截、错误统一处理 */import axios from 'axios';import QS from 'qs';// import { Toast } from 'vant';import { Message } from "element-ui";import store from '../store/index'//...

随便推点

linux内核编译最详细,Linux内核编译详细教程,linux内核编译_weixin_39969340的博客-程序员宝宝

Linux内核编译详细教程,linux内核编译尝试编译下Linux-kernel 4.14.14,使用Ubuntu 16.04 64位 系统。kernel-4.14.14 内核文件约96MB,解压后得到linux-4.14.14目录约900MB。在终端中切换到解压后的linux-4.14.14文件目录,执行下面的命令:1. .config复制一份当前系统编译时的配置,在/usr/src目录下$ l...

git 创建远程分支 关联远程分支_子静静的博客-程序员宝宝_git 添加远程分支

关联远程分支git branch –set-upstream master origin/master origin: 远程库原因是之前有添加远程repo我们来查看一下git branch -av 注:红色的字体表示远程的repo删除远程repo (使用命令或者修改配置文件) 1.使用命令git remote rm origin

windows 上的 _splitpath 函数在 linux 平台下的简单实现_Sma11_Tim3的博客-程序员宝宝__splitpath() linux

文章转载至:https://blog.csdn.net/a_ran/article/details/41551955在做移植时, 发现了_splitpath 在 linux 下是没有的,于是决定自己写下,也不难。首先百科到如下内容:声明定义void _splitpath( const char *path, char *drive, char *dir, char *fname,...

pcm alaw java_查表法实现PCM与Alaw、μlaw之间的格式转换_weixin_39830917的博客-程序员宝宝

static byte ALawCompressTable[] ={1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,6, 6, 6, 6, 6, 6, 6, 6, 6...

阿里云携手晞司盖工业,赋能设备制造商制造+服务转型升级_阿里开发者的博客-程序员宝宝

简介:此次签署围绕边缘网关设备及相关配套IT软件解决方案展开深入合作,旨在针对制造业OEM型客户共同打造低成本、可复制、高增益的数字化解决方案,实现从底层设备数据采集、清洗、应用到运维的一体化解决方案,帮助更多中小企业实现数字化赋能。随着物联网、大数据、边缘计算等新一代信息技术的不断革新,传统制造业的生产管理模式正在逐渐发生改变,数字化浪潮的涌起也为更多中小型制造企业数字化转型提供了新的动力,这也是为赋能中小企业的数字化转型提供了新的机遇。&nbsp;10月19日,阿里云携手上海晞司盖工业控制有限公司,举行

junit 5 + mockito 编写单元测试_junit5 mockito @resource_云端小飞熊的博客-程序员宝宝

junit 5 + mockito 编写单元测试最近在学习过程中,涉及到了单元测试的小情况,一下就是单元测试的各个层之间的单元测试,一开始只用junit5做测试,后面发现测试的用例涉及到了数据库,不方便合作开发,故此引进mockito如有不当之处,欢迎指正:.dao层:@ExtendWith(SpringExtension.class)@SpringBootTestclass OrganizationMapperTest { @Mock OrganizationMapper organiz

推荐文章

热门文章

相关标签