欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-07-25 21:04:24
二叉树及其变体是数据结构家族里的重要组成部分。最为链表的一种变体,二叉树最适合处理需要一特定次序快速组织和检索的数据。复制代码 代码如下:
二叉树及其变体是数据结构家族里的重要组成部分。最为链表的一种变体,二叉树最适合处理需要一特定次序快速组织和检索的数据。
复制代码 代码如下:

<?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>';
?>