文档章节

多叉树最短路径

酒逍遥
 酒逍遥
发布于 2017/02/13 14:31
字数 240
阅读 783
收藏 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
算法之路

最近在GitHub上看到的某位学友的算法学习规划,贴过来与各位共勉。有新的内容可以文末留言补充。 学习方法 把所有经典算法写一遍 看算法有关源码 加入算法学习社区,相互鼓励学习 看经典书籍...

李序锴
2017/11/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

CentOS7防火墙firewalld操作

firewalld Linux上新用的防火墙软件,跟iptables差不多的工具。 firewall-cmd 是 firewalld 的字符界面管理工具,firewalld是CentOS7的一大特性,最大的好处有两个:支持动态更新,不用重启服...

dingdayu
今天
1
0
关于组件化的最初步

一个工程可能会有多个版本,有国际版、国内版、还有针对各种不同的渠道化的打包版本、这个属于我们日常经常见到的打包差异化版本需求。 而对于工程的开发,比如以前的公司,分成了有三大块业...

DannyCoder
今天
2
0
Spring的Resttemplate发送带header的post请求

private HttpHeaders getJsonHeader() { HttpHeaders headers = new HttpHeaders(); MediaType type = MediaType.parseMediaType("application/json; charset=UTF-8"); ......

qiang123
昨天
3
0
Spring Cloud Gateway 之 Only one connection receive subscriber allowed

都说Spring Cloud Gateway好,我也来试试,可是配置了总是报下面这个错误: java.lang.IllegalStateException: Only one connection receive subscriber allowed. 困扰了我几天的问题,原来...

ThinkGem
昨天
27
0
学习设计模式——观察者模式

1. 认识观察者模式 1. 定义:定义对象之间一种一对多的依赖关系,当一个对象状态发生变化时,依赖该对象的其他对象都会得到通知并进行相应的变化。 2. 组织结构: Subject:目标对象类,会被...

江左煤郎
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部