数据结构之利用PHP实现二分搜索树(3)

/** * 后序遍历 */ public function rearTraversal() { $this->recursionRearTraversal($this->root, 0); } /** * 后序遍历的递归 */ public function recursionRearTraversal($root, $sign_num) { if ($root == null) { echo $this->getSign($sign_num);//打印深度 echo "null<br>"; return; } $this->recursionRearTraversal($root->left, $sign_num + 1); $this->recursionRearTraversal($root->right, $sign_num + 1); echo $this->getSign($sign_num);//打印深度 echo $root->e . "<br>"; }

下面是打印结果:

<?php
require 'BinarySearchTree.php';
$binarySearchTree = new BinarySearchTree();
$binarySearchTree->add(45);
$binarySearchTree->add(30);
$binarySearchTree->add(55);
$binarySearchTree->add(25);
$binarySearchTree->add(35);
$binarySearchTree->add(50);
$binarySearchTree->add(65);
$binarySearchTree->add(15);
$binarySearchTree->add(27);
$binarySearchTree->add(31);
$binarySearchTree->add(48);
$binarySearchTree->add(60);
$binarySearchTree->add(68);
//下面是预期想要的结果
/**
 *                     45
 *           /                  
 *          30                   55
 *        /                    /   
 *      25       35         50       65
 *     /       /          /       /  
 *   15   27  31         48       60     68
 *
 */
$binarySearchTree->rearTraversal();
/**
打印输出
--------------------null
--------------------null
---------------15
--------------------null
--------------------null
---------------27
----------25
--------------------null
--------------------null
---------------31
---------------null
----------35
-----30
--------------------null
--------------------null
---------------48
---------------null
----------50
--------------------null
--------------------null
---------------60
--------------------null
--------------------null
---------------68
----------65
-----55
45
 */

代码仓库 ：https://gitee.com/love-for-po...

总结