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

1<?php
2
3/********************************************************
4* 我写的PHP都是从C语言的数据结构中演化而来************************
5**************************************************************
6/**
7 *    ******二叉树图****
8      *      A                    * 
9      *     * *                   * 
10      *    *   *                  * 
11      *   B     C                *       
12      *        *                   * 
13      *       *                    *
14      *      D                    *  
15      *       *                    *
16      *         *E                *
17      ******************
18
19 * PHP- 链式二叉树的遍历---先序遍历（根,左,右）-中序遍历(左,根,右)-后序遍历(左,右，根)
20 * 先 A B C D E
21 * 中 B A D E C
22 * 后 B E D C A
23 * @Author 任孟洋 
24 * @time   2013-8-10
25 ****/
26 
27
28 Class  BTreeNode{
29      
30         public  $data ; //数据域
31         public  $LeftHand  = NULL ; //左指针
32         public  $RightHand = NULL ; //右指针
33
34	      public function  __construct($data){
35	    
36		        if(!empty($data))
37		        {
38
39		        	$this->data = $data;
40		        }
41	      }
42	      
43	      
44          //先序遍历（根，左，右）递归实现
45	      public  function PreTraverseBTree($BTree){
46
47	             if (NULL !== $BTree)
48	             {           	
49	               var_dump($BTree->data);  //根
50
51	               if (NULL !== $BTree->LeftHand)
52	                {
53	                   $this->PreTraverseBTree($BTree->LeftHand); //递归遍历左树
54	                }
55	       
56	                
57	               if (NULL !== $BTree->RightHand)
58	                {
59	                   $this->PreTraverseBTree($BTree->RightHand); //递归遍历右树
60	                }
61	               
62	             } 
63	        }
64
65	       //中序遍历(左，根，右)递归实现
66	       public  function  InTraverseBTree($BTree){
67	             
68	             if (NULL !== $BTree)
69	             {              
70	               if (NULL !== $BTree->LeftHand)
71	                {
72	                   $this->InTraverseBTree($BTree->LeftHand); //递归遍历左树
73	                }
74	       
75	                var_dump($BTree->data); //根 
76
77	               if (NULL !== $BTree->RightHand)
78	                {
79	                   $this->InTraverseBTree($BTree->RightHand); //递归遍历右树
80	                }
81	               
82	             } 
83	             
84	       }
85
86	       //后序遍历(左，右，根)递归实现
87	      public  function  FexTarverseBTree($BTree){
88               
89                if (NULL !== $BTree)
90	             {
91	               if (NULL !== $BTree->LeftHand)
92	                {
93	                   $this->FexTarverseBTree($BTree->LeftHand); //递归遍历左树
94	                }
95	       
96	                
97	               if (NULL !== $BTree->RightHand)
98	                {
99	                   $this->FexTarverseBTree($BTree->RightHand); //递归遍历右树
100	                }
101	                var_dump($BTree->data); //根
102	             } 
103	       } 
104}
105 
106 header("Content-Type:text/html;charset=utf-8");
107 echo '先的内存为'.var_dump(memory_get_usage());
108 echo '<hr/>';
109 
110   //创建五个节点
111   $A  = new  BTreeNode('A');
112   $B  = new  BTreeNode('B');
113   $C  = new  BTreeNode('C');
114   $D  = new  BTreeNode('D');
115   $E  = new  BTreeNode('E');
116   
117
118   //连接形成一个二叉树
119
120   $A->LeftHand  = $B;
121   $A->RightHand = $C;
122   $C->LeftHand  = $D;
123   $D->RightHand = $E;
124   
125   //先序遍历
126   echo '先序遍历的结果'.'<br>';
127   $A->PreTraverseBTree($A);
128
129   echo '<br/>中序遍历的结果'.'<br>';
130   $A->InTraverseBTree($A);
131
132   echo  '<br/>后序列遍历的结果'.'<br/>';
133   $A->FexTarverseBTree($A);
134
135   echo '<hr/>';
136   echo '后的内存为'.var_dump(memory_get_usage());