1. 遍历准则

  • 前序遍历：先遍历以后结点，再遍历以后结点的左儿子，最初遍历以后结点的右儿子

  • 中序遍历：先遍历以后结点的左儿子，再遍历以后结点，最初遍历以后结点的右儿子

  • 后续遍历：先遍历以后结点的左儿子，再遍历以后结点的右儿子，最初遍历以后结点

2. 前序遍历示意图

3. 中序遍历示意图

4. 后序遍历示意图

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

<?phpnamespace 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 -> 290 -> 1 -> 2 -> 5 -> 8 -> 9 -> 10 -> 11 -> 12 -> 15 -> 16 -> 17 -> 18 -> 19 -> 290 -> 2 -> 1 -> 8 -> 9 -> 5 -> 12 -> 11 -> 17 -> 16 -> 18 -> 29 -> 19 -> 15 -> 10