您现在的位置是:首页 > 正文

二叉树从根节点到r所指节点之间的路径并输出算法【C/C++】

2024-04-01 02:51:31阅读 2


前言

保存一下自己对二叉树从根节点到r所指节点之间的路径并输出算法的理解。

在这里偷懒了,没有调自己的栈的api函数,用的stl里的栈。不过无伤大雅,重要的是思想。

对于二叉树从根节点到r所指节点之间的路径的算法,首先要明白是先找到r所指的节点,然后不断出栈,这就有点类似与先输出子节点再输出父节点,因此该算法的模型即为二叉树的非递归的后序遍历。

这里虽然用了stl,但主要还是以C/C++为主。


思路

1.先递归建树

//先序递归建树,以'.'表示NULL
void PreOrderCreateTree(BiTree* bt) {
	ElemType temp;
	cin >> temp;
	if (temp == '.') {
		(*bt) == NULL;
	}
	else {
		Node* s = (Node*)malloc(sizeof(Node));
		s->data = temp;
		s->lchild = s->rchild = NULL;
		*bt = s;
		PreOrderCreateTree(&(*bt)->lchild);
		PreOrderCreateTree(&(*bt)->rchild);
	}
	return;
}

2.为r节点写按值寻找的算法

//按值查找二叉树,返回其节点。
void SearchTree(BiTree bt, ElemType key, Node** p) {
	if (bt == NULL) {
		return;
	}
	else {
		//如果找到key,那么就修改p指针,否则p指针一直为NULL;
		if (bt->data == key) {
			*p = bt;
		}
		else {
			SearchTree(bt->lchild, key, p);
			SearchTree(bt->rchild, key, p);
		}
	}
}

3.路径输出算法

以二叉树的非递归的后序遍历的模板,当出栈元素为r节点时,弹空栈。

if (tmp == p) {
	while (!S.empty()) {
		BiTreeNode* pop = S.top();
		printf("%c ", pop->data);
		S.pop();
	}
	return;
}
else {
	pre = cur;
	S.pop();
	cur = NULL;
}

4.测试结果

在这里插入图片描述

完整代码如下

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<stack>
#define ElemType char
using namespace std;

//二叉树的存储结构
typedef struct Node {
	ElemType data;
	struct Node* lchild;
	struct Node* rchild;
}Node, * BiTree;

//先序递归建树,以'.'表示NULL
void PreOrderCreateTree(BiTree* bt) {
	ElemType temp;
	cin >> temp;
	if (temp == '.') {
		(*bt) == NULL;
	}
	else {
		Node* s = (Node*)malloc(sizeof(Node));
		s->data = temp;
		s->lchild = s->rchild = NULL;
		*bt = s;
		PreOrderCreateTree(&(*bt)->lchild);
		PreOrderCreateTree(&(*bt)->rchild);
	}
	return;
}

//按值查找二叉树,返回其节点。
void SearchTree(BiTree bt, ElemType key, Node** p) {
	if (bt == NULL) {
		return;
	}
	else {
		//如果找到key,那么就修改p指针,否则p指针一直为NULL;
		if (bt->data == key) {
			*p = bt;
		}
		else {
			SearchTree(bt->lchild, key, p);
			SearchTree(bt->rchild, key, p);
		}
	}
}

//二叉树从根节点到r所指节点之间的路径并输出算法
void Path(BiTree bt, Node* r) {
	if (bt == NULL) {
		return;
	}
	Node* node = bt;
	Node* pre = NULL;
	stack<Node*>S;
	while (node != NULL || !S.empty()) {
		if (node != NULL) {
			S.push(node);
			node = node->lchild;
		}
		else {
			Node* top = S.top();
			if (top->rchild == NULL || top->rchild == pre) {
				//如果找到r指针,那么直接弹栈直至栈空即可。否则按正常弹栈。
				if (top == r) {
					while (!S.empty()) {
						Node* tmp = S.top();
						printf("%c ", tmp->data);
						S.pop();
					}
					return;
				}
				else {
					pre = top;
					S.pop();
					node = NULL;
				}
			}
			else {
				node = top->rchild;
			}
		}
	}
}

