PHP 实现自排序二叉树：插入与中序遍历详解

自排序二叉树的核心逻辑

二叉树提供出色的数据组织方式。对于每个节点，满足特定条件（如小于或等于）的元素位于左节点及其子节点，其余元素位于右节点。在插入新元素时，从根节点开始判断其归属侧并向下寻找恰当位置；读取数据时，只需使用按序遍历方法遍历二叉树即可得到结果。

PHP 实现步骤

第 1 步：定义二叉树节点类

首先需要创建一个基础节点类，用于存储数据和指向左右子节点的指针。这是构建树结构的最小单元。

<?php
class Binary_Tree_Node {
    public $data;
    public $left = null;
    public $right = null;

    public function __construct($val) {
        $this->data = $val;
    }
}
?>

第 2 步：实现排序树的插入逻辑

创建一个包装类 Sorting_Tree 来管理树的整体结构。插入操作需要处理两种情况：树为空时创建根节点；树非空时，通过循环不断移动指针，直到找到左右子节点为空的合适位置进行插入。

• 目的：将数值按照“左小右大”的规则放入树中。
• 动作：初始化树容器，编写 insert 方法。
• 关键参数：待插入值 $val，当前指针 $pointer。

class Sorting_Tree {
    // 定义变量持有整棵树
    public $tree;

    public function insert($val) {
        // 情况1：树为空，创建根节点
        if (!(isset($this->tree))) {
            $this->tree = new Binary_Tree_Node($val);
        } else {
            // 情况2：树不为空，遍历寻找位置
            $pointer = $this->tree;
            
            // 无限循环直至找到空位
            for (;;) {
                // 若值小于或等于当前节点，向左查找
                if ($val <= $pointer->data) {
                    if ($pointer->left) {
                        $pointer = $pointer->left;
                    } else {
                        $pointer->left = new Binary_Tree_Node($val);
                        break;
                    }
                } else {
                    // 若值大于当前节点，向右查找
                    if ($pointer->right) {
                        $pointer = $pointer->right;
                    } else {
                        $pointer->right = new Binary_Tree_Node($val);
                        break;
                    }
                }
            }
        }
    }
}

第 3 步：添加中序遍历获取排序结果

二叉搜索树的一个关键属性是：其中序遍历（左->中->右）的结果必然是有序的。我们需要在节点类中实现 traverseInorder 方法，并在 Sorting_Tree 中调用它。

• 入口：根节点 $this->tree。
• 动作：递归调用左子树，记录当前节点，再递归调用右子树。

注：由于原文草稿中的 Binary_Tree_Node 类体为空，以下补全了必要的遍历方法以实现功能闭环：

// 补充至 Binary_Tree_Node 类中
public function traverseInorder() {
    $results = array();
    
    if ($this->left !== null) {
        $results = array_merge($results, $this->left->traverseInorder());
    }
    
    $results[] = $this->data;
    
    if ($this->right !== null) {
        $results = array_merge($results, $this->right->traverseInorder());
    }
    
    return $results;
}

测试与运行

实例化排序树后，随机生成数字进行插入，最后打印排序结果。

$sort_as_you_go = new Sorting_Tree();

// 随机插入 20 个 1-100 之间的整数
for ($i = 0; $i < 20; $i++) {
    $sort_as_you_go->insert(rand(1,100));
}

// 输出排序后的列表
$sorted_data = $sort_as_you_go->returnSorted();
echo '<p>', implode(', ', $sorted_data), '</p>';

通过以上步骤，我们实现了在一个无序的输入流中，通过二叉树的自我平衡插入机制，最终高效地获取有序数据。以上就是 PHP 实现自排序二叉树的详细内容，更多关于 PHP 数据结构设计的资料请关注本站其它相关文章！