在 PHP 中,要删除二叉树中的节点,需要遵循以下步骤:
- 查找要删除的节点
- 如果节点有两个子节点,找到其后继节点(右子树中的最小节点),用它来替换要删除的节点,然后删除后继节点。
- 如果节点只有一个子节点或没有子节点,用其子节点替换要删除的节点。
- 如果找不到要删除的节点,不做任何操作。
以下是一个简单的 PHP 类,表示二叉树及其节点,以及删除节点的函数:
class TreeNode {
public $value;
public $left;
public $right;
public function __construct($value) {
$this->value = https://www.yisu.com/ask/$value;>left = null;
$this->right = null;
}
}
class BinaryTree {
public $root;
public function __construct() {
$this->root = null;
}
public function deleteNode($value) {
$this->root = $this->deleteNodeRecursive($this->root, $value);
}
private function deleteNodeRecursive($node, $value) {
if ($node === null) {
return null;
}
if ($value < $node->value) {
$node->left = $this->deleteNodeRecursive($node->left, $value);
} elseif ($value > $node->value) {
$node->right = $this->deleteNodeRecursive($node->right, $value);
} else {
if ($node->left === null) {
return $node->right;
} elseif ($node->right === null) {
return $node->left;
}
$node->value = https://www.yisu.com/ask/$this->findMin($node->right)->value;
$node->right = $this->deleteNodeRecursive($node->right, $node->value);
}
return $node;
}
private function findMin($node) {
while ($node->left !== null) {
$node = $node->left;
}
return $node;
}
}
使用这个类,你可以创建一个二叉树并删除指定值的节点:
$tree = new BinaryTree(); $tree->root = new TreeNode(5); $tree->root->left = new TreeNode(3); $tree->root->right = new TreeNode(7); $tree->root->left->left = new TreeNode(2); $tree->root->left->right = new TreeNode(4); $tree->root->right->left = new TreeNode(6); $tree->root->right->right = new TreeNode(8); $tree->deleteNode(3);
这个例子将删除值为 3 的节点,然后树将变为:
5 / \ 2 7 / \ 6 8