溫馨提示×

php二叉樹如何設(shè)計(jì)算法

PHP
小樊
81
2024-10-17 19:40:04
欄目: 編程語言

在PHP中設(shè)計(jì)一個(gè)二叉樹算法，首先需要?jiǎng)?chuàng)建一個(gè)二叉樹節(jié)點(diǎn)類（BinaryTreeNode），然后實(shí)現(xiàn)各種操作方法，例如插入、刪除、查找、遍歷等。以下是一個(gè)簡單的二叉樹節(jié)點(diǎn)類和一些基本操作的實(shí)現(xiàn)：

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

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

class BinaryTree {
    public $root;

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

    // 插入值到二叉樹中
    public function insert($value) {
        $node = new BinaryTreeNode($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);
        }
    }
}

// 使用示例
$binaryTree = new BinaryTree();
$binaryTree->insert(8);
$binaryTree->insert(3);
$binaryTree->insert(10);
$binaryTree->insert(1);
$binaryTree->insert(6);
$binaryTree->insert(14);
$binaryTree->insert(4);
$binaryTree->insert(7);
$binaryTree->insert(13);

echo "中序遍歷結(jié)果: ";
$binaryTree->inorderTraversal();

這個(gè)例子中實(shí)現(xiàn)了一個(gè)簡單的二叉搜索樹（Binary Search Tree），它允許你插入值并對(duì)樹進(jìn)行中序遍歷。你可以根據(jù)需要擴(kuò)展這個(gè)類，實(shí)現(xiàn)其他操作，如刪除節(jié)點(diǎn)、查找節(jié)點(diǎn)等。

0 踩