在学习图之前,中间休息了两天,感觉二叉树需要消化一下。所以中间去温习了下sql,推荐一本工具书《程序员的SQL金典》看名字不像一本好书,但是作为一个不错的SQL工具书还是可以小小备忘一下。涵盖内容不详细但是挺广,覆盖多种主流数据库
言归正传,以前知道折半查找,二叉树的概念也是感觉挺有意思,二叉树的实现有一个案例很不错,代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
class
BiNode{
public
$data
;
public
$lchild
;
public
$rchild
;
public
function
__construct(
$data
){
$this
->data =
$data
;
//节点数据
$this
->lchild = null;
//左子节点指针
$this
->rchild = null;
//右指针
}
}
class
LinkBiTree{
private
$root
;
//根节点
private
static
$count
;
//结点总数
const
MAX_LEVEL = 2;
public
function
__construct(){
$this
->root = null;
self::
$count
= 0;
}
public
function
ClearBiTree(){
$this
->clearTree(
$this
->root);
}
/**
*@param $root 树的根节点
*
*/
public
function
clearTree(
$root
){
if
(
$root
){
if
(
$root
->lchild){
$this
->clearTree(
$root
->lchild);
}
if
(
$root
->rchild){
$this
->clearTree(
$root
->rchild);
}
unset(
$root
);
$root
=null;
}
}
}
|
其实我更加感兴趣的就是赫夫曼树,能够给我带来感觉得才让我激动,就是100以内猜七次肯定可以猜出来,这种感觉是很奇妙的,当年赫夫曼为了传输点卯,更改了数据的排列顺序,形成了新的储存序列和标识,是的竟成使用的字母快速找出来,节省了资源,很棒。
赫尔曼构造算法的实现
初始化HT
输入初始n个叶子结点:置HT[1…n]的weight值
然后根据权值来重新安排叶子结点,可以先序可以中序可以后续也可以中序,只要距离根节点的搜索顺序在前面就好
-
先序递归实现如下
-
12345678910111213
public
function
PreOrderTraverse(){
$this
->preTraverse(
$this
->root);
return
self::
$preArr
;
}
//还是递归调用,不对,
private
function
preTraverse(){
if
(
$root
){
self::
$preArr
[]=
$root
->data;
//这里可以把数据都存进去也可以做其他操作或者业务逻辑function()
$this
->preTraverse(
$root
->lchild);
$this
->preTraverse(
$root
->rchild);
}
}
-
中序递归实现如下
-
123456789101112
public
function
InOrderTraverse(){
$this
->inTraverse(
$this
->root);
return
self::
$inArr
;
}
private
function
inTraverse(){
if
(
$root
){
$this
->inTraverse(
$root
->lchild);
self::
$inArr
[]=
$root
->data;
//这里可以把数据都存进去也可以做其他操作或者业务逻辑function()
$this
->inTraverse(
$root
->rchild);
}
}
-
后续递归实现如下
-
12345678910111213
public
function
PostOrderTraverse(){
$this
->postTraverse(
$this
->root);
return
self::
$postArr
;
}
private
function
postTraverse(){
if
(
$root
){
$this
->postTraverse(
$root
->lchild);
self::
$postArr
[]=
$root
->data;
//这里可以把数据都存进去也可以做其他操作或者业务逻辑function()
$this
->postTraverse(
$root
->rchild);
}
}
-
层序递归实现如下
-
12345678910111213141516
//我个人还是挺喜欢层序遍历
public
function
LevelOrderTraverse(){
for
(
$i
=1;
$i
<=
$this
->BiTreeDepth();
$i
++){
$this
->LevelOrderTraverse(
$this
->root,
$i
);
}
return
self::
$levelArr
;
}
private
function
leverTraverse(
$root
,
$level
){
if
(
$root
){
if
(
$level
==1){
self::
$levelArr
[]=
$root
->data;
}
$this
->LevelOrderTraverse(
$root
->lchild,
$level
-1);
$this
->LevelOrderTraverse(
$root
->rchild,
$level
-1);
}
}
记录一下。其实有时候在想,写程序的同事,真的要做点其他的。但行好事,莫问前程
愿法界众生,皆得安乐。
本文转自 jackdongting 51CTO博客,原文链接:http://blog.51cto.com/10725691/1951446