您现在的位置是:首页 > web开发 > php 二叉树 与赫夫曼树

php 二叉树 与赫夫曼树

web开发作者:dayu日期:5天前点击:1

在学习图之前,中间休息了两天,感觉二叉树需要消化一下。所以中间去温习了下sql,推荐一本工具书《程序员的SQL金典》看名字不像一本好书,但是作为一个不错的SQL工具书还是可以小小备忘一下。涵盖内容不详细但是挺广,覆盖多种主流数据库


言归正传,以前知道折半查找,二叉树的概念也是感觉挺有意思,二叉树的实现有一个案例很不错,代码如下

classBiNode{
	public$data;
	public$lchild;
	public$rchild;
	publicfunction__construct($data){
			$this->data=$data;//节点数据
			$this->lchild=null;//左子节点指针
			$this->rchild=null;//右指针
	}
}
classLinkBiTree{
	private$root;//根节点
privatestatic$count;	//结点总数
	constMAX_LEVEL=2;
	
	publicfunction__construct(){
		$this->root=null;
		self::$count=0;	
	}

	publicfunctionClearBiTree(){
		$this->clearTree($this->root);
	}

	/**
	*@param$root树的根节点
	*
	*/

	publicfunctionclearTree($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. publicfunctionPreOrderTraverse(){
    $this->preTraverse($this->root);
    returnself::$preArr;
    }
    //还是递归调用,不对,
    privatefunctionpreTraverse(){
    if($root){
    self::$preArr[]=$root->data;
    //这里可以把数据都存进去也可以做其他操作或者业务逻辑function()
    $this->preTraverse($root->lchild);
    $this->preTraverse($root->rchild);
    }
    }
  3. 中序递归实现如下

  4. publicfunctionInOrderTraverse(){
    $this->inTraverse($this->root);
    returnself::$inArr;
    }
    privatefunctioninTraverse(){
    if($root){
    $this->inTraverse($root->lchild);
    self::$inArr[]=$root->data;
    //这里可以把数据都存进去也可以做其他操作或者业务逻辑function()
    $this->inTraverse($root->rchild);
    }
    }
  5. 后续递归实现如下

  6. publicfunctionPostOrderTraverse(){
    		$this->postTraverse($this->root);
    		returnself::$postArr;
    	}
    	privatefunctionpostTraverse(){
    		if($root){
    			$this->postTraverse($root->lchild);
    			self::$postArr[]=$root->data;
    			//这里可以把数据都存进去也可以做其他操作或者业务逻辑function()
    			
    			$this->postTraverse($root->rchild);
    		}
    	}
  7. 层序递归实现如下

  8. //我个人还是挺喜欢层序遍历
    	publicfunctionLevelOrderTraverse(){
    		for($i=1;$i<=$this->BiTreeDepth();$i++){
    			$this->LevelOrderTraverse($this->root,$i);
    		}
    		returnself::$levelArr;
    	}
    	privatefunctionleverTraverse($root,$level){
    		if($root){
    			if($level==1){
    				self::$levelArr[]=$root->data;
    			}
    			$this->LevelOrderTraverse($root->lchild,$level-1);
    			$this->LevelOrderTraverse($root->rchild,$level-1);
    		}
    	}

记录一下。其实有时候在想,写程序的同事,真的要做点其他的。但行好事,莫问前程


愿法界众生,皆得安乐。

本文出自 “一站式解决方案” 博客,请务必保留此出处http://10725691.blog.51cto.com/10715691/1951446

php 二叉树 与赫夫曼树

原文地址:http://10725691.blog.51cto.com/10715691/1951446


下一篇       上一篇