php二叉樹(shù)怎樣遍歷節(jié)點(diǎn)

PHP
小樊
82
2024-10-17 19:31:06

在 PHP 中，可以使用遞歸或迭代方法來(lái)遍歷二叉樹(shù)節(jié)點(diǎn)。這里，我們將介紹兩種方法：前序遍歷、中序遍歷和后序遍歷。

首先，定義一個(gè)簡(jiǎn)單的二叉樹(shù)節(jié)點(diǎn)類(lèi)：

class TreeNode {
    public $value;
    public $left;
    public $right;

    public function __construct($value) {
        $this->value = $value;
        $this->left = null;
        $this->right = null;
    }
}

遞歸遍歷

  1. 前序遍歷（根->左->右）
function preOrderTraversal($node) {
    if ($node === null) {
        return;
    }

    echo $node->value . " ";
    preOrderTraversal($node->left);
    preOrderTraversal($node->right);
}
  1. 中序遍歷（左->根->右）
function inOrderTraversal($node) {
    if ($node === null) {
        return;
    }

    inOrderTraversal($node->left);
    echo $node->value . " ";
    inOrderTraversal($node->right);
}
  1. 后序遍歷（左->右->根）
function postOrderTraversal($node) {
    if ($node === null) {
        return;
    }

    postOrderTraversal($node->left);
    postOrderTraversal($node->right);
    echo $node->value . " ";
}

迭代遍歷

  1. 前序遍歷（根->左->右）
function preOrderTraversalIterative($node) {
    if ($node === null) {
        return;
    }

    $stack = [$node];

    while ($stack) {
        $current = $stack[count($stack) - 1];
        $stack = array_slice($stack, 0, -1);
        echo $current->value . " ";

        if ($current->right !== null) {
            $stack[] = $current->right;
        }
        if ($current->left !== null) {
            $stack[] = $current->left;
        }
    }
}
  1. 中序遍歷（左->根->右）
function inOrderTraversalIterative($node) {
    if ($node === null) {
        return;
    }

    $stack = [];
    $current = $node;

    while ($current !== null || count($stack) > 0) {
        while ($current !== null) {
            $stack[] = $current;
            $current = $current->left;
        }

        $current = array_pop($stack);
        echo $current->value . " ";
        $current = $current->right;
    }
}
  1. 后序遍歷（左->右->根）
function postOrderTraversalIterative($node) {
    if ($node === null) {
        return;
    }

    $stack = [];
    $lastVisitedNode = null;

    $current = $node;
    while ($current !== null || count($stack) > 0) {
        if ($current !== null) {
            $stack[] = $current;
            $current = $current->left;
        } else {
            $topNode = array_pop($stack);
            if ($topNode->right !== null && $lastVisitedNode !== $topNode->right) {
                $current = $topNode->right;
            } else {
                echo $topNode->value . " ";
                $lastVisitedNode = $topNode;
            }
        }
    }
}

使用這些遍歷函數(shù)，可以方便地遍歷二叉樹(shù)的節(jié)點(diǎn)。

0 踩