温馨提示×

php二叉树能实现排序吗

PHP
小樊
81
2024-10-17 19:42:04
栏目: 编程语言

PHP中的二叉树可以实现排序。您可以创建一个自定义的二叉搜索树(BST),它允许您快速插入、删除和查找节点。在插入或删除节点时,树会自动重新排列以保持排序顺序。

以下是一个简单的PHP二叉搜索树实现,包括插入和遍历功能:

class Node {
    public $value;
    public $left;
    public $right;

    public function __construct($value) {
        $this->value = $value;
        $this->left = null;
        $this->right = null;
    }
}

class BinarySearchTree {
    public $root;

    public function __construct() {
        $this->root = null;
    }

    public function insert($value) {
        $node = new Node($value);
        if ($this->root === null) {
            $this->root = $node;
        } else {
            $this->insertNode($this->root, $node);
        }
    }

    private function insertNode($node, $newNode) {
        if ($newNode->value < $node->value) {
            if ($node->left === null) {
                $node->left = $newNode;
            } else {
                $this->insertNode($node->left, $newNode);
            }
        } else {
            if ($node->right === null) {
                $node->right = $newNode;
            } else {
                $this->insertNode($node->right, $newNode);
            }
        }
    }

    public function inOrderTraversal($node = null) {
        if ($node === null) {
            $node = $this->root;
        }

        if ($node !== null) {
            $this->inOrderTraversal($node->left);
            echo $node->value . " ";
            $this->inOrderTraversal($node->right);
        }
    }
}

$bst = new BinarySearchTree();
$values = [8, 3, 10, 1, 6, 14, 4, 7, 13];

foreach ($values as $value) {
    $bst->insert($value);
}

echo "In-order traversal of the BST: ";
$bst->inOrderTraversal();

在这个例子中,我们创建了一个简单的二叉搜索树,并向其中插入了一些值。然后,我们使用中序遍历(左-根-右)打印出排序后的值。这将输出:In-order traversal of the BST: 1 3 4 6 7 8 10 13 14

0