void test() {
	BiTree bt = NULL;
	PreOrderCreateTree(&bt);
	Node* p = NULL;
	SearchTree(bt, 'E', &p);
	Path(bt, p);
	return;
}

int main() {
	test();/*测试用例 ABD..E..CF... */
	//输出E B A
	return 0;
}

网站文章

  • 安卓相关测试

    安卓相关测试

    环境准备:网易Mumu安卓模拟器,里面还有adb方便调试: http://mumu.163.com/baidu/adb: brew cask install android-platform-tools动态调试adb连接,mac下网易mumu端口是5555,windows下是7555windows下:adb connect 127.0.0.1:7555adb shell...

    2024-04-01 02:51:24
  • SGI STL学习笔记(2):traits编程技法

    traits编程技法

    2024-04-01 02:51:17
  • 深度学习入门

    深度学习入门

    ---恢复内容开始---Softmax函数,或称归一化指数函数是逻辑函数的一种推广。它能将一个含任意实数的K维向量“压缩”到另一个K维实向量中,使得每一个元素的范围都在之间,并且所有元素的和为1。该函数的形式通常按下面的式子给出: forj= 1, …,K.wiki的资料看完了,就感觉softmax的作用只有归一化。cross-entropy loss...

    2024-04-01 02:51:11
  • Java跨域请求代码

    1、get请求的方式get请求中,如果拼接的参数字符串中带有空格,后台会报错无法请求成功,适用于通过属性值查询对象接口。import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.net.HttpURLConnection;import j...

    2024-04-01 02:50:29
  • 如何在一个页面中动态放置多个Droppable来接受不同的Draggable?(accept参数的用法)...

    如何在一个页面中动态放置多个Droppable来接受不同的Draggable?(accept参数的用法)...

    工作中遇到这个问题,问别人解决了。答案在问题的下半部分,仅供参考。http://stackoverflow.com/questions/6501812/how-to-use-danymic-accept-value-in-jqueryui-droppable 点击下载免费的敏捷开发教材:《火星人敏捷开发手册》转载于:https://www.cnblogs.com/JPAORM/...

    2024-04-01 02:50:24
  • 一种有趣的弱监督机器学习问题:比例标签学习(Learning from label proportions)

    一种有趣的弱监督机器学习问题:比例标签学习(Learning from label proportions)

    欢迎使用Markdown编辑器 你好! 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章,了解一下Markdown的基本语法...

    2024-04-01 02:50:16
  • sublime某些插件出现'Node.js was not find ...' 的解决方法

    丫路径中又中文吧。。step1: find "HTMLPrettify.py" and make a backup, it should be here ~/Library/Application\ Support/Sublime\ Text\ 2/Packages/HTML-CSS-JS\ Prettify/HTMLPrettify.pystep2: line 83, rep

    2024-04-01 02:49:35
  • Java程序员如何通过跳槽薪资翻倍?java开发项目经验描述

    Java程序员如何通过跳槽薪资翻倍?java开发项目经验描述

    一、面试官考点之索引是什么?索引是一种能提高数据库查询效率的数据结构。它可以比作一本字典的目录,可以帮你快速找到对应的记录。索引一般存储在磁盘的文件中,它是占用物理空间的。正所谓水能载舟,也能覆舟。适...

    2024-04-01 02:49:26
  • impress.js css模板,impress.js 使用教程

    一、官方示例文件构成impress:jsimpress.js(JavaScript文件,提供特效支持,核心库)cssimpress_demo.css(CSS文件,提供样式支持)htmlindex.html(HTML文件,幻灯片入口)二、HTML说明头部html>impress.js支持反馈当浏览器不支持时会显示,可改写错误信息的内容。你的浏览器不支持impress.js你可以下载Chr...

    2024-04-01 02:49:19
  • Linux系统编程之进程间通信方式介绍 最新发布

    通信方式效果无名管道速度慢,容量有限,只有父子进程能通讯命名管道 (FIFO)任何进程间都能通讯,但速度慢消息队列容量受到系统限制,且要注意第一次读的时候,要考虑上一次没有读完数据的问题共享内存能够很...

    2024-04-01 02:48:35