文档章节

多叉树最短路径

酒逍遥
 酒逍遥
发布于 2017/02/13 14:31
字数 240
阅读 793
收藏 1
<?php
$arr =array('A'=>array('value'=>1,'child_list'=>array('B','C','D')),
'B'=>array('value'=>1,'child_list'=>array('E','F','G')),
'F'=>array('value'=>1,'child_list'=>array('K','L','N')),
'N'=>array('value'=>1,'child_list'=>array('R','S','T')),
'D'=>array('value'=>1,'child_list'=>array('H','I','J')),
'H'=>array('value'=>1,'child_list'=>array('O','P','Q')),
'C'=>array('value'=>1,'child_list'=>array()),
'E'=>array('value'=>1,'child_list'=>array()),
'K'=>array('value'=>1,'child_list'=>array()),
'L'=>array('value'=>1,'child_list'=>array()),
'G'=>array('value'=>1,'child_list'=>array()),
'R'=>array('value'=>1,'child_list'=>array()),
'S'=>array('value'=>1,'child_list'=>array()),
'T'=>array('value'=>1,'child_list'=>array()),
'I'=>array('value'=>1,'child_list'=>array()),
'J'=>array('value'=>1,'child_list'=>array()),
'O'=>array('value'=>1,'child_list'=>array()),
'P'=>array('value'=>1,'child_list'=>array()),
'Q'=>array('value'=>1,'child_list'=>array()),
);

function find_path($nodeA,$nodeB){
	global $arr;
	$rootA = find_root($nodeA);
	$rootB = find_root($nodeB);
	if(!$rootA) $rootA[]=$nodeA;
	else $outA[] = $nodeA;
	if(!$rootB) $rootB[]=$nodeB;
	else $outB[] = $nodeB;
	foreach($rootA as $v){
		$outA[] = $v;
		if(in_array($v,$rootB)){
			foreach($rootB as $va){
				if($va == $v) break;
				else $outB[] =$va;
			}
			if($outB) $outB = array_reverse($outB);
			break;
		}
	}
	if($outA) echo implode('=>',$outA);
	if($outB) echo '=>'.implode('=>',$outB);
}

function find_root($node,$root=array()){
	global $arr;
	foreach($arr as $k=>$v){
		if(in_array($node,$v['child_list'])){
			$root[]=$k;
			return find_root($k,$root);
		}
	}
	return $root;
}
find_path('G','R');
?>

输出 G=>B=>F=>N=>R

© 著作权归作者所有

共有 人打赏支持
酒逍遥

酒逍遥

粉丝 48
博文 40
码字总数 35454
作品 0
武汉
高级程序员
私信 提问
数据结构之树

数据结构之树 目录: 二叉树的结构 二叉树的性质 二叉树的遍历 二叉树的特例 二叉树典型程序 树是一种编程中常常用到的一种数据结构,它的逻辑是:除了根结点之外每个结点只有一个父结点,根...

花开半夏qb
2016/11/29
0
0
Algo-Practice: 算法实践(JavaScript & Java),排序,查找、树、两指针、动态规划等

记录一些算法实践 目录 Java篇 一、基础算法 七种基础排序 二叉堆 K选取问题 链表判环问题 N皇后问题 两指针扫描算法举例 位运算(求首个bit1,求bit1的个数,寻找奇数项) 最小栈的实现 横纵有...

qcer
2017/12/20
0
0
[算法总结] 20 道题搞定 BAT 面试——二叉树

本文首发于我的个人博客:尾尾部落 0. 几个概念 完全二叉树:若二叉树的高度是h,除第h层之外,其他(1h-1)层的节点数都达到了最大个数,并且第h层的节点都连续的集中在最左边。想到点什么没...

繁著
09/04
0
0
树/二叉树(哈夫曼树/红黑树)笔记

1.树是一种常用数据结构,它是非线性结构。 2.树中任一普通节点可以有0或者多个子节点,但只能有一个父节点。 根节点没有父节点,叶子节点没有子节点。 3.二叉树: 1)每个节点最多只能有两个...

6pker
2015/08/14
0
0
【算法系列 五】 树和图

二叉搜索树的后序遍历序列(九度1367) 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 与此题相...

Hosee
2016/08/08
173
0

没有更多内容

加载失败,请刷新页面

加载更多

大数据学习之大数据技术笔记—spring入门

篇一 spring介绍 spring.io 官网 快速开始 Aop 面向切面编程,可以任何位置,并且可以细致到方法上 连接框架与框架 Spring 就是 IOC AOP 思想 有效的组织中间层对象一般都是切入 service 层 ...

董黎明
2分钟前
0
0
Linux如何查看进程、杀死进程、启动进程等常用命令

关键字: linux 查进程、杀进程、起进程 1.查进程 ps命令查找与进程相关的PID号: ps a 显示现行终端机下的所有程序,包括其他用户的程序。 ps -A 显示所有程序。 ps c 列出程序时,显示每个程...

临江仙卜算子
20分钟前
3
0
ASP.NET Core MVC 静态文件配置

在启动文件中添加以下配置 public class Startup{ public IServiceProvider ConfigureServices(IServiceCollection services) { services.AddDirectoryBrowser(); ......

whltian
30分钟前
1
0
linux之自定义命令

本人使用的是ubuntu系统,不喜欢建各种桌面快捷链接,但是每次启动个软件,去查找又麻烦,所以自定义了命令,来快捷的启动应用: 1、修改/etc/bash.bashrc,在文件末尾,加上如下List-1中的内...

克虏伯
38分钟前
6
0
linux基础

系统安全 sudo su chmod setfacl 进程管理 w top ps kill pkill pstree killall 用户管理 id usermod useradd groupad userdel 文件系统 mount umount fsck df du 网络应用 curl telnet mail......

关元
39分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部