阅读量:0
在PHP中，构建一个平衡的二叉树可以使用AVL树。AVL树是一种自平衡二叉搜索树，它在每次插入或删除节点后都会自动调整以保持平衡状态。以下是一个简单的PHP实现：
class TreeNode { public $value; public $left; public $right; public $height; public function __construct($value) { $this->value = $value; $this->left = null; $this->right = null; $this->height = 1; } } class AVLTree { private $root; private function getHeight($node) { if ($node === null) { return 0; } return $node->height; } private function getBalanceFactor($node) { if ($node === null) { return 0; } return $this->getHeight($node->left) - $this->getHeight($node->right); } private function rightRotate($y) { $x = $y->left; $T2 = $x->right; $x->right = $y; $y->left = $T2; $y->height = max($this->getHeight($y->left), $this->getHeight($y->right)) + 1; $x->height = max($this->getHeight($x->left), $this->getHeight($x->right)) + 1; return $x; } private function leftRotate($x) { $y = $x->right; $T2 = $y->left; $y->left = $x; $x->right = $T2; $x->height = max($this->getHeight($x->left), $this->getHeight($x->right)) + 1; $y->height = max($this->getHeight($y->left), $this->getHeight($y->right)) + 1; return $y; } public function insert($value) { $this->root = $this->insertNode($this->root, $value); } private function insertNode($node, $value) { if ($node === null) { return new TreeNode($value); } if ($value < $node->value) { $node->left = $this->insertNode($node->left, $value); } else if ($value > $node->value) { $node->right = $this->insertNode($node->right, $value); } else { return $node; // Duplicate values are not allowed } $node->height = 1 + max($this->getHeight($node->left), $this->getHeight($node->right)); $balanceFactor = $this->getBalanceFactor($node); // Left Left Case if ($balanceFactor > 1 && $value < $node->left->value) { return $this->rightRotate($node); } // Right Right Case if ($balanceFactor < -1 && $value > $node->right->value) { return $this->leftRotate($node); } // Left Right Case if ($balanceFactor > 1 && $value > $node->left->value) { $node->left = $this->leftRotate($node->left); return $this->rightRotate($node); } // Right Left Case if ($balanceFactor < -1 && $value < $node->right->value) { $node->right = $this->rightRotate($node->right); return $this->leftRotate($node); } return $node; } } // Example usage: $avlTree = new AVLTree(); $avlTree->insert(10); $avlTree->insert(20); $avlTree->insert(30); $avlTree->insert(40); $avlTree->insert(50); $avlTree->insert(25); 这个实现包括了一个TreeNode类，用于表示二叉树的节点，以及一个AVLTree类，用于管理二叉树的操作。AVLTree类包含了插入节点、左旋转、右旋转等方法，以确保树在每次插入或删除节点后都能保持平衡。
