文档章节

PHP数据结构之实现链式二叉树与遍历

小洋哥
 小洋哥
发布于 2013/08/13 23:12
字数 398
阅读 899
收藏 15
<?php

/********************************************************
* 我写的PHP都是从C语言的数据结构中演化而来************************
**************************************************************
/**
 *    ******二叉树图****
      *      A                    * 
      *     * *                   * 
      *    *   *                  * 
      *   B     C                *       
      *        *                   * 
      *       *                    *
      *      D                    *  
      *       *                    *
      *         *E                *
      ******************

 * PHP- 链式二叉树的遍历---先序遍历(根,左,右)-中序遍历(左,根,右)-后序遍历(左,右,根)
 * 先 A B C D E
 * 中 B A D E C
 * 后 B E D C A
 * @Author 任孟洋 
 * @time   2013-8-10
 ****/
 

 Class  BTreeNode{
      
         public  $data ; //数据域
         public  $LeftHand  = NULL ; //左指针
         public  $RightHand = NULL ; //右指针

	      public function  __construct($data){
	    
		        if(!empty($data))
		        {

		        	$this->data = $data;
		        }
	      }
	      
	      
          //先序遍历(根,左,右)递归实现
	      public  function PreTraverseBTree($BTree){

	             if (NULL !== $BTree)
	             {           	
	               var_dump($BTree->data);  //根

	               if (NULL !== $BTree->LeftHand)
	                {
	                   $this->PreTraverseBTree($BTree->LeftHand); //递归遍历左树
	                }
	       
	                
	               if (NULL !== $BTree->RightHand)
	                {
	                   $this->PreTraverseBTree($BTree->RightHand); //递归遍历右树
	                }
	               
	             } 
	        }

	       //中序遍历(左,根,右)递归实现
	       public  function  InTraverseBTree($BTree){
	             
	             if (NULL !== $BTree)
	             {              
	               if (NULL !== $BTree->LeftHand)
	                {
	                   $this->InTraverseBTree($BTree->LeftHand); //递归遍历左树
	                }
	       
	                var_dump($BTree->data); //根 

	               if (NULL !== $BTree->RightHand)
	                {
	                   $this->InTraverseBTree($BTree->RightHand); //递归遍历右树
	                }
	               
	             } 
	             
	       }

	       //后序遍历(左,右,根)递归实现
	      public  function  FexTarverseBTree($BTree){
               
                if (NULL !== $BTree)
	             {
	               if (NULL !== $BTree->LeftHand)
	                {
	                   $this->FexTarverseBTree($BTree->LeftHand); //递归遍历左树
	                }
	       
	                
	               if (NULL !== $BTree->RightHand)
	                {
	                   $this->FexTarverseBTree($BTree->RightHand); //递归遍历右树
	                }
	                var_dump($BTree->data); //根
	             } 
	       } 
}
 
 header("Content-Type:text/html;charset=utf-8");
 echo '先的内存为'.var_dump(memory_get_usage());
 echo '<hr/>';
 
   //创建五个节点
   $A  = new  BTreeNode('A');
   $B  = new  BTreeNode('B');
   $C  = new  BTreeNode('C');
   $D  = new  BTreeNode('D');
   $E  = new  BTreeNode('E');
   

   //连接形成一个二叉树

   $A->LeftHand  = $B;
   $A->RightHand = $C;
   $C->LeftHand  = $D;
   $D->RightHand = $E;
   
   //先序遍历
   echo '先序遍历的结果'.'<br>';
   $A->PreTraverseBTree($A);

   echo '<br/>中序遍历的结果'.'<br>';
   $A->InTraverseBTree($A);

   echo  '<br/>后序列遍历的结果'.'<br/>';
   $A->FexTarverseBTree($A);

   echo '<hr/>';
   echo '后的内存为'.var_dump(memory_get_usage());




© 著作权归作者所有

共有 人打赏支持
小洋哥
粉丝 23
博文 73
码字总数 39565
作品 0
成都
程序员
私信 提问
加载中

评论(1)

旁边白
旁边白
用array赛,php的array太好用了
数据结构-二叉树的存储结构与遍历

定义 一个有穷的结点集合,可以为空。若不为空,则它是由根结点和称为其左子树和右子树的两个互不相交的二叉树组成。 二叉树的五种基本形态: tree_state 二叉树的子树是有顺序之分的,称为左...

IAM四十二
2017/10/24
0
0
二叉树的性质以及二叉树的遍历(非递归)(c语言)(一)

二叉树的性质: 性质 1 在二叉树的第i层上至多有2^(i-1)个结点(i>=1)。 性质 2 深度为k的二叉树至多有2^k-1个结点,(k>=1)。 性质 3 任何一颗二叉树,终端结点为n0,度为2的结点为n2,那...

奔跑的码农
2016/05/14
196
0
C语言/C++编程新手入门基础知识整理学习

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
04/01
0
0
Java数据结构和算法 - 二叉树

前言 数据结构可划分为线性结构、树型结构和图型结构三大类。前面几篇讨论了数组、栈和队列、链表都是线性结构。树型结构中每个结点只允许有一个直接前驱结点,但允许有一个以上直接后驱结点...

fireway
08/23
0
0
线索二叉树及其遍历

遍历二叉树就是以一定的规则将二叉树中的节点排列成一个线性序列,从而得到二叉树节点的各种遍历序列,其实质是:对一个非线性的结构进行线性化。使得在这个访问序列中每一个节点都有一个直接...

robin_Xu_shuai
2016/03/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Supervisor管理springboot应用

目录 概述 环境准备 spring boot应用 supervisor配置 启动应用 概述 前面博文介绍了Supervisor进程管理,实际应用可以对springboot应用进行管理,如果springboot应用挂掉,Supervisor还可以对它...

java_龙
8分钟前
1
0
将神经网络训练成一个“放大镜”

摘要: 想不想将神经网络训练成一个“放大镜”?我们就训练了一个这样炫酷的神经网络,点击文章一起看下吧! 低分辨率蝴蝶的放大 当我们网购时,我们肯定希望有一个贴近现实的购物体验,也就...

阿里云官方博客
8分钟前
0
0
在细节消息中包含能够捕获失败的信息(63)

程序由于未被捕获异常失败时,系统会自动打印该异常的堆栈轨迹 包含异常的字符串表示法(toString) 通常包含异常的类名,以及紧随其后的细节信息(detail message) 是检查程序失败的必须信...

Java搬砖工程师
9分钟前
0
0
day173-2018-12-10-英语流利阅读-待学习

如何评价特朗普在此次 G20 上的表现? 毛西 2018-12-10 1.今日导读 在公众眼里,特朗普一直是个不省事的主——他爱在推特吐槽,还喜欢到处树敌。但最近,阿根廷首都布宜诺斯艾利斯举行的 G2...

飞鱼说编程
11分钟前
1
0
adr adrl ldr mov简单科普

ADR是一条小范围的地址读取伪指令,它将基于PC的相对偏移的地址值读到目标寄存器中。格式:ADR register,exper。 编译源程序时,汇编器首先计算当前PC值(当前指令位置)到exper的距离,然后用...

天王盖地虎626
17分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部