PHP Class&Object -- PHP 自排序二叉树的深入解析

yipeiwu_com7年前PHP代码库
在节点之间再应用一些排序逻辑,二叉树就能提供出色的组织方式。对于每个节点,都让满足所有特定条件的元素都位于左节点及其子节点。在插入新元素时,我们需要从树的第一个节 点(根节点)开始,判断它属于哪一侧的节点,然后沿着这一侧找到恰当的位置,类似地,在读取数据时,只需要使用按序遍历方法来遍历二叉树。
复制代码 代码如下:

<?php
ob_start();
// Here we need to include the binary tree class
Class Binary_Tree_Node() {
   // You can find the details at
}
ob_end_clean();
// Define a class to implement self sorting binary tree
class Sorting_Tree {
    // Define the variable to hold our tree:
    public $tree;
    // We need a method that will allow for inserts that automatically place
    // themselves in the proper order in the tree
    public function insert($val) {
        // Handle the first case:
        if (!(isset($this->tree))) {
            $this->tree = new Binary_Tree_Node($val);
        } else {
            // In all other cases:
            // Start a pointer that looks at the current tree top:
            $pointer = $this->tree;
            // Iteratively search the tree for the right place:
            for(;;) {
                // If this value is less than, or equal to the current data:
                if ($val <= $pointer->data) {
                    // We are looking to the left ... If the child exists:
                    if ($pointer->left) {
                        // Traverse deeper:
                        $pointer = $pointer->left;
                    } else {
                        // Found the new spot: insert the new element here:
                        $pointer->left = new Binary_Tree_Node($val);
                        break;
                    }
                } else {
                    // We are looking to the right ... If the child exists:
                    if ($pointer->right) {
                        // Traverse deeper:
                        $pointer = $pointer->right;
                    } else {
                        // Found the new spot: insert the new element here:
                        $pointer->right = new Binary_Tree_Node($val);
                        break;
                    }
                }
            }
        }
    }

    // Now create a method to return the sorted values of this tree.
    // All it entails is using the in-order traversal, which will now
    // give us the proper sorted order.
    public function returnSorted() {
        return $this->tree->traverseInorder();
    }
}
// Declare a new sorting tree:
$sort_as_you_go = new Sorting_Tree();
// Let's randomly create 20 numbers, inserting them as we go:
for ($i = 0; $i < 20; $i++) {
    $sort_as_you_go->insert(rand(1,100));
}
// Now echo the tree out, using in-order traversal, and it will be sorted:
// Example: 1, 2, 11, 18, 22, 26, 32, 32, 34, 43, 46, 47, 47, 53, 60, 71,
//   75, 84, 86, 90
echo '<p>', implode(', ', $sort_as_you_go->returnSorted()), '</p>';
?>

相关文章

php引用和拷贝的区别知识点总结

对于值传递和引用传递,书本上的解释比较繁琐,而php面试中总会出现,下面我会通过一个生活的例子带大家理解它们之间区别。 第一步 假设我们去酒店订房间,我们把酒店的门牌号比作变量名,我们把...

php.ini中date.timezone设置分析

虽然知道这个参数表示“中华人民共和国”的意思,但官方文档 中并没有这样的参数,只有Asia/Shanghai、Asia/Hong_Kong等这些参数啊,为何这里可以设置为RPC,哪位给指...

利用浏览器的Javascript控制台调试PHP程序

利用浏览器的Javascript控制台调试PHP程序

PHP是一种服务器端脚本语言,用来开发动态web应用程序。与JAVA相比,没有一个好的服务器端调试工具是其限制之一。通常我们都是在PHP代码中添加echo、var_dump等语句,将变量...

DOM基础及php读取xml内容操作的方法

DOM基础及php读取xml内容操作的方法

本文实例讲述了DOM基础及php读取xml内容操作的方法。分享给大家供大家参考。具体分析如下: DOM(Document Object Model):文档对象模型。核心思想是:把 xml...

深入PHP5中的魔术方法详解

从PHP 5以后的版本,PHP中的类就可以使用魔术方法了。其规定以两个下划线(__)开头的方法都保留为魔术方法,所以建议大家函数名最好不用__开头,除非是为了重载已有的魔术方法。 1、_...