本文共 2763 字，大约阅读时间需要 9 分钟。
在学习图之前，中间休息了两天，感觉二叉树需要消化一下。所以中间去温习了下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值
然后根据权值来重新安排叶子结点，可以先序可以中序可以后续也可以中序，只要距离根节点的搜索顺序在前面就好
先序递归实现如下
| 1 2 3 4 5 6 7 8 9 10 11 12 13 | 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); } } |
中序递归实现如下
| 1 2 3 4 5 6 7 8 9 10 11 12 | 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); } } |
后续递归实现如下
| 1 2 3 4 5 6 7 8 9 10 11 12 13 | 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); } } |
层序递归实现如下
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | //我个人还是挺喜欢层序遍历 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
转载地址：http://vhnlx.baihongyu.com/