4.2 数据结构（PHP实现） -- 二叉树 > 二分搜索树的遍历方式（递归实现）

码农天地 - 2020-10-30 22:15:40

---

1. 遍历原则前序遍历：先遍历当前结点，再遍历当前结点的左儿子，最后遍历当前结点的右儿子中序遍历：先遍历当前结点的左儿子，再遍历当前结点，最后遍历当前结点的右儿子后续遍历：先遍历当前结点的左儿子，再遍历当前结点的右儿子，最后遍历当前结点2. 前序遍历示意图

3. 中序遍历示意图

4. 后序遍历示意图

5. 二分搜索树的递归遍历实现

<?php

namespace TreeBundle;

use ArrayBundle\BaseArray;
use StackBundle\BaseStack;

class BaseBinaryTree
{
    public function __construct()
    {
        $this->rootNode = null;
        $this->size = 0;
    }

    /**
     * 二叉树的根节点
     * @var Node
     */
    protected $rootNode;

    /**
     * 获取根节点
     * @return Node
     */
    public function getRootNode(): Node
    {
        return $this->rootNode;
    }

    /**
     * 二叉树的个数
     * @var int
     */
    protected $size;

    /**
     * 获取二叉树的元素个数
     * @return int
     */
    public function getSize(): int
    {
        return $this->size;
    }

    /**
     * 判断是否为空
     * @return bool
     */
    public function isEmpty(): bool
    {
        return $this->size == 0;
    }

    /**
     * 插入结点
     * @param mixed $value
     * @return void
     */
    public function add($value): void
    {
        // 如果不存在根节点就插入根节点
        if (is_null($this->rootNode)) {
            $this->rootNode = new Node($value);
            $this->size;
            return;
        } else {
            $this->addChild($value, $this->rootNode);
            return;
        }
    }

    /**
     * 插入儿子结点
     * @param mixed $value
     * @param Node|null $parentNode
     */
    private function addChild($value, ?Node $parentNode): void
    {
        if (bccomp($parentNode->getValue(), $value) > 0) {
            // 左儿子
            if (is_null($parentNode->getLeftChild())) {
                $parentNode->setLeftChild(new Node($value));
                $this->size++;
                return;
            } else {
                $this->addChild($value, $parentNode->getLeftChild());
            }
        } elseif (bccomp($parentNode->getValue(), $value) < 0) {
            // 右儿子
            if (is_null($parentNode->getRightChild())) {
                $parentNode->setRightChild(new Node($value));
                $this->size++;
                return;
            } else {
                $this->addChild($value, $parentNode->getRightChild());
            }
        } else {
            return;
        }
    }
    
    const TRAVERSAL_PREORDER  = 1; // 先序遍历
    const TRAVERSAL_INORDER   = 2; // 中序遍历
    const TRAVERSAL_POSTORDER = 3; // 后序遍历
    
    /**
     * 遍历二叉树
     * @param int $traversalType
     * @return string
     */
    public function traversal(int $traversalType = 1): string
    {
        $result = '';
        switch ($traversalType) {
            case self::TRAVERSAL_PREORDER:
                $this->preorderTraversal($result, $this->rootNode);
                break;
            case self::TRAVERSAL_INORDER:
                $this->inorderTraversal($result, $this->rootNode);
                break;
            case self::TRAVERSAL_POSTORDER:
                $this->postorderTraversal($result, $this->rootNode);
                break;
            default:
                break;
        }
        return $result;
    }

    /**
     * 先序遍历
     * @param string $result 结果值
     * @param Node|null $node 结点
     * @return void
     */
    protected function preorderTraversal(string &$result, ?Node $node): void
    {
        if (is_null($node)) return;

        // 拼接
        if ($result != '') $result .= ' -> ';
        // 先遍历当前节点
        $result .= $node->getValue();
        // 再遍历左儿子
        $this->preorderTraversal($result, $node->getLeftChild());
        // 在遍历右儿子
        $this->preorderTraversal($result, $node->getRightChild());
        return;
    }

    /**
     * 中序遍历
     * @param string $result 结果值
     * @param Node|null $node 结点
     * @return void
     */
    public function inorderTraversal(string &$result, ?Node $node): void
    {
        if (is_null($node)) return;

        // 先遍历左儿子
        $this->inorderTraversal($result, $node->getLeftChild());
        // 拼接
        if ($result != '') $result .= ' -> ';
        // 再获取当前结点
        $result .= $node->getValue();
        // 在遍历右儿子
        $this->inorderTraversal($result, $node->getRightChild());
        return;
    }

    /**
     * 后序遍历
     * @param string $result 结果值
     * @param Node|null $node 结点
     * @return void
     */
    public function postorderTraversal(string &$result, ?Node $node): void
    {
        if (is_null($node)) return;

        // 先遍历左儿子
        $this->postorderTraversal($result, $node->getLeftChild());
        // 在遍历右儿子
        $this->postorderTraversal($result, $node->getRightChild());
        // 拼接
        if ($result != '') $result .= ' -> ';
        // 再获取当前结点
        $result .= $node->getValue();
        return;
    }
}

6. demo

<?php
// composer自动加载
require_once __DIR__ . '/../../vendor/autoload.php';
// 获取一个二分搜索树
$tree = new TreeBundleBaseBinaryTree();
// 插入结点
$tree->add(10);
$tree->add(5);
$tree->add(15);
$tree->add(1);
$tree->add(0);
$tree->add(2);
$tree->add(9);
$tree->add(8);
$tree->add(11);
$tree->add(12);
$tree->add(19);
$tree->add(18);
$tree->add(29);
$tree->add(16);
$tree->add(17);
// 前序遍历
echo $tree->traversal(TreeBundleBaseBinaryTree::TRAVERSAL_PREORDER). PHP_EOL;
// 中序遍历
echo $tree->traversal(TreeBundleBaseBinaryTree::TRAVERSAL_INORDER). PHP_EOL;
// 后续遍历
echo $tree->traversal(TreeBundleBaseBinaryTree::TRAVERSAL_POSTORDER). PHP_EOL;

打印结果：

10 -> 5 -> 1 -> 0 -> 2 -> 9 -> 8 -> 15 -> 11 -> 12 -> 19 -> 18 -> 16 -> 17 -> 29
0 -> 1 -> 2 -> 5 -> 8 -> 9 -> 10 -> 11 -> 12 -> 15 -> 16 -> 17 -> 18 -> 19 -> 29
0 -> 2 -> 1 -> 8 -> 9 -> 5 -> 12 -> 11 -> 17 -> 16 -> 18 -> 29 -> 19 -> 15 -> 10

php介绍

PHP即“超文本预处理器”，是一种通用开源脚本语言。PHP是在服务器端执行的脚本语言，与C语言类似，是常用的网站编程语言。PHP独特的语法混合了C、Java、Perl以及 PHP 自创的语法。利于学习，使用广泛，主要适用于Web开发领域。

更多关于php的阅读

Tags 标签

数据结构二叉树php递归

扩展阅读