PHP Class&Object -- 解析PHP实现二叉树

yipeiwu_com5年前PHP代码库
二叉树及其变体是数据结构家族里的重要组成部分。最为链表的一种变体,二叉树最适合处理需要一特定次序快速组织和检索的数据。
复制代码 代码如下:

<?php
// Define a class to implement a binary tree
class Binary_Tree_Node {
    // Define the variable to hold our data:
    public $data;
    // And a variable to hold the left and right objects:
    public $left;
    public $right;

    // A constructor method that allows for data to be passed in
    public function __construct($d = NULL) {
        $this->data = $d;
    }

    // Traverse the tree, left to right, in pre-order, returning an array
    // Preorder means that each node's value preceeds its children.
    public function traversePreorder() {
        // Prep some variables.
        $l = array();
        $r = array();
        // Read in the left and right children appropriately traversed:
        if ($this->left) { $l = $this->left->traversePreorder(); }
        if ($this->right) { $r = $this->right->traversePreorder(); }

        // Return a merged array of the current value, left, and right:
        return array_merge(array($this->data), $l, $r);
    }
    // Traverse the tree, left to right, in postorder, returning an array
    // Postorder means that each node's value follows its children.
    public function traversePostorder() {
        // Prep some variables.
        $l = array();
        $r = array();
        // Read in the left and right children appropriately traversed:
        if ($this->left) { $l = $this->left->traversePostorder(); }
        if ($this->right) { $r = $this->right->traversePostorder(); }

        // Return a merged array of the current value, left, and right:
        return array_merge($l, $r, array($this->data));
    }
    // Traverse the tree, left to right, in-order, returning an array.
    // In-order means that values are ordered as left children, then the
    //  node value, then the right children.
    public function traverseInorder() {
        // Prep some variables.
        $l = array();
        $r = array();
        // Read in the left and right children appropriately traversed:
        if ($this->left) { $l = $this->left->traverseInorder(); }
        if ($this->right) { $r = $this->right->traverseInorder(); }

        // Return a merged array of the current value, left, and right:
        return array_merge($l, array($this->data), $r);
    }
}
// Let's create a binary tree that will equal the following:    3
//                                                             / /     
//                                                            h   9     
//                                                               / /    
// Create the tree:                                             6   a   
$tree = new Binary_Tree_Node(3);
$tree->left = new Binary_Tree_Node('h');
$tree->right = new Binary_Tree_Node(9);
$tree->right->left = new Binary_Tree_Node(6);
$tree->right->right = new Binary_Tree_Node('a');
// Now traverse this tree in all possible orders and display the results:
// Pre-order: 3, h, 9, 6, a
echo '<p>', implode(', ', $tree->traversePreorder()), '</p>';
// Post-order: h, 9, 6, a, 3
echo '<p>', implode(', ', $tree->traversePostorder()), '</p>';
// In-order: h, 3, 6, 9, a
echo '<p>', implode(', ', $tree->traverseInorder()), '</p>';
?>

相关文章

php面向对象 字段的声明与使用

字段是用于描述类的么个方面的性质。 字段是用于描述类的某个方面的性质。它与一般的PHP 变量非常相似,只是有一些细微的差别,本节将介绍这些差别。这一节还将讨论如何声明和使用字段,下一节则...

dirname(__FILE__)的含义和应用说明

__FILE__表示当前所在文件的绝对路径包括文件名,dirname(__FILE__)表示当前文件的绝对路径,basename(__FILE__)表示当前文件的文件名称,dirname...

php精度计算的问题解析

PHP var_dump(intval(0.58 * 100)); 正确结果是 57,而不是 58 浮点运算惹的祸 其实这些结果都并非语言的 bug,但和语言的实现原理有关,...

探讨:如何通过stats命令分析Memcached的内部状态

Memcached有个stats命令,通过它可以查看Memcached服务的许多状态信息。使用方法如下:先在命令行直接输入telnet 主机名端口号,连接到memcached服务器,然后...

php 过滤器实现代码

在以前,一个用户通过网络主要是获取信息。而如今的网络刚更注重与用户的交互,用户不再仅仅是网站的浏览者,也是网站内容的制造者。由以前单纯的“读”向“写”以及“共同创作”发展,由被动接收信息...