README

"Forest" 是一个 PHP 库，包含创建树数据结构的类，如通用树或二叉搜索树。此外，还实现了典型的树遍历策略。

如何使用 Forest

您必须区分使用 Forest 的目的。有三种不同的实现方式

• 通用树
• 二叉树
• AVL 树

通用树

通用树具有以下特征：每个节点可以有不超过一个父节点。只有一个节点可以没有父节点，这个节点是树的根。每个节点可以有任意数量的子节点

假设您想创建一个具有以下结构的树

                1
             /     \
           2         3
                   / | \
                 4   5   6
               /  \
             7      8

首先，您必须创建一个 GeneralTree 的实例。传递您想要添加到此树的项目类型

use Seboettg\Forest\GeneralTree;
use Seboettg\Forest\Item\IntegerItem;
$tree = new GeneralTree(IntegerItem::class);

您还可以为树添加其他项目，但请注意，此项目必须实现 Seboettg\Forest\Item\ItemInterface。现在您可以添加项目。第一个元素必须使用 root() 添加。

$tree
    ->root(new IntegerItem(1)) // add item objects (of type as defined in the constructor)
        ->child(2) // or simple integers (instance of IntegerItem will created automatically)  
        ->subTree(new IntegerItem(3))
            ->subTree(new IntegerItem(4))
                ->child(new IntegerItem(7))
                ->child(new IntegerItem(8))
            ->endSubTree()
            ->child(new IntegerItem(5))
            ->child(new IntegerItem(6))
        ->endSubTree();

要获取树根，可以这样做： $root = $builder->getRoot();。

更多示例请参阅 /examples/generalTree.php。

二叉树

二叉树的每个节点只能有两个子节点。插入子节点的顺序是固定的。对于每个插入的节点，以下条件适用：左节点的相关值或标签必须小于右节点的相关值或标签。 https://en.wikipedia.org/wiki/Binary_tree

如前所述，二叉树的节点始终有两个或更少的子节点。与通用树不同，二叉树本身决定节点添加的位置，以确保满足二叉节点条件。

使用二叉树进行排序

假设您想向二叉树添加以下值：d g b f a c e h。这将导致以下树结构

          d
      /       \
    b           g
  /  \         / \
 a    c       f   h 
             /
            e

如果您想以列表形式获取树内容，并选择中序遍历策略，您将得到一个排序后的列表，因为在中序策略中，首先遍历左子树，然后是根，最后是右子树。

use Seboettg\Forest\BinaryTree;
use Seboettg\Forest\General\TreeTraversalInterface;
use Seboettg\Forest\Item\StringItem;

$bst = new BinaryTree(StringItem::class);
foreach (['d', 'g', 'b', 'f', 'a', 'c', 'e', 'h'] as $char) {
    $bst->insert($char);
}

$list = $bst->toArrayList(TreeTraversalInterface::TRAVERSE_IN_ORDER);
// result is ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']

搜索：使用二叉树作为搜索树

如您所见，二叉树条件具有固有的排序。这使得此数据结构非常适合搜索场景。如果树是平衡的，最坏情况的时间复杂度仅为 O(log n)。

$result = $bst->search(new StringItem("e"));
echo $result->getItem();

但是，简单的二叉树可能会退化。假设您以预排序的顺序添加所有节点

foreach (['a', 'b', 'c', 'd', 'e'] as $char) {
    $bst->insert($char);
}

由于二叉树条件，树现在退化了。每个节点都将作为右子节点添加，因此树实际上就是一个链表。

    a
   / \
      b
     / \
        c
       / \
          d
         / \
            e

如果您想使用二叉树进行搜索，这可能会对运行时间产生巨大影响：在最坏情况下，运行时间可能是 O(n)。

为了防止这种行为，您可以使用 AVL 树。

AVL 树

AVL 树是一个自平衡的二叉搜索树。它实际上与二叉树相同，但 AVL 条件必须适用：任何节点的两个子子树的高度之差最多为 1；如果它们在任何时候超过 1，则进行重新平衡以恢复此属性。

此条件确保AVL树不会退化，因此特别适用于搜索。为了满足此条件，Georgy Adelson-Velsky和Evgenii Landis发明了一种特殊的平衡算法来修改操作。有关平衡算法的更多信息，您可以在维基百科上找到。

use Seboettg\Forest\AVLTree;
use Seboettg\Forest\Item\StringItem;
$avl = new AVLTree(StringItem::class);
foreach (['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'] as $char) {
    $avl->insert($char);
}

结果是

            d
          /   \
        b       f
       / \     / \
      a   c   e   g
                   \
                    h

二叉搜索树的一个示例

一个可能的例子是您可以在示例文件夹中找到的地址簿